Using Kamenetsky's formula to count digits in a factorial

We need to count the number of digits in \(N!\). We can do that by first calculating the \(N!\), and then counting the number of digits. As we know the value of \(N!\) can be very large so it would cause an overflow if we even try to store it in a unsigned long long variable.

So what to do now? We can use the property of logarithms.

We know that, \(log(ab) = log(a)+log(b)\)
\(\therefore log(n!) = log(1*2*3...* n)\)
\(= log(1)+log(2)+...+log(n)\)

The floor value of log base 10 increased by 1, of any number, gives the number of digits present in that number.

Hence, \(floor(log_{10}(n!)) + 1\)

Here is the code for it:


The time complexity of the above code is \(O(n)\). We can further optimize it using Kamenetsky's formula. Using this formula, we can count digits in a factorial for extremely large values of N.

It approximates the number of digits in a factorial by :
\(f(n) = \log_{10}( (n/e)^{n} \sqrt{2 \pi n})\)

After applying the property of logarithms we get,
\(f(n) = n log_{10}(n/e)+\dfrac{log_{10}(2 \pi n)}{2}\)

Here is the code:


The time complexity of the above code is \(O(1)\).

Voila! We're done. It's now time for some quote reading:

“The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct.” ― Donald E. Knuth, Selected Papers on Computer Science



Comments

Post a Comment