12
$\begingroup$

I was going to ask this on Stack Overflow, but finally decided this was more math than programming. I may still turn out to be wrong about that, but...

Given a number represented in binary, it's fairly easy to derive a decimal representation using integer division and remainders to extract digits in reverse order. You can then simply count how many digits you extracted.

However, I wondered about calculating an exact number of decimal digits more efficiently by avoiding calculating the actual digits.

At first sight this is easy. First, count the binary digits needed (ie determine the position of the highest set bit). Many processors have an operation to do this directly, and there are bit-fiddling algorithms to do it in O(log n) time where n varies with the width of a machine register. In an arbitrary position integer, you normally know how many machine words you have, so you can usually jump directly to the most significant word.

Once you know the size in binary digits, you can scale by $\log 2 \over \log 10$ to get the number of decimal digits. Sort of.

The problem is that this scale factor is (I think) an irrational number. If you have a maximum number of digits you need to worry about, you can use a rational approximation and you only need to worry about getting the rounding right.

The question is, therefore - is there a way to determine this number of decimal digits efficiently and precisely for numbers of any size? Is there (for example) a completely different approach to the calculation that I haven't thought of?

$\endgroup$
3
  • 1
    $\begingroup$ You can't get away without using logarithms, I think; it is a fact that an integer $n$ has $\lfloor 1+\log_b\;n\rfloor$ base-$b$ digits. $\endgroup$
    – J. M. ain't a mathematician
    Sep 4, 2010 at 0:32
  • 10
    $\begingroup$ Just to confirm this for you: log(2)/log(10) is irrational. The proof is simple: clearly log(2)/log(10) is positive. So assume it's a positive rational number, i. e. that log(2)/log(10) = p/q where p and q are nonzero positive integers. Then you have p log 10 = q log 2. Exponentiating both sizes, 10^p = 2^q. But 10^p is divisible by 5 and 2^q isn't. $\endgroup$
    – Michael Lugo
    Sep 5, 2010 at 17:30
  • $\begingroup$ @Michael - nice proof. $\endgroup$
    – user510
    Sep 7, 2010 at 1:20

2 Answers 2

Reset to default
10
$\begingroup$

I would post this as a comment if I could, because it seems too simple for an answer. You already said that you can find the highest bit with a single instruction (if the number fits into a register). For every result $r$ you get (that is, your number is between $2^r$ and $2^{r+1}-1$), there are only two possible numbers $k$ and $k+1$ of decimal digits. So you could just use $r$ as an index into a lookup table that stores both $k$ and $10^k$, and output $k$ if your number is less than $10^k$, or $k+1$ otherwise.

$\endgroup$
3
  • $\begingroup$ +1, but the question he should answer now is "how big are the numbers you'll be seeing?" which would determine the size of his lookup table. $\endgroup$
    – J. M. ain't a mathematician
    Sep 5, 2010 at 22:06
  • $\begingroup$ Good enough to accept rather than my own answer - but this is a thought experiment rather than a practical exercise, and I can think of some very big numbers. Big enough that (using a rational approximation of log(2)/log(10)) I can be out by an unbounded number of decimal digits. For example, on a 64-bit machine with lots of memory, it wouldn't be that hard to have a very big integer that takes up, ooo, lets say 16GB of memory. It may not be useful, but it's possible. $\endgroup$
    – user510
    Sep 7, 2010 at 1:17
  • $\begingroup$ OK, in that case, a variation of the approach you suggested seems more appropriate (my suggestion is O(r) in time but O(r^2) in space). I would make two modifications: Instead of repeatedly dividing your number, just check which of 10^1, 10^2, 10^4, etc. exceed your number (maybe using binary search, depending on the distribution of inputs). If, say, 10^8 does but 10^4 does not, calculate 10^4*10^2 (both of which you have in store) and check again, then either 10^4*10^1 or (10^4*10^2)*10^1. Seems to be O(r*log(r)) in both time and space, but I didn't check thoroughly. $\endgroup$
    – Sebastian Reichelt
    Sep 7, 2010 at 16:54
1
$\begingroup$

With no better answer, I'll just add a little to what I said in the question to get this closed.

There are series calculations for logarithms (http://en.wikipedia.org/wiki/Logarithm) so I could in principle calculate the base 10 log directly. This would be awkward and slow, though, as for arbitrary precision integers a machine float/double isn't precise enough. I'd probably need a rational library, and the rationals involved wouldn't be simple.

It may be possible to use an imprecise base-converting factor. With an underestimate factor, you'd get an underestimate log value. Divide through by 10^x for that log value, then repeat as often as necessary to top up your underestimate.

The problem is that dividing through by 10^x isn't trivial unless you happen to be working in base 10.

Probably best to stick with repeated division by 10 - or powers of 10, at least. Constructing a list of powers (10^1, 10^2, 10^4, 10^8 and so on) by squaring wouldn't be too hard. Stop when you exceed the target number, then do the divisions largest to smallest. Each power should only need to be considered once.

Even then, it may be better to not build powers of 10 that won't fit in a machine word, and just do repeated division by (small powers of) 10.

Also, this sounds now more like programming than math, so sorry about that.

$\endgroup$
1
  • $\begingroup$ This uses an algorithm similar to your base converting factor idea. Probably most effective with very large numbers when a lookup table would be unfeasable. $\endgroup$
    – OldCurmudgeon
    Sep 18, 2013 at 13:54

You must log in to answer this question.