Is there a way to find the log of very large numbers?

Question

I should like to evaluate $\log_2{256!}$ or other large numbers to find 'bits' of information. For example, I'd need three bits of information to represent the seven days of the week since $\lceil \log_2{7}\rceil = 3$, but my calculator returns an error for large numbers.

Answer 1

If it's about factorials, you can use Stirling's approximation:

$$\ln(N!) \approx N\ln(N) - N$$

Due to the fact that

$$N! \approx \sqrt{2\pi N}\ N^N\ e^{-N}$$

Error Bound

Writing the "whole" Stirling series as

$$\ln(n!)\approx n\ln(n)−n+\frac{1}{2}\ln(2\pi n)+\frac{1}{12n} −\frac{1}{360n^3}+\frac{1}{1260n^5}+\ldots $$

it is known that the error in truncating the series is always the opposite sign and at most the same magnitude as the first omitted term. Due to Robbins, we can bound:

$$\sqrt{2\pi }n^{n+1/2}e^{-n} e^{\frac{1}{12n+1}} < n! < \sqrt{2\pi }n^{n+1/2} e^{−n} e^{1/12n}$$

More on Stirling Series in Base $2$

Let's develop the question of Stirling series when we have a base $2$ for example. The above approximation has to be read this way:

$$log_2(N!) \approx \log_2(\sqrt{2\pi N} N^N\ e^{-N})$$

Due to the fact that we have a non-natural log, it becomes

$$\log_2(N!) \approx \frac{1}{2}\log_2(2\pi N) + N\log_2(N) - N\log_2(e)$$

Hence one has to be very careful with the last term which is not $N$ anymore, but $N\log_2(e)$.

That being said one can proceed with the rest of Stirling series.

See the comments for numerical results.

Beauty Report

$$\color{red}{256\log_2(256) - 256\log_2(e) + \frac{1}{2}\log_2(2\pi\cdot 256) = 1683.9958175971615}$$

a very good accord with numerical evaluation (for example W. Mathematica) which gives $\log_2(256!) = 1683.9962872242145$.

Answer 2

By the laws of logarithms

$$ \log_2(256!) = \sum_{i=1}^{256} \log_2(i)$$

This is easily evaluated (albeit not on all calculators).

In Python:

>>> sum(math.log2(i) for i in range(1,257))
1683.9962872242136

Answer 3

Just a comment:

Of course, there are many calculators that can handle $\log_2 256!$ and much "worse" expressions directly. For example PARI/GP, if you type

log(256!)/log(2)

you will get a result like:

%1 = 1683.9962872242146194061476793149931595

(the number of digits can be configured with the default called realprecision).

If you want an exact integer logarithm, you can also use logint(256!, 2) which will give you 1683.

Typing 256! alone will give you the full 507-digit decimal expansion of this integer.

If PARI/GP is allowed to use memory (set parisizemax default), it will also immediately say that logint(654321!, 2) is 11697270.

---

As noted in comment, with reference to answer by Charles, if you want to work with floating-point operations (and not huge exact integers), you can use function lngamma which is equal to $\log\circ\Gamma$ for positive real arguments. Remember that compared to factorial, the Gamma function is shifted by one. So $$\log_2 n! = \frac{\log n!}{\log 2} = \frac{\log \Gamma(n+1)}{\log 2}$$ and you can type lngamma(654321 + 1)/log(2) in PARI/GP and everything will be floating point operations. This will work for astronomical values of $n$, for example lngamma(3.14e1000) is fine ($\log\Gamma(3.14\cdot 10^{1000})$).

Answer 4

In Emacs, C-x * * 256 ! 2 B N will readily deliver 1683.99628722 and of course you are free to increase the precision of your calculation. Stuff definitely is fast enough that there isn't much incentive for designing a solution outside of your editor.

Answer 5

Since this is a question about evaluating to get a result rather than understanding the method behind that result, the online computational knowledge engine WolframAlpha is always an option. A truly fantastic resource that gives the result to great accuracy almost instantly without the need for programming or even mathematical experience

Answer 6

As others have mentioned, your example is small enough to be computed directly with many systems. I should mention that many systems implement $$ \log\Gamma(x) $$ usually with names like lngamma or lgamma. You can then compute $$ \log_2(256!)=\frac{\log\Gamma(257)}{\log 2} $$ with minimal difficulty (and without leaving double precision).

In general some care is needed to work with the gamma function (branch cuts and numerical analysis), but in your case as long as you stick to factorials of numbers from 1 to 10³⁰⁵ or so you should be just fine with 64-bit doubles.

Answer 7

If the number is not a factorial but rather any large number then a cutest way would be to consider the fundamental theorem of number theory.

says for any integer $n$ we have $$n =\prod p_i^{a_i}$$ where p_i's are prime numbers. then by the law of log you get $$\log n= \sum a_i\log p_i. $$