[
Date Prev][
Date Next][
Thread Prev][
Thread Next][
Date Index][
Thread Index]
Re: Binary-Decimal conversion for extremely large integers
Thorsten Siebenborn <7_born@xxxxxx> wrote:
I am talking about numbers with thousands or even millions of
binary digits.
I don't see the relevance to this mailing list, but still :-)
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.
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.
Grrk. That doesn't sound like a very good divide instruction.
It certainly USED to be dire, but that was ages ago. You might
try asking Terje Mathisen on comp.arch.arithmetic.
There are two approaches to fast division by powers of ten on most
systems using the word size. One is to divide by an appropriate
one and not faff around with shifts and adds, and the other is to
use multiplication - yes seriously! Especially if you have an
efficient single to double multiply, the latter is often a lot
faster (because multiply is often pipelines in ways that divide
is not).
I never programmed it carefully, but my experience is that well
designed iterative methods are often faster than exact ones. For
example, I could (MARGINALLY) beat Knuth's method for division by
not getting the result right on the first pass, and correcting.
I found the code a lot simpler, and easier to debug, too. I
think that you could do the same for conversion.
In cases like that, yes, a table helps - but you don't need a
massive one provided that your numbers are small enough that
keeping a table of a few is acceptable. You can use ones like
10^9, 10^36, 10^144, 10^576 and so on, though you need fancier
code.
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