Proof of concept, 25% faster than n log n, multiplication algorithm for 8x8
Marco Bodrato
bodrato at mail.dm.unipi.it
Fri Oct 28 20:32:16 CEST 2022
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
More information about the gmp-discuss
mailing list