Re: Binary-Decimal conversion for extremely large integers

[Thorsten Siebenborn <7_born@xxxxxx>]

Nick Maclaren schrieb:
> 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.

Thanks for the answer.

I am talking about numbers with thousands or even millions of
binary digits.
The fast, but memory-consuming method is building a lookup-table
for division by subtraction with 1,2,4,8,10,20,40,80 etc.
The obvious drawback is the growing table size; even if you have
enough hard disk space, parts of your conversion table must be
loaded into memory which slows down conversion. While I himself
will use it for numbers with fewer digits, it is not advisable for
really big numbers.

If you try to extract several digits at once, it means AFAIK that you
are thinking of using 1,10^9,10^18,10^27 etc. as divisors.
As 10 = 2*5 is coprime to binary numbers, it is increasingly
difficult to simulate greater divisors with fast add/shift algorithms.

But if you use long division, the division must be splitted
into several chunks and the algorithm must correct the bits
accordingly which in fact is prohibitively expensive.
So expensive that in fact nine runs of my algorithm is still faster
than one run with long division; the longer the number, the better
the add/shift algorithm.

Best,
Thorsten