Ask Your Question
0

How to handle very large numbers

asked 2020-09-03 07:23:29 +0100

dantetante gravatar image

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.

edit retag flag offensive close merge delete

Comments

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

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2020-09-03 08:41:38 +0100 )edit

2 Answers

Sort by ยป oldest newest most voted
2

answered 2020-09-04 12:36:10 +0100

vdelecroix gravatar image

Just avoid the symbolic ring

sage: e_float = e.n() 
sage: pi_float = pi.n() 
sage: def s(n): 
....:     x=sqrt(2*pi_float*n)*((n/e_float)**n) 
....:     return x.numerical_approx()                                                                                                                                                                               
sage: s(10**10)                                                                                                                                                                                                     
2.32579597597705e95657055186
edit flag offensive delete link more
0

answered 2024-12-13 14:15:13 +0100

I came across a similar error in the version of Sage 10.4 while computing

(1 - x^38)^9223372036854775808

It "feels" similare because the line of code which generates the error is the same (x = g_pow(self._gobj, nexp._gobj)). While the RuntimeError I get seems now undocumented (no description after "RuntimeError:"), the fact that 9223372036854775808 is 2^63 calls for a signed long size error.

I read the comment about the size of memory involved, and I think it is not the case: it really seems that the library sage is using relies on signed long, rather than switching to arbitrary large integers.

Is there something which can be done to bypass this limitation while using the same library of Sage? (or some other way within Sage to succeed in this computation?)

Thank you very much for your help.


This is the error I get:

    RuntimeError                              Traceback (most recent call last)
Cell In[1], line 1
----> 1 (Integer(1) - x**Integer(38))**Integer(9989690752182277136)

File /ext/sage/10.4/src/sage/structure/element.pyx:2058, in sage.structure.element.Element.__pow__()
   2056     return (<Element>left)._pow_(right)
   2057 if BOTH_ARE_ELEMENT(cl):
-> 2058     return coercion_model.bin_op(left, right, pow)
   2059 
   2060 cdef long value

File /ext/sage/10.4/src/sage/structure/coerce.pyx:1228, in sage.structure.coerce.CoercionModel.bin_op()
   1226         return (<Action>action)._act_(x, y)
   1227     else:
-> 1228         return (<Action>action)._act_(y, x)
   1229 
   1230 # Now coerce to a common parent and do the operation there

File /ext/sage/10.4/src/sage/structure/coerce_actions.pyx:931, in sage.structure.coerce_actions.IntegerPowAction._act_()
    929     if not err:
    930         return e._pow_long(value)
--> 931     return e._pow_int(n)
    932 
    933 def _repr_name_(self):

File /ext/sage/10.4/src/sage/symbolic/expression.pyx:4530, in sage.symbolic.expression.Expression._pow_int()
   4528         pi^4
   4529     """
-> 4530     return self._pow_(self._parent(other))
   4531 
   4532 def derivative(self, *args):

File /ext/sage/10.4/src/sage/symbolic/expression.pyx:4514, in sage.symbolic.expression.Expression._pow_()
   4512                    relational_operator(self._gobj))
   4513 else:
-> 4514     x = g_pow(self._gobj, nexp._gobj)
   4515 return new_Expression_from_GEx(self._parent, x)
   4516 

RuntimeError:
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-09-03 07:23:29 +0100

Seen: 2,037 times

Last updated: Sep 04 '20