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-05 04:18:26

>Unfortunately, it's worse than that. My O(N^2), base-10^8
>school-method multiplication stores multiple carries in its
>rows of the multiplication algorithm. These can
>can potentially overflow 64-bit.
>
>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:

   //
   // There is a limit on how many limbs this algorithm can handle without 
dropping digits
   // due to overflow in the carry, it is:
   //
   // FLOOR( (2^64 - 1) / (10^8 * 10^8) )  ==  1844
   //
   BOOST_STATIC_ASSERT_MSG(mp_elem_number < 1800, "Too many limbs in the 
data type for the multiplication algorithm - unsupported precision in 
cpp_dec_float.");

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!

John.