Re: [boost] [xint] Boost.XInt formal review

Subject: Re: [boost] [xint] Boost.XInt formal review
From: Chad Nelson (chad.thecomfychair_at_[hidden])
Date: 2011-03-04 01:12:30

On Fri, 04 Mar 2011 02:42:32 +0900
"k.inaba" <kiki_at_[hidden]> wrote:

> This is just a quick question, not meant to be a full review.
>
> The documentation says that the complexity of multiplication is
> O(n^2). But as far as I know, there are asymptotically better
> algorithms such as Karatsuba method O(n^1.585) or FFT O(n log(n)
> log(log(n))), etc:
> http://en.wikipedia.org/wiki/Multiplication_algorithm
>
> Are there any reason that these methods aren't used in XInt?

From <http://www.oakcircle.com/xint_docs/r_interface_design_only.html>:

    It does not, at present, implement a multiplication scheme with
    better performance than the "basecase" mentioned in section 3.4 of
    n1692, primarily because I haven't had the time to research all of
    them yet. I suspect that most people using the library will usually
    be using numbers below the threshold where the more exotic
    algorithms are faster, but I plan to add at least one of them in
    the future, maybe several.

> For large numbers, they work much faster than the textbook
> multiplication, and they can be implemented perfectly portably in
> C++. 

They only become faster for *really* large numbers, much larger than I
generally work with -- on the order of tens of thousands of bits, if I
remember correctly. For the more usual case of 4Kbit numbers at most,
they have noticeably worse performance than the algorithm that's in
there now.

I've experimented with both Karatsuba and FFT, but after discovering
that limitation, I abandoned them to concentrate on getting the rest of
the library working right. As mentioned, I'll look at them again in the
future.
-- 
Chad Nelson
Oak Circle Software, Inc.
*
*
*