#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2002
    Location
    USA
    Posts
    12
    Rep Power
    0

    Question 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
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jul 2001
    Location
    Oslo
    Posts
    1,516
    Rep Power
    15
    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
  4. #3
  5. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,642
    Rep Power
    4247

    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 01:53 PM.
  6. #4
  7. No Profile Picture
    Dev
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Jan 2001
    Posts
    1,436
    Rep Power
    41
    Why do all that when you can use one line of code.
  8. #5
  9. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,642
    Rep Power
    4247
    Well, this is an algorithms forum and I figured I might as well add the logic behind andaness's one liner.
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jul 2001
    Location
    Oslo
    Posts
    1,516
    Rep Power
    15
    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
  12. #7
  13. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,642
    Rep Power
    4247
    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))
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2002
    Location
    USA
    Posts
    12
    Rep Power
    0

    Talking thanks


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

    DA

IMN logo majestic logo threadwatch logo seochat tools logo