Re: Binary-Decimal conversion for extremely large integers

[Nick Maclaren <nmm1@xxxxxxxxxxxxx>]

Thorsten Siebenborn <7_born@xxxxxx> wrote:
> 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.

Well, you can do better than THAT.  You can extract an arbitrary
number of digits in one go - with traditional 32-bit integers,
nine at once is normal.

> 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.

I have never seen anything published, but my suspicion is that
you can't do more than a constant factor better.  I tried to
think of how to use one of the standard multiplication or
division tricks to improve the order, and failed.


Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QH, England.
Email:  nmm1@xxxxxxxxx
Tel.:  +44 1223 334761    Fax:  +44 1223 334679