28
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ There's an important distinction between $\log_2 256!$ and $\lceil\log_2 256!\rceil$. If you only need an approximation, then Stirling is the way to go. If you need the actual value, then computers are more helpful (although there are refinements to Stirling). $\endgroup$ – Teepeemm Mar 17 '18 at 22:24
  • 14
    $\begingroup$ Your title is poor English (despite the fact you rejected an improvement to it). "Is there a (simple) way" would be better. $\endgroup$ – matt_black Mar 18 '18 at 19:19
  • 3
    $\begingroup$ It was fine as it was originally. In any case, 'improvement' is an opinion and 'simple' would be presumptions. Let's stick to the mathematics. $\endgroup$ – Red Book 1 Mar 19 '18 at 0:44
  • 2
    $\begingroup$ Nope - "I should like" is fine. It's rather old-fashioned and perhaps more common in the UK ... e.g. english.stackexchange.com/questions/19438/… $\endgroup$ – MartinV Mar 19 '18 at 17:08
  • 3
    $\begingroup$ @RedBook1 “Is there are way” is not grammatical. You probably meant either “Is there a way” or “Is there any way”. (Many of the other changes that people tried making to your question seem unnecessary though.) $\endgroup$ – ShreevatsaR Mar 19 '18 at 18:13
62
$\begingroup$

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$.

$\endgroup$
  • 9
    $\begingroup$ It would be useful to have an error bound here. $\endgroup$ – Paŭlo Ebermann Mar 18 '18 at 1:24
  • $\begingroup$ How about $log_2{n!}$? $\endgroup$ – Solomon Ucko Mar 18 '18 at 20:38
  • 8
    $\begingroup$ @SolomonUcko you can use the laws of logarithms: $$ \log_2 n! = { \ln n! \over \ln 2 } \approx { n \cdot \ln n - n \over \ln 2 } $$ $\endgroup$ – Tobia Mar 18 '18 at 21:17
  • $\begingroup$ @SolomonUcko As Tobia suggested, you can use the change of basis rule with ease. $\endgroup$ – Von Neumann Mar 18 '18 at 21:20
  • 3
    $\begingroup$ @SolomonUcko Yes, it can convert from any base. The mnemonic rule is that the base is traditionally written below the word "log", so it goes on the bottom when you convert it to a fraction: $$ \log_{base} arg = { \log_x arg \over \log_x base } $$ and this is true for any $x$ (if the log exists, etc.) $\endgroup$ – Tobia Mar 19 '18 at 8:52
113
$\begingroup$

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
$\endgroup$
  • 15
    $\begingroup$ As long as we’re optimizing, since lg 1 = 0, you could start with 2. $\endgroup$ – Davislor Mar 17 '18 at 23:20
  • 3
    $\begingroup$ (Hmm computer experimentation doesn't seem to bear out my previous comment. Probably because of the division; need to look deeper… anyway, floating-point issues from adding up many terms is something to take into account, as note that for $n = 256$, the correct value is $1683.9962872242146…$ while the above from adding up the logs seems to give $1683.9962872242136$ which is an error at 12th decimal place. Probably not a big deal yet.) $\endgroup$ – ShreevatsaR Mar 18 '18 at 9:10
  • 3
    $\begingroup$ @ShreevatsaR As a rough rule of thumb, the error in adding up 256 floats of roughly the same magnitude should be around 256*(machine_epsilon) which would be (for 64 bit floats) $256*2^{-52} \approx 2.7 \times 10^{-14}$. Your calculation suggests that the error is slightly worse than that (probably since the numerical method to approximate logs has its own error). It is an interesting question of how large $N$ needs to be for round-off errors make the calculation worthless. $\endgroup$ – John Coleman Mar 18 '18 at 12:28
  • 10
    $\begingroup$ The error of adding floating point numbers depends on the order and magnitude differenence. In this calculation it's added from smallest to biggest. If you turned the range around, then the result would be a lot more unprecise. $\endgroup$ – HopefullyHelpful Mar 18 '18 at 14:09
  • 4
    $\begingroup$ @HopefullyHelpful That is why I stipulated that the numbers being added all be of roughly the same magnitude. sum(math.log2(x) for x in range(256,0,-1)) agrees with the original calculation out to 11 decimal places, so I wouldn't characterize it as "a lot" more imprecise. $\endgroup$ – John Coleman Mar 18 '18 at 14:18
11
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Truly, Emacs is the only software you ever need. $\endgroup$ – davidbak Mar 19 '18 at 4:43
  • 4
    $\begingroup$ I feel editor envy. Can that not be done with vim?? $\endgroup$ – Peter - Reinstate Monica Mar 19 '18 at 12:55
  • $\begingroup$ @PeterA.Schneider Sure, it could be done with Vim, someone would just have to re-implement Emacs Calc, which is a pretty large piece of software by itself, in Vim. I suspect it was easier to implement in Emacs Lisp than it would be in Vimscript, though. :-) $\endgroup$ – ShreevatsaR Mar 19 '18 at 19:23
  • $\begingroup$ @PeterA.Schneider you can run commands or other programs, like bc, from inside vi (and I suppose Vim). For example: :r ! echo "( l(8*a(1))/2 + (256+1/2)*(l(256)-1) + 1/2 ) / l(2)" | bc -l will calculate and bring back into the editor: 1683.99581759716152712952. Who needs emacs ... $\endgroup$ – ypercubeᵀᴹ Mar 19 '18 at 20:19
  • 1
    $\begingroup$ @PeterA.Schneider Sure, if Vim is compiled with the +python option you can do it with ":from math import *" followed by ":py print log(factorial(256))/log(2)" Much more readable than Emacs :P $\endgroup$ – Paul Evans Mar 20 '18 at 1:16
11
$\begingroup$

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})$).

$\endgroup$
  • 1
    $\begingroup$ The excellent PARI/gp implements too the much faster lngamma function (proposed by Charles) and lngamma(N+1)/log(2) should reduce the possibility of overflows for $N\gg 1$. $\endgroup$ – Raymond Manzoni Mar 19 '18 at 9:34
6
$\begingroup$

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 10305 or so you should be just fine with 64-bit doubles.

$\endgroup$
  • $\begingroup$ Although only the positive integers are relevant for the question it should be noted that $\log(\Gamma(x)) \not= \log\Gamma(x)$ in several common multiprecision programs. (For details see e.g.: D. E. G. Hare's "Computing the Principal Branch of log-Gamma". ) This might also be the case for "normal" (double precision) calculators if they support complex numbers, so a bit of caution is advised. For example the difference between abs(lngamma(-3.4)) ~ 12.6163 and abs(log(gamma(-3.4))) ~ 1.1212 can cause some severe headaches if hidden deeply in a large formula. $\endgroup$ – deamentiaemundi Mar 19 '18 at 3:04
  • $\begingroup$ @deamentiaemundi Yes, good advice for the general case. When working with positive integers it should not matter. I'll edit in some general remarks. $\endgroup$ – Charles Mar 19 '18 at 3:12
3
$\begingroup$

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

enter image description here

$\endgroup$
  • 1
    $\begingroup$ If you're using Alpha (or Mathematica for that matter), you can use LogGamma[256 + 1]/Log[2] instead of separately computing the factorial before taking the logarithm. $\endgroup$ – J. M. is a poor mathematician Mar 19 '18 at 12:24
2
$\begingroup$

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. $$

$\endgroup$

protected by Von Neumann Mar 19 '18 at 17:45

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.