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.
$\begingroup$
$\endgroup$
10
-
2$\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$– TeepeemmCommented Mar 17, 2018 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_blackCommented Mar 18, 2018 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 1Commented Mar 19, 2018 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$– MartinVCommented Mar 19, 2018 at 17:08
-
4$\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$– ShreevatsaRCommented Mar 19, 2018 at 18:13
|
Show 5 more comments
7 Answers
$\begingroup$
$\endgroup$
29
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
answered Mar 17, 2018 at 20:24
-
17$\begingroup$ As long as we’re optimizing, since lg 1 = 0, you could start with 2. $\endgroup$– DavislorCommented Mar 17, 2018 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$ Commented Mar 18, 2018 at 9:10
-
4$\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$ Commented Mar 18, 2018 at 12:28
-
11$\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$ Commented Mar 18, 2018 at 14:09
-
5$\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$ Commented Mar 18, 2018 at 14:18
$\begingroup$
$\endgroup$
8
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$.
answered Mar 17, 2018 at 18:32
-
9$\begingroup$ It would be useful to have an error bound here. $\endgroup$ Commented Mar 18, 2018 at 1:24
-
-
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$– TobiaCommented Mar 18, 2018 at 21:17
-
$\begingroup$ @SolomonUcko As Tobia suggested, you can use the change of basis rule with ease. $\endgroup$ Commented Mar 18, 2018 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$– TobiaCommented Mar 19, 2018 at 8:52
$\begingroup$
$\endgroup$
6
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.
-
2$\begingroup$ Truly, Emacs is the only software you ever need. $\endgroup$– davidbakCommented Mar 19, 2018 at 4:43
-
4$\begingroup$ I feel editor envy. Can that not be done with vim?? $\endgroup$ Commented Mar 19, 2018 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$ Commented Mar 19, 2018 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 -lwill calculate and bring back into the editor:1683.99581759716152712952. Who needs emacs ... $\endgroup$ Commented Mar 19, 2018 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$ Commented Mar 20, 2018 at 1:16
$\begingroup$
$\endgroup$
1
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})$).
answered Mar 17, 2018 at 20:43
-
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$ Commented Mar 19, 2018 at 9:34
$\begingroup$
$\endgroup$
2
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.
-
$\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.6163andabs(log(gamma(-3.4))) ~ 1.1212can cause some severe headaches if hidden deeply in a large formula. $\endgroup$ Commented Mar 19, 2018 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$– CharlesCommented Mar 19, 2018 at 3:12
$\begingroup$
$\endgroup$
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. $$
answered Mar 21, 2018 at 0:47
$\begingroup$
$\endgroup$
1
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
-
2$\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$ Commented Mar 19, 2018 at 12:24