Subject: Re: [boost] [Review Request] Multiprecision Arithmetic Library
From: Christopher Kormanyos (e_float_at_[hidden])
Date: 2012-04-06 06:57:23
>> But let's face it, my O(N^2) is very slowwww for 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!
In my previous unpublished work (mp_cpp, also using base-10^8), I tuned to the following:
static const INT32 mp_elem_karatsuba_min = static_cast< INT32>(40); // Approx. 280 digits.
static const INT32 mp_elem_fft_min = static_cast< INT32>(129); // Approx. 900 digits.
I've got a recursive Karatsuba template available in my catalog already.
Maybe we should try it out. The FFT mentioned above was FFTW
(a sadly non-BPL wonder of mankind) so a vanilla FFT would be,
maybe, 2 or 3 times slower.
> So maybe examples are a higher priority for now?
Yes, you are right. I just don't want to get into trouble with the community.
Everyone wants to compute a million digits of pi, and they might get mad
at us if boost can't do it.
But you're right below. We need to stop and get a work of high quality out
there to the world---maybe improving it later, like in the fall of 2012.
In fact, as I told you and Paul Bristow
(both of whom have helped so much in this project),
I'm actually booked solid through summer.
> 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.
Fortunately, we already have this. The routines mul_unsigned_long_long()
and div_unsigned_long_long() utilize O(N) linear mul/div by integer.
And we support them in your interface functions eval_multiply()
>> 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.
You are right. We need to stop real soon and review what we've got.
If I can contribute anything like Karatsuba or FFT relatively quickly,
yet adequately reliable, I'll let you know.
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