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

Subject: Re: [boost] [xint] Boost.XInt formal review
From: Jeffrey Lee Hellrung, Jr. (jhellrung_at_[hidden])
Date: 2011-03-04 01:23:11

On 3/3/2011 10:12 PM, Chad Nelson wrote:
> 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.
[...]

The wikipedia article on Karatsuba's method suggests a switch from the 
grade-school algorithm to Karatsuba at around 320 to 640 bits:

http://en.wikipedia.org/wiki/Karatsuba#Efficiency_analysis

I don't consider an implementation of Karatsuba's method or any other 
asymptotically faster method to be necessary at present, but it might be 
surprising at what point the asymptotically faster methods are 
practically faster.

- Jeff