3
$\begingroup$

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.

$\endgroup$

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.