Proof of concept, 25% faster than n log n, multiplication algorithm for 8x8

[Marco Bodrato]

Ciao,

Il Gio, 27 Ottobre 2022 7:56 pm, Hans Petter Selasky ha scritto:
> The algorithm shown below needs only 18 non-complex
> multiplications to complete an 8 by 8 multiplication, similarly to a FFT
> transform. Currently looking into scalability :-)

Look at Toom's algorithm. It needs 15 integer multiplications to complete
an 8x8 multiplication.

It's Toom-8 flavour is implemented in GMP, as a more flexible
Toom-"8andHalf".

It is faster than FFT for "not so large" operands, but its asymptotic
complexity is worst than that of FFT.

Ĝis,
m

-- 
http://bodrato.it/software/toom.html