3
$\begingroup$

I have problem. I've calculated memory complexity of my algorithm. In exchange of very good time complexity of my algorithm, I have memory complexity $x!$, where $x$ is number of elements my algorithm gets.

Number of numbers I can easily store equals $2^{22000000}$. How many elements can my algorithm accept?

$x!=2^{22000000}$

How can I solve it? I've tried several calculators (even wolfram alpha), but no calculator was able to solve it. I've tried to use Stirling approximation ( Solving equations with factorials? ), but the number is just too big.

Do you know some online calculator that would be powerfull enough to calculate it? Or some other method to calculate it? I do not need exact number, I just want to know how big the number is (if I could tell number of digits in the number, it would be great).

Thanks, Peter

$\endgroup$
  • $\begingroup$ A crude approximation is $x! \approx (x/e)^x$. Solving for this gives: $$ (\frac{x}{e})^x = 2^{22000000} \implies x \ln (x) -x = 22000000 \ln(2) $$ Then using Wolfram Alpha gives you an approximation. Note also that taking first logarithm will help software to approximate the answer since it needs not to deal with extra huge number anymore. For example here. $\endgroup$ – Zubzub Nov 3 '17 at 9:19
  • $\begingroup$ If you look at math.stackexchange.com/questions/1333449/… , have a look at @robjohn's elegant solution for a similar problem. $\endgroup$ – Claude Leibovici Nov 3 '17 at 9:27
  • 1
    $\begingroup$ You can easily store $2^22000000$ numbers? May I ask what kind of hardware you're using for that? $\endgroup$ – Professor Vector Nov 3 '17 at 9:41
  • 1
    $\begingroup$ Take logarithms, use the loggamma and inverse loggamma function: $$\log x! = \log\Gamma(x+1)=22000000\log(2)$$ $$ x= \mathrm{loggamma}^{-1}(22000000\log(2))-1= 1175108.399864\dots$$ The inverse loggamma function can be computed e.g. with Newtons method. $\endgroup$ – gammatester Nov 3 '17 at 9:43
  • $\begingroup$ @Professor Vector I have a collection of numbers (like one row in excel full of numbers). But because of my algorithm structure, most of row will not be occupied, so I will physically store only few numbers (plus information which cells are occupied). $\endgroup$ – SoptikHa Nov 3 '17 at 9:59
4
$\begingroup$

In this answer is given the approximation $$ n\sim e\exp\left(\operatorname{W}\left(\frac1{e}\log\left(\frac{n!}{\sqrt{2\pi}}\right)\right)\right)-\frac12 $$ Plugging in $n!=2^{22000000}$, we get $n\approx1175108.4$. Then $$ 1175108!\approx2^{21999991.937} $$ and $$ 1175109!\approx2^{22000012.101} $$

$\endgroup$
  • $\begingroup$ In fact, if we use the Gamma function, we get $$1175108.4! =\Gamma(1175109.4) \approx2^{22000000.003}$$ $\endgroup$ – robjohn Nov 4 '17 at 14:19
  • $\begingroup$ For computing purposes, you probably want to use $\exp(W(x))=x/W(x)$ to avoid calculating $\exp$. $\endgroup$ – Simply Beautiful Art Jul 20 '18 at 13:28
2
$\begingroup$

A quick and dirty approximation.

Considering the function $\log_2(x!)$ for $10^3 \leq x \leq 10^6$ (by steps of $10^3$) and considering a totally empirical model $a+b x^c$, a non linear regression gave $$\begin{array}{clclclclc} \text{} & \text{Estimate} & \text{Standard Error} & \text{Confidence Interval} \\ a & -24230.2 & 415.912 & \{-25046,-23414\} \\ b & 6.22383 & 0.005670 & \{6.21271,6.23496\} \\ c & 1.07893 & 0.000065 & \{1.07880,1.07905\} \\ \end{array}$$ So, if $x!=2^k$, the solution will be $$x=0.183666 (k+24230.2)^{0.926847}$$ For $k=22 \times 10^6$, this would lead to $x=1.17429\times 10^6$ which is not too bad compared to gammatester's exact result.

Edit after robjohn's answer

Remembering that $z=W(z)\, e^{W(z)}$ and taking into account that equation $x!=2^k$ has to be solved for large values of $k$, we can make good approximations defining $$z=\frac{2k \log(2)-\log(2\pi)}{2e}\qquad L_1=\log(z)\qquad L_2=\log(L_1)$$ and use the truncated expansion given here to get $$x\approx \frac{e z} {L_1-L_2+\frac{L_2}{L_1}+\frac{L_2(L_2-2)}{2L_1^2}+\frac {L_2(6-9L_2+2L_2^2)}{6L_1^3}}-\frac 12$$ which, for $k=22 \times 10^6$, would lead to $x=1175102$. Adding the next terms of the given expansion would lead to more accurate values.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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