Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
If $a$ and $b$ are positive integer then what is length of digits of $a^b$?
I have worked so far and formula works fine.
To find the exact length of digits of $a^b$ where $a\gt 0, b\gt 0$:
Number of Digits are = $\lfloor 1+b\ log(a) \rfloor$
Either it is true of any positive integers $a$ and $b$ or it's accuracy is limited?
Tell me if is there any other method to find the number of digits of $a^b$?
The logarithmic formula is accurate. The base of the logarithm is the base of the number system you're using. Why it works? Consider the limiting cases. The smallest number with $n$ digits in base $B$ is
$$B^{n-1}$$ The largest number with $n$ digits is $$B^{n}-1$$ Taking the logarithm, you get
$$1+\log_B B^{n-1}=n$$ $$1+\log_B (B^n-1)<1+\log_B (B^n)=1+n$$ so because of the inequality, the floor of this is still $n$.
If it works correctly for the limiting cases, it works for all numbers (except for 0 and negatives): $$\lfloor 1 + \log_B x \rfloor$$
That's a mathematically exact result. But in finite arithmetic (logarithm computed numerically) you may run into problems. There are two potential problems here, both at the cases when the number changes:
If the log is only slightly smaller than its true value, it you may get $\log_{10} 10^n=n-\epsilon$ which will get rounded down (it may say 1000 has 3 digits).
For large enough numbers, the number of places computed may not even be large enough. That's not that dangerous if you're computing $\log x$ with integer range $x$, but if $a^b$ is enormous and over the range of double precision, and you're computing it like this: $\log a^b = b\log a$, the $b$ factor may blow up the number enough to run out of correct digits.
Let's see how much precision we actually need:
$$\log_B (x+1)=\log_B (x(1+1/x))\approx \log_B x + \frac{1}{x\ln B}$$ This means that for consecutive numbers, their logarithms (you probably have $B=10$) will differ only by around $\frac{1}{x\ln B}$. So if you're concerned about underestimating the corner case, you may add less than about half of this amount to ensure that the floor function will give you the right integer, but you wont accidentally say 999 has 4 digits. In this respect, this may be safer: $$\lfloor 1 + \log_B x + 0.5/(x\ln B) \rfloor$$
What about the issue (2)? Well, let's see how much precision we need for $x=a^b$ if $\log_B a$ is only accurate $\pm \epsilon$. $$\log_{B}x\approx b \log_B a \pm b\epsilon+\frac{1}{a^b\ln B}$$ we want to see what's the relative precision needed for the log (number of binary digits of double precision is 52).
Requirement for correct result: $$\frac{\epsilon}{\log_B a} < \frac{1}{b a^b \ln a}$$
Condition for $a$ and $b$ for this to work in double precision: $$-\log_2 \frac{\epsilon}{\log_B a}=\log_2 b + b\log_2 a+\log_2(\ln a)<52$$ The last term makes no difference. But the second one tells you that if $b$ times the binary length of $a$ is over 52, you'll get mistakes for numbers where the number of digits changes. What this actually tells you that you don't benefit much by not computing $x=a^b$ out right. The basic limit of the computation is the same - put in $b=1$ and you retrieve (taking into account that the worst case $x=2^{64}$ in the last term), $$\log_2 x<47$$ Which tells you that not even 64-bit integers can be measured correctly in length! Try with $10^{15}$, it gets it wrong.
