Implementations of integer multiplication often choose different algorithms for different input sizes: for smallest numbers the school book method is preferred, for largest sizes the method based on FFT are fastest currently known.

For medium sized inputs, what other methods there are besides the ones by Karatsuba, Toom and Cook?

  • $\begingroup$ Probably not, but the GMP Multiplication Algorithms page has four variations of Toom-Cook for different ranges. $\endgroup$ – Somos Jul 7 '18 at 10:51
  • $\begingroup$ In my experience working on software for arbitrary-precision arithmetic, and to my knowledge (from extensive literature search), there are no algorithms in existence for medium-sized operands besides Karatsuba and Toom-Cook. It would be exiting if someone were to provide an answer that proves me wrong. $\endgroup$ – njuffa Jul 24 '18 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.