[fpc-devel] Arbitrary-precision arithmetic unit
klenin at gmail.com
Mon Mar 2 14:26:14 CET 2009
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
More information about the fpc-devel