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:45:44

On Thu, 03 Mar 2011 22:23:11 -0800
"Jeffrey Lee Hellrung, Jr." <jhellrung_at_[hidden]> wrote:

>> [...] 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

Curious. That's not my experience, though the implementation I was
trying to get working may well have been buggy.

> 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.

It might indeed. I'll take another look at that when I have the time,
though it might be a few weeks by the look of things.
-- 
Chad Nelson
Oak Circle Software, Inc.
*
*
*