On Mon, Mar 2, 2009 at 23:13, Michael Schnell <[email protected]> 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 <[email protected]> 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 _______________________________________________ fpc-devel maillist - [email protected] http://lists.freepascal.org/mailman/listinfo/fpc-devel
