Fast Binary-to-Decimal Conversion Algorithms?

From: Simon G Best (s.g.best_at_btopenworld.com)
Date: 07/31/04 

Date: Sat, 31 Jul 2004 00:55:28 +0000 (UTC)

Hello!

Without much success, I've been trying to find a 'fast' algorithm for
converting large numbers from binary to decimal. By 'fast', I mean
something like O(N log(N)). By 'large', I mean billions of bits. Oh,
and I'd like a similarly fast algorithm for converting back from decimal
to binary, too, please. Oh, and yes, I'd like fries with that :-)

O(N^2) algorithms are obvious, and I've had no trouble finding those on
the web (not that I need to look them up).

I've also been informed of what seems to be a faster algorithm by
Christian Bau in sci.math. It's a way of using an n-bit-to-m-digit
converter in a 2n-bit-to-2m-digit converter. It works as follows.

To convert a 2n bit binary number, x, into a 2m digit decimal number,
split x into two, n bit binary numbers, y and z, such that x = (2^n)y +
z. Convert 2^n, y and z into decimal (using the n-bit-to-m-digit
converter), and then calculate x in decimal. This technique can
obviously be applied recursively for 4n bit numbers, 8n bit numbers, 16n
bit numbers, and so on.

Is there a faster algorithm? Where might I be able to find the kinds of
speedy algorithms I'm looking for? Where might I be able to find some
useful pointers? Which newsgroup should I really be asking this in?

Thanks!

Simon

Relevant Pages

  • Fast Binary-to-Decimal Conversion Algorithms?
    ... and I'd like a similarly fast algorithm for converting back from decimal ... I've also been informed of what seems to be a faster algorithm by ... It's a way of using an n-bit-to-m-digit ... converter in a 2n-bit-to-2m-digit converter. ...
    (comp.theory)
  • Re: off-topic: Why is lisp so weird?
    ... I'm not arguing against finding a better algorithm. ... >> advantage to be had by running in a more efficient environment. ... some languages can optimize code better. ... actually be faster than a faster algorithm in a different language. ...
    (comp.programming)
  • Re: New and faster algorithm for multiplication
    ... Hans Petter Selasky wrote: ... > I think I have found a new and faster algorithm for multiplication. ... Prev by Date: ...
    (comp.arch.arithmetic)
  • Re: Fast Binary-to-Decimal Conversion Algorithms?
    ... >Without much success, I've been trying to find a 'fast' algorithm for ... >converting large numbers from binary to decimal. ... >and I'd like a similarly fast algorithm for converting back from decimal ... >I've also been informed of what seems to be a faster algorithm by ...
    (comp.programming)