Alexander Klenin a écrit :
On Mon, Mar 2, 2009 at 21:58, Michael Schnell <[email protected]> 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
_______________________________________________
fpc-devel maillist - [email protected]
http://lists.freepascal.org/mailman/listinfo/fpc-devel
