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$
  • $\begingroup$ In the Fast Algorithms for Integers section of this 2019 numberworld article on Radix Conversion, author Alexander Yee says "It's unknown when the Divide-and-Conquer radix conversion was first discovered, but it is detailed in Richard Brent's Modern Computer Arithmetic Today." $\endgroup$ – martineau Jul 8 at 17:22
  • $\begingroup$ @martineau yes, it seems as if all things point to R. P. Brent. He is still alive but I have no email address, the only way of contact I found is the postal address of the Mathematical Sciences Institute at Canberra U. Ah, why not; let's dip the nib into some real ink and put some letters on some real paper and wait and see what happens. I will update this post accordingly when and if necessary. $\endgroup$ – deamentiaemundi Jul 8 at 19:16
  • $\begingroup$ Just ran across a link to a pdf of Modern Computer Arithmetic that might have some clues (or be useful to you in other ways). In addition, the author of this answer claims to have corresponded with the authors of the textbook. $\endgroup$ – martineau Jul 8 at 19:29
  • 1
    $\begingroup$ @martineau I see Paul Zimmermann (the second author of MCA) is still active and has an email address (and a phone number, but my French is quasi non-existant, so...), will give it a try. Thanks! $\endgroup$ – deamentiaemundi Jul 8 at 20:12

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.