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

Subject: Re: [boost] [Review Request] Multiprecision Arithmetic Library
From: John Maddock (boost.regex_at_[hidden])
Date: 2012-04-06 04:20:53

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

All your fault for writing the arithmetic code though ;-)

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

Up to a point - for smaller digit counts it's usually the best you can do in 
practice.

> 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?

Maybe.  My understanding is that FFT doesn't become viable until the digit 
count grows truely huge?  Would the Karatsuba algorithm be viable sooner and 
help more users?

My gut feeling is that the current implementation is perfectly fine up to a 
few hundred (and maybe a thousand?) decimal places, which will probably take 
care of most use cases.... well my use cases anyway!

So maybe examples are a higher priority for now?

We could also go through the current the code looking for optimisation 
oportunities - for example would the inversion code be more efficient using 
Halley rather than Newton iteration (see for example 
http://numbers.computation.free.fr/Constants/Algorithms/inverse.html)?

Also multiplication and division by integer (relatively common operations?) 
as special cases.

> 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.

For sure, there's always much more that can be done, it's just a case of 
knowing when to stop! ;-)

Cheers, John.