Decimal arithmetic

[Paul Zimmermann]

> > Of course this assumes the base conversion really has complexity
> > O(M(n) log(n)), which is not completely true with gmp-4.2.1: the base-2 to
> > base-10 conversion implements a subquadratic algorithm, but relies on the
> > division, which has cost O(M(n) log(n)) in 4.2.1 instead of O(M(n)) in 5.0.
> > Thus the current base 2 -> base 10 conversion has cost O(M(n) log(n)^2).
> 
> Fascinating. I'll have to look where the division comes in. As far as I 
> recall, there is no need for division.

The division comes in as follows: to convert in decimal a binary number N of n 
bits, you compute a power D=10^k of about half size, and divide N by D. Then
you convert recursively the quotient (upper part of the decimal output) and
the remainder (lower part). This gives C(n) = D(n/2) + 2 C(n/2). See section
1.7.2 from [1].

You can avoid the division using Bernstein's "scaled remainder trees"; see
exercise 1.9.21, but you still need at least one division at the top level.
The input routine (base 10 to base 2) needs only multiplications.

Along this topic, I suggest Exercise 1.9.23 is relevant too.

Paul

[1] Modern Computer Arithmetic, Richard Brent and Paul Zimmermann,
 version 0.1.1, November 2006, http://www.loria.fr/~zimmerma/mca/mca-0.1.1.pdf.