Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
February 15th, 2002, 07:10 PM
 darkangel
Registered User

Join Date: Feb 2002
Location: USA
Posts: 12
Time spent in forums: < 1 sec
Reputation Power: 0
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?

DA

#2
February 16th, 2002, 05:58 AM
 andnaess
Contributing User

Join Date: Jul 2001
Location: Oslo
Posts: 1,516
Time spent in forums: < 1 sec
Reputation Power: 14
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

#3
February 16th, 2002, 02:01 PM
 Scorpions4ever
Banned ;)

Join Date: Nov 2001
Location: Woodland Hills, Los Angeles County, California, USA
Posts: 9,535
Time spent in forums: 2 Months 3 Days 5 h 27 m 30 sec
Reputation Power: 4106
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.

#4
February 17th, 2002, 01:42 AM
 JeffCT
Dev

Join Date: Jan 2001
Posts: 1,436
Time spent in forums: 5 h 52 m 59 sec
Reputation Power: 40
Why do all that when you can use one line of code.

#5
February 17th, 2002, 03:12 AM
 Scorpions4ever
Banned ;)

Join Date: Nov 2001
Location: Woodland Hills, Los Angeles County, California, USA
Posts: 9,535
Time spent in forums: 2 Months 3 Days 5 h 27 m 30 sec
Reputation Power: 4106
Well, this is an algorithms forum and I figured I might as well add the logic behind andaness's one liner.

#6
February 17th, 2002, 08:48 AM
 andnaess
Contributing User

Join Date: Jul 2001
Location: Oslo
Posts: 1,516
Time spent in forums: < 1 sec
Reputation Power: 14
Quote:
 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.

#7
February 17th, 2002, 11:59 AM
 Scorpions4ever
Banned ;)

Join Date: Nov 2001
Location: Woodland Hills, Los Angeles County, California, USA
Posts: 9,535
Time spent in forums: 2 Months 3 Days 5 h 27 m 30 sec
Reputation Power: 4106
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))

#8
March 29th, 2002, 12:40 PM
 darkangel
Registered User

Join Date: Feb 2002
Location: USA
Posts: 12
Time spent in forums: < 1 sec
Reputation Power: 0
thanks

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

DA

 Viewing: Dev Shed Forums > Programming Languages - More > Software Design > bits needed to represent a 100 digit decimal