Predicting Number of Decimal Digits in a Binary Number

Date: 03/10/2004 at 11:52:00
From: R.B.
Subject: Number of decimal digits from binary number

I am trying to write a function that will return the number of decimal 
digits from a binary number without actually converting from binary to 
decimal.  Here is what I have so far:

let d = number of digits
d = floor of [(bits - 1)*log2] + 1

However, if (bits - 1)mod 10 = 3,6,or 9 then the number of digits 
could be:

 [(bits - 1)*log2] + 1  OR  [(bits - 1)*log2] + 2

Say, for instance, the binary number has 4 bits.  In decimal that 
number ranges from 8-15...1 or 2 digits.  Is there a way to determine 
which length is correct without going through a complete conversion? 

Date: 03/10/2004 at 12:53:15
From: Doctor Douglas
Subject: Re: Number of decimal digits from binary number

Hi R.B.

Thanks for writing to the Math Forum.  I don't think that there
is a way to do this with a single formula.  For example, consider
the two numbers

  1111100111 binary  =   999 decimal
  1111101000 binary  =  1000 decimal

If you are going to distinguish the fact that one of these numbers
gives rise to 3 decimal digits and the other gives rise to 4 decimal
digits, you will need to get into the last four digits in the binary
expansion--you will need to parse at least the first seven digits
of the binary input.

To be efficient, as you've realized, you need to implement the direct 
conversion only when there is a danger of crossing from k decimal 
digits to k + 1 decimal digits (e.g. 999 to 1000).  This is almost, 
but not quite, identical to your rule using the mod function.  I think 
the smallest number of binary digits for which this differs is 102 
bits:

  2^103 = 1.01412E+31 has 32 decimal digits
 
Thus a 102 bit number could have either 31 or 32 decimal digits.

- Doctor Douglas, The Math Forum
  http://mathforum.org/dr.math/