Abstract
The recursion tree resulting from Karatsuba’s formula is built here using an interleaved splitting scheme rather than the traditional left/right one. This allows an easier access to the nodes of the tree and some of them are initially flattened all at once into a single recursive formula. The whole tree is then flattened further into a convolution formula involving less elementary multiplications than the usual Cauchy product—leading to iterative (rather than recursive) implementations of the algorithm. Unlike the traditional splitting scheme, the interleaved approach may also be applied to infinite power series, and the corresponding formulas are also given.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
The \(1/(1-x)\) part is an usual generating function for \(1+x+x^2+x^3+x^4+\cdots \) and multplicating it by \((1-x^{2^m})\) allows to truncate the series to an arbitrary degree.
This property can also be noticed in the illustration of the interleaved splitting scheme at the beginning of the current section for a polynomial of degree 7, formally applying this splitting scheme being deeply related to applying the formula (1) with regard to the degree of computed terms. In this example, the constant term of each sparse polynomial in parentheses at any level is \(a_k\) when the external factor of this polynomial is \(x^k\).
A tree is traversed in level-order when each node on a level is visited before going to a lower level. Of course, we only care here about primary indirect nodes.
By convention \({ \texttt {A268289}}_0=0\), the formal definition of the sequence is slightly different from the plain english one above which would imply the wrong statement \({ \texttt {A268289}}_0=-1\).
This symbol is compact but not very common; it can be found however in an article by Shigeru Kuroda, Shestakov–Umirbaev reductions and Nagata’s conjecture on a polynomial automorphism (2007).
This is one of the most important concepts behind the famous Numpy module for Python; strides allow to build views on parts of an existing array without actually copying it.
References
The on-line encyclopedia of integer sequences. Published electronically at https://oeis.org. Accessed 1 Nov 2019.
Anatoly Karatsuba, Yuri Ofman. Multiplication of many-digital numbers by automatic computers. Nauk SSSR: Dokl. Akad; 1962.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of Interest
The authors declare that they have no conflict of interest. The current article is accessible on http://export.arxiv.org/pdf/1902.08982.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The first version of this paper was carefully reviewed by Aurélien Monteillet and Anthony Travers. Their comments have been taken into account in the current revision.
Rights and permissions
About this article
Cite this article
Baruchel, T. Flattening Karatsuba’s Recursion Tree into a Single Summation. SN COMPUT. SCI. 1, 48 (2020). https://doi.org/10.1007/s42979-019-0049-1
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s42979-019-0049-1