2016/05/22 by Cheng, Yiping
#F.2.1 #FOS: Mathematics #I.1.2 #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.1605.06760
The traditional Karatsuba algorithm for the multiplication of polynomials and multi-precision integers has a time complexity of O(n1.59) and a space complexity of O(n). Roche proposed an improved algorithm with the same O(n1.59) time complexity but with a much reduced O(log n) 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.