[fpc-devel] Arbitrary-precision arithmetic unit

[Alexander Klenin]

On Mon, Mar 2, 2009 at 23:13, Michael Schnell <mschnell at lumino.de> wrote:
>
>> 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²).
>
> I suppose in fact it's o(n * ln(n) )

It is O(n^log 3) ~ O(n^1.58)

On Mon, Mar 2, 2009 at 21:58, Michael Schnell <mschnell at lumino.de> wrote:
> see Wikipedia on Karazuba
Perhaps you should do this too ;-)
I would also recommend wolfram's world article, since Wikipedia one is
lacking in math details.

-- 
Alexander S. Klenin