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-10 04:18:18

> Long e-mail here. Lot's of information and need your inputs.
>
> My attempts with recursive Karatsuba in base-10 were a disaster.
> The expected benefit was not achieved---all the way up to
> 100,000 decimal digits.

:-(

> I experimented with FFTs. We need your inputs if we *really*
> want to make very high-precision available at this stage.
> The community might expect it. But I really don't know
> if you would like to introduce a potentially poorly tested
> FFT-based multiplication scheme at this late stage in the
> game or if you would prefer to do it in a more controlled
> and better tested fashion after review, potential acceptance
> and establishment.
>
> A *dumb* FFT was slow, not out-performing O(N^2) until
> over 50,000 decimal digits. A merely *naive* FFT of
> Danielson-Lanczos type was better, out-performing O(N^2)
> at around 10,000 decimal digits. It's low-impact, clean code,
> maybe about 30 lines of code.

Nice, had no idea it could be implemented in such a small space!

> Still, the naive FFT gives a slow multiplication. Performing 100 
> individual
> 100,000 digit square-root calculation with the naive FFT requires 12 
> seconds
> on my machine. State-of-the-art MPFR does the same test square-root in
> about 0.8 sec. This puts us off of the best by a factor of 15.
> My goal with base-10, no Karatsuba and no Toom-Cook would be, say,
> 3-4 times worse. Still, the naive FFT is a good start---not embarrassing,
> rather, shows the potential and paves the way for improvement
> over the years.
>
> My program crashed for a million digit square-root calculation.
>
> I could potentially make a much faster FFT (factor 3 or 4)
> in fall or
> winter.
>
> The square-root algorithm required some slight modifications
> to properly converge for high digits. Other Newton-iterations
> may need similar tuning if we decide to make high-precision
> available. Plus ultra-high precision needs other algos for
> atan, exp, etc., as Taylor loses effectiveness. Would need to
> build these up over years if you would like to go that way.

Sigh.... yes I forgot about those, so it sounds like for now at least these 
more advanced algorithms aren't going to help much - at least not for 
cpp_dec_float's target ordiance - those wanting higher precision than long 
double, but not crazy digit counts?

So my gut feeling is to hold off for now, and maybe do things properly later 
(dynamic allocation, better std lib support etc)?

>>> So maybe examples are a higher priority for now?
>
> We have some examples now. I am awaiting your input if
> you think I should contribute more floating-point examples.

I think the existing ones work out quite nicely now thanks, I could use some 
ideas for integer and maybe rational number examples, but that's a whole 
other ball game ;-)

>> P.S. I also have a potential solution to my excessive guard digits.
>
> I resolved the excessive guard digit issue and reduced the guard digits
> to the necessary amount (and provide rationale in a code comment).
>
> It may require testing the test cases again because tiny tolerances
> might shift. Not expected, but maybe.
>
> With your permission, I can check it in on Tuesday.

Sure, or mail me a patch and I'll run the full tests (or you can - just cd 
into libs/multiprecision/test and do a "bjam --enable-specfun" and then wait 
for a long time!)

Thanks, John.