Space-Efficient Karatsuba Multiplication for Multi-Precision Integers

MaRDI QIDQ6511690arXivFDO

Authors Yiping Cheng

Published in arXiv

Abstract: The traditional Karatsuba algorithm for the multiplication of polynomials and multi-precision integers has a time complexity of $O(n^{1.59})$ and a space complexity of $O(n)$. Roche proposed an improved algorithm with the same $O(n^{1.59})$ time complexity but with a much reduced $O(logn)$ space complexity. In Roche's paper details were provided for multiplication of polynomials, but not for multi-precision integers. Multi-precision integers differ from polynomials by the presence of carries, which poses difficulties in implementing Roche's scheme in multi-precision integers. This paper provides a detailed solution to these difficulties. Finally, numerical comparisons between the schoolbook, traditional Karatsuba, and space-efficient Karatsuba algorithms are provided.

This page was built for publication: Space-Efficient Karatsuba Multiplication for Multi-Precision Integers

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