[fpc-devel] Arbitrary-precision arithmetic unit

[m2]

Alexander Klenin a écrit :
> On Mon, Mar 2, 2009 at 21:58, Michael Schnell <mschnell at lumino.de> wrote:
>> In the "Deutsches Lazarus Forum" there was a project called "GNURZ"
>> providing this. It was quite promising and I provided some ASM-optimization
>> for it.
>>
>> Here the original Author implemented a "Karazuba" multiplication, that is a
>> lot faster than the standard Multiplication algorithm, when very long
>> numbers are handled (see Wikipedia on Karazuba).
> 
> It is Karatsuba, actually (he is Russian professor). I studied this
> algorithm at university.
> I vaguely remember that although it is asymptotically faster than FFT,
> implementation
> is complicated and the time constant is higher, so FFT is used in
> practice except
> for really large problems.

As a matter of fact, this is the other way. FFT is asymptotically
better than Karatsuba. Karatsuba is good for integers in, say, the range
800..8000 bits. Then Toom-3 is better than FFT up to, say, 80000 bits.
(That's why I didn't code FFT in NX, I never needed to work with such
monsters. 80000 bits ~ 24000 decimal digits.)

mm
--
http://www.ellipsa.net