[fpc-devel] Arbitrary-precision arithmetic unit

[Michael Schnell]

> 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