It is Karatsuba, actually (he is Russian professor).
:) Thanks :)
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.
In this application the make-up of the algorithm (compared to the plain
old "school" multiplication) in fact is a little bit similar to how FFT
works (compared to doing straight DFT), but regarding to what it results
in here it has nothing to do with what a Fourier Transform results in.
But like FFT it's speed is O(n), while the speed of plain old "school"
multiplication and DFT is O(n²).
In fact it's not very complicated, it's done as recursive function calls
that do partial multiplications for half of the word cont. If the word
count gets below a predefined limit, normal multiplication is done, as
here same is faster (and the recursion level is limited).
Unfortunately, I do not read German, so I it is hard for me to understand,
and this code even uses German procedure names (!).
If someone will at least provide an english translation, I might help
with code cleanup
to get the code ready for FPC inclusion.
If someone is inclined to manage this as an open source project, I'll be
happy to help....
Good, although getting explicit license from the author is always
preferable.
He certainly will provide this (e.g. LGLP) when the project is out of Alpha.
-Michael
_______________________________________________
fpc-devel maillist - [email protected]
http://lists.freepascal.org/mailman/listinfo/fpc-devel
