While doing the tedious work of documenting my software I tried to find the original source of the divide and conquer method for the conversion of numbers of one base to a number in another base (mostly binary to decimal and vice versa these days). The obligatory "If in doubt, it was Knuth." was not very helpful: In his TAoCP[^1] in the answer to exercise 4.4.14 he just gave the hint

Similarly Schönhage has observed that we can convert a ($2^n\log 10$)-bit number $U$ from binary to decimal, in $O(nM(2^n))$ steps.

The single place where Arnold Schönhage said something in that direction was in a book[^2] he co-authored

There is a standard divide-and-conquer method (here mentioned as a nice exercise) by which the full speed of the of the fast multiplication routines can be utilized so that a time bound of order $\Theta\cdot n \cdot(\log n)^2\log \log n$ for the conversion of $n$ word operands […]

There are other findings, for example Richard Brent in an article[^3] but he pointed to D. Knuth at[^1].

The method is most probably not very old because it needs asymptotically fast multiplication (There is the Nikhilam method from India[^4], Karatsuba[^5] in the West was much later) to function properly, so where did it originate, who can I cite? Or is it lost, deep in the dusty abyss of some obscure mathematical almanac, long forgotten?

[^1] Knuth, Donald-E. "The Art of Computer Programming. Vol. 2." (1998).

[^2] Schönhage, Arnold, Andreas FW Grotefeld, and Ekkehart Vetter. "Fast algorithms: a multitape turing machine implementation". BI Wissenschaftsverlag, 1994.

[^3] Brent, Richard P. "The complexity of multiple-precision arithmetic." The Complexity of Computational Problem Solving (1976): 126-165.

[^4] Tirtha, Swami Bharati Krishna, Vasudeva Sharana Agrawala, and V. S. Agrawala. Vedic mathematics. Vol. 10. Motilal Banarsidass Publ., 1992.

[^5] Karatsuba, Anatolii, and Yu Ofman. "Multiplication of multidigit numbers on automata." Soviet physics doklady. Vol. 7. 1963.


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.