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
// 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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk