### Using Kamenetsky's formula to count digits in a factorial

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

Surprisingly amazing.

ReplyDeleteI agree. The algorithm just stunned me.

ReplyDeleteDamn boi... way to go!

ReplyDeleteThank you so much!

ReplyDelete