bodr...@mail.dm.unipi.it writes: > Remember that toom42 simply is "unbalanced Toom-3" (i.e. same cost as > toom33), toom63 is "unbalanced Toom-4'n'half" and mpn_mulmod_bnm1 can be > used for "unbalanced FFT". With this point of view, it should be easier to > understand that, in the FFT range, mulmod is the best strategy (among the > three).
Ah. So then the only unbalanced algorithms which can beat fft at large sizes are *interated* multiplication doing one block of the larger operand at a time. Which are linear in the size of the larger operand. Not sure how relevant that is for sizes like 3n x n and 2n x n, though That's also related to Torbjörn's suggestion of reusing the transform of the smaller operand. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance. _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
