How to handle very large numbers
I want to play around with factorials. I found that factorial(10**9)
takes about 20 minutes (on my machine, which is a Mac mini with 8GB Memory). Then I tried factorial(10**10)
and there I got this:
/Applications/...pathtoSageMath/sage/src/bin/sage-python: line 2: 975 Killed: 9 sage - python "$@"
Then I searched for a SageMath Stirling Formula, which I didn't find (only some related stuff), so I tried it myself:
sage: def s(n):
....: x=sqrt(2*pi*n)*((n/e)**n)
....: return x.numerical_approx()
....:
sage: s(5)
118.019167957590
sage: s(6)
710.078184642185
sage: s(10**10)
This gave me an error after some minutes:
RuntimeError
...
4047 relational_operator(self._gobj))
4048 else:
-> 4049 x = g_pow(self._gobj, nexp._gobj)
4050 return new_Expression_from_GEx(self._parent, x)
4051
RuntimeError: size of exponent exceeds signed long size
Then I tried s(10**9), there I got another error:
python3(755,0x10fbecdc0) malloc: can't allocate region
:*** mach_vm_map(size=18446744073151754240, flags: 100) failed (error code=3)
python3(755,0x10fbecdc0) malloc: *** set a breakpoint in malloc_error_break to debug
sig_error() without sig_on()
------------------------------------------------------------------------
(no backtrace available)
------------------------------------------------------------------------
Unhandled SIGABRT: An abort() occurred.
This probably occurred because a *compiled* module has a bug
in it and is not properly wrapped with sig_on(), sig_off().
Python will now terminate.
So what can I do? Is there a special library for very large reals or int or some special commands for getting an approximation of how many decimals a factorial will have? Could I use the log
somehow or would this have the same runtime problems?
The reason why I'm asking is that I am rewriting a text which is 20 years old and there's a statement that factorial(10**100)
could not be computed (ok, I believe that because of factorial being between O(2**n)
and O(2**(2**n))
) and factorial(10**8)
would take many hours, which was not the case on my machine (see above).
And last but not least I would like to know if there is an upper bound for numbers that sage can handle. I thought not, but now I know otherwise ;-) Also hints to good literature on these topics would be appreciated.
You are limited by
the size of your memory (real and swapfile), and, eventually, by
the size of addressable space.
Stirling's formula allows you to compute an approximation of $\log n!$ ; you probably have to devise an approximation of $\log\log n!$...