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
> 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
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
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! ;-)