Re: [boost] [Review Request] Multiprecision Arithmetic Library

Subject: Re: [boost] [Review Request] Multiprecision Arithmetic Library
From: Christopher Kormanyos (e_float_at_[hidden])
Date: 2012-04-05 17:57:33

>> Also, since cpp_dec_float does not climb the

>> digit scale elegantly switching from school O(N^2)
>> multiply to Karatsuba to FFT, the N^2 crushes efficiency
>> for more than a few hundred digits. I had originally set
>> an upper limit of 300 decimal digits.
>> 
>> It's so critical that I would maybe go so far as to
>> use a static_assert on it.

> For sure, looking at the code, this is the Coomba algorithm yes?
> Assuming that's correct I'm adding:

<snip>

> That still allows 14000 digits which would be grindingly slow at O(N^2), but 
> at least the basic algorithm should work ;-)
> Thanks for the heads up!
> John. 

Yes. Thanks!

Did I ever mention that I love what you have done with this stuff?
It's simply great programming!

But let's face it, my O(N^2) is very slowwww for digits.

I've got to do better than that!

What would you say if I suggested, late in the game,
that I add, *at least*, a naive FFT multiplication based on
complex decimation in radix-2. We won't break any speed records
or catch GMP at a million digits, but at least we won't end up with
a stand-still at 10,000 decimal digits.

In your opinion, should I take a crack at this if I find a spare afternoon?

Of course, in the future we need to cooperate with FFT specialists
who could get the speed of big-num types (with BPL licensing)
up to state.of-the-art. But maybe we can get just a bit more
functionality now before review and potential first distrubition.

Best regards, Chris