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
:confused:
ceil(log(you_number)) would give you the number of bits needed. e.g. ceil(log(1025)) is 4.
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!
Why do all that when you can use one line of code.
Well, this is an algorithms forum and I figured I might as well add the logic behind andaness's one liner.
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.
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 GW-BASIC, 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))
Hi,
Thank you all for replying to my question. It really helped.