Re: Binary-Decimal conversion for extremely large integers

[Paul.Zimmermann@xxxxxxxx (Paul Zimmermann)]

       Dear Thorsten,

> Date: Thu, 09 Aug 2007 17:29:14 +0200
> From: Thorsten Siebenborn <7_born@xxxxxx>
>
> For my arbitrary precision library I need conversion
> routines for unlimited integers. AFAIK you can't circumvent
> the division by ten, so currently I am extracting the last
> decimal digit, subtract it from the integer
> and divide the integer by ten with the 1/10 = 51/512*256/255
> add-shift method until all decimal digits have been parsed.
>
> What is the current state of art with binary-decimal
> conversion ? The Clinger, Gay, Steele & White papers are
> more interested to convert IEEE numbers perfectly rounded
> instead of the problem to convert integers as fast as
> possible.
>
> Best,
> Thorsten

see section 1.7 from the book (in preparation) "Modern Computer Arithmetic",
by Richard Brent and myself, version 0.1.1, November 2006,
http://www.loria.fr/~zimmerma/mca/mca-0.1.1.pdf. Exercise 1.9.21 shows that
the "print" routine (conversion from internal representation to string) can
be made asymptotically as fast as the "read" routine, including the constant
multiplier of the O(M(n) log(n)) complexity.

Paul Zimmermann