Binary <-> Decimal Conversion

Icheb · #1 10-14-2002, 09:54 AM

At the moment I am trying to find a method which allows me to convert a large binary number (about 5 billion digits) into a decimal number extremely precise. The program language is not so relevant, it can be C or PHP or whatever possible.
I know there will a memory problem, but how can I calculate the amount of memory needed to store such a number?
And more important, does someone know of a method to convert such a number?

nexcess.net2 · #2 10-14-2002, 10:30 AM

Did you say 5 billion digits? That isn't a "large" number... That is a ridiculous number.

If it were a 1 followed by 5 billion zero's, it would be 2^(5 billion), which is close enough to infinity for me.

This sounds like one of those "get a guaranteed A in class if you solve this" problems. Well, guess what? Nobody every does.

That said, if my life depended on this problem, I would investigate using LISP. My only reason for saying that is I have a vague memory of reading about being able to generate crazy big numbers without sucking up memory with LISP. If I find where this memory is coming from I'll let you know. But don't count on it.

Good luck,
Paul

Icheb · #3 10-14-2002, 10:56 AM

Ok, I'll try to find something about LISP, thank you.

But how would you calculate the amount of memory needed to store and/or process such a large number?

wave · #4 10-14-2002, 05:43 PM

Its easy to calculate the memory needed to store a binary number. Suppose your binary number has 5 billion binary digits. So it will take at least 5 billion bits or 6.25E8 bytes to represent such a number.

To calculate how much memory is needed to store the decimal equivalent is slightly more complicated. It depends on how your numbers are represented. Say we want to represent decimal digits in C using char - typically it takes 1 byte per char. We'll keep the answer simple and only worry about unsigned integers. A x bit binary number can represent decimal values from 0 to 2^x - 1. We'll find the maximum memory we need to store a decimal number (say N) that is equivalent to a 5 billion bit binary number

2^(5E9) = N + 1
(5E9)log2 = log(N + 1)
10^(1.6E9) >= N

Thus N will have at most 1.6E9 + 1 digits. Since each digit is represented by a char, it will take 1.6E9 + 1 bytes or 1.6GB to store N. Unless you have lots of memory to work with you'll need to use your disk. It shouldn't be difficult to program since you're only converting a number to a different base.