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:
> 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!
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk