February 15th, 2002, 07:10 PM

bits needed to represent a 100 digit decimal
Hi All,
I realise that this is a newbie question but i do need help on this. We r trying to code a program to find out no of bits needed (binary) to represent a 100 digit decimal number. Could one approach be to find the log of the decimal no and add 1 to it?
Thanks in advance
DA
February 16th, 2002, 05:58 AM

ceil(log(you_number)) would give you the number of bits needed. e.g. ceil(log(1025)) is 4.

Regards
André Nęss
Puritanism: The haunting fear that someone, somewhere may be having fun
February 16th, 2002, 02:01 PM

The minimum # of bits is 329 and max # of bits is 333
You don't need a computer to figure this out  pen, paper and a copy of Clark's Log tables is all you need (ok, you can cheat and use a calculator instead if you like).
First let's see if I can remember the terminology correctly (it's been a long while since 8th grade):
Theorem 1:
Let's say log(x) = 3.1256, then the part before the decimal point is called the characteristic and the part after the decimal point is called the mantissa. In this case, the characteristic is 3 and the mantissa is .1256. So antilog(3.1256) will have 4 digits before the decimal point (characteristic + 1). In general if log(x) = m.pqrs, then antilog(m.pqrs) will have m+1 digits before the decimal point.
Theorem 2:
If a = b^c, then log(a) = c * log(b)
Now onto the problem at hand. We need to find x, such that 2^x has 100 digits or more. Let's call this number y.
==> y = 2^x
Now from theorem 2, we have
log(y) = x * log(2)
From theorem 1, we can see that for the number to have 100 digits or more, log(y) should be >= 99. Therefore we have
x * log(2) >= 99
==> x >= 99/log(2)
From the top of my head, log(2) is 0.3010 approximately. Use a calculator if you want a more accurate value. Anyways, doing the math, we get
==> x >= 328.87
The nearest integer value of x is 329, which is the answer you're looking for. If you want to verify this, all you need to do is compute 329 * log(2) which comes out to 99.038 approx., which means that antilog(99.038) will have 100 digits.
Note that this is the minimum # of bits required to represent a number of 100 digits. You can use the same logic to find the max # of bits. (Hint: Find the min # of bits to represent a number with 101 digits!). I'll save you the math and tell you that the answer is 333.
So, the smallest # of bits required to represent a 100 digit decimal number is 329 and the # of bits required to represent any 100 digit # is 333. If you're looking to represent any 100 digit number, then your answer should be 333 bits. Quat Erat Demonstrandum!
Hope this helps!
Last edited by Scorpions4ever; February 16th, 2002 at 02:53 PM.
February 17th, 2002, 01:42 AM

Why do all that when you can use one line of code.
February 17th, 2002, 03:12 AM

Well, this is an algorithms forum and I figured I might as well add the logic behind andaness's one liner.
February 17th, 2002, 08:48 AM

Originally posted by JeffCT
Why do all that when you can use one line of code.
What's "all that"? Scorpions4ever boiled it all down to (num_digits  1)/log(2) which is a much better solution than mine because there's no need for arbitrary precision mathematics. He also did a good job of explaining how he landed at this simple calculation by way of simple mathematical theorems, thus proving the correctness of his solution.
The one line of code you end up with is ceil((num_digits  1) / log(2)). A *lot* better than my solution.
I just noticed something peculiar, the PHP function log() is actually the natural logarithm... Isn't this normally named ln()? In all mathematics and CS course I've taken log is base 2 logarithm, ln is the natural, and any other logarithm is written as log with the base in subscript. Strange.

Regards
André Nęss
Puritanism: The haunting fear that someone, somewhere may be having fun
February 17th, 2002, 11:59 AM

and Andaness did an excellent job of describing what my explanation boils down to
Regarding the log() function returning ln(), I haven't seen a single language that DOESN'T do that. It confused me the first time I programmed in GWBASIC, because I was taught to represent the natural log as ln() and common log as log() in school too.
Some languages (including PHP, Perl and C) have a log10() function which returns the common log rather than the natural logarithm. This is the function that should be used in the one liner if you're actually going to write some code, so I'll amend the expression to:
bits = ceil((num_digits 1)/log10(2))
March 29th, 2002, 12:40 PM

thanks
Hi,
Thank you all for replying to my question. It really helped.
DA