Boost logo

Boost :

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

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!


Boost list run by bdawes at, gregod at, cpdaniel at, john at