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)?
Interesting...
> 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()
and eval_divide().
>> 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