Number of digits in a number?

Buri

I was playing around with my calculator and I noticed that to calculate the number of digits in a number n we have # of digits in n = [log(n) + 1], where log is in base 10 and [] represents the floor function. I after looked this up and it seems like its true. But how would you go about proving something like this? I thought of writing n as its decimal expansion, and then taking the logarithm, but it doesn't seem to get me no where. Any ideas?

micromass

Let x be a number, then it is easy to see that

x has n digits if and only if [tex]10^{n-1}\leq x<10^{n}[/tex].

If we apply your expression on this, then we obtain

[tex]n=\log(10^{n-1})+1\leq \log(x)+1<\log(10^n)+1=n+1[/tex]

This yields that [tex][\log(x)+1]=n[/tex].

HallsofIvy

A number, n, has "d" digits if and only if [itex]10^{d-1}\le n< 10^d[/itex]. Take the logarithm (base 10) of each part of that, using the fact that logarithm is an increasing function.

Buri

Ahhh didn't think of that. Thanks a lot to both of you! :)

Robert1986

Note that this can be generalized to any base b system. In particular, the number of bits needed to represent a number in base 2 is the log of that number to the base 2. This is really important in the analysis of algorithms.

Buri

Funny how you actually mentioned algorithms. I actually got into this problem by looking at the efficiency of the Euclidean Algorithm. I was trying to show that when the Euclidean Algorithm is applied to a and b (a > b) that it terminates in at most 7 times the number of digits of b.