Re: [boost] [xint] Third release is ready, requesting preliminary review

Subject: Re: [boost] [xint] Third release is ready, requesting preliminary review
From: DE (satan66613_at_[hidden])
Date: 2010-05-02 16:46:13

on 02.05.2010 at 20:48
 Chad Nelson wrote :
>> I'm curious:  Are you researching, or do you have plans to research,
>> more efficient multiplication algorithms (Karatsuba's, FFT-based, etc.)?
>> I believe these only become efficient at large integers, but I'm not
>> sure how large...

> Yes, I already have a description of the Karatsuba one to work from, for
> a later release. It's supposed to be more effective than the traditional
> version once you get past a certain size, but I don't know what that
> size is yet. Once that's added, I'll look into the others.

wikipedia says that kartsuba gains any advantage starting from ~10000
_decimal_ digits (that is roughly 30000 bits)
i don't know if that is practical to have an implementation onboard
unless you want to multiply numbers of order of googolplex

sorry for spurious reply

-- 
Pavel
P.S.
if you notice a grammar mistake or weird phrasing in my message
please point it out