The Karatsuba integer middle product

DOI10.1016/J.JSC.2012.02.001MaRDI QIDQ414629zbMATH OpenOpenAlexFDO

Authors David Harvey

Publication date 11 May 2012

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jsc.2012.02.001

zbMATH Keywords

efficient algorithminteger arithmeticmiddle product

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Polynomials, factorization in commutative rings (13P05)

Recommendations

• scientific article; zbMATH DE number 1254004
• Missing a trick: Karatsuba variations
• Even faster integer multiplication
• Integer multiplication in time \(O(n\log n)\)
• The middle product algorithm. I: Speeding up the division and square root of power series

Cites work

• scientific article; zbMATH DE number 2151179 (Why is no real title available?)
• Batch Binary Edwards
• Integer and polynomial multiplication: towards optimal Toom-Cook matrices
• On short multiplications and divisions
• The middle product algorithm. I: Speeding up the division and square root of power series

Cited in

(2)

• The combinatorics of product scanning multiplication and squaring
• A probabilistic algorithm for verifying polynomial middle product in linear time

Describes a project that uses

Uses Software

• gmp

This page was built for publication: The Karatsuba integer middle product

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414629)