Memory exhaustion calculating very large integers

[davidar]

Is your feature request related to a problem? Please describe. The following program from https://oeis.org/A000643 causes mathics to use over 10GB of RAM, and I end up having to kill it to avoid it from exhausting all the memory on my machine:

Off[General::ovfl];
a={1,0};
Flatten[Prepend[Table[s=Plus@@a;a=2^(RotateLeft[a]);a[[ -1]]=s,{n,8}],
                Table[0,{m,Length[a]-1}]]]

To be fair, the program attempts to calculate an integer with over 5 million digits (inside the list a), which is why I'm not calling this a bug. But at the same time WMA handles this program completely fine, and gives a result almost immediately (it just takes a long time if you try to print the final value of a, but doesn't appear to use any substantial amount of memory)

Describe the solution you'd like Better memory efficiency for arbitrary precision arithmetic.

Describe alternatives you've considered Don't attempt to calculate numbers that are that big ;)

[mmatera]

It seems that the problem appears when it tries to calculate SystemPower[2, 35184372088832]`

Power[2, 351843] is calculated without problems, but SystemPower[2, 3518430] crashes the evaluation. The problem happens at the level of the Python interpreter: 2**35184372088832 produces the same issue.

[davidar]

Huh, I wonder where that power is coming from, it should only be calculating $2^{16777496}$, which python can handle fine (but just doesn't want to print by default):

>>> 2**16777496
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: Exceeds the limit (4300 digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit

The other power is too big for WMA even, but at least it prints an error message instead:

In[4]:= Power[2, 35184372088832]

General::nomem: The current computation was aborted because there was insufficient memory available to
    complete the computation.

Throw::sysexc: Uncaught SystemException returned to top level. Can be caught with Catch[…,
    _SystemException].

Out[4]= SystemException[MemoryAllocationFailure]

[mmatera]

I found where the evaluation stucks by wrapping the expression with TraceEvaluation.

The collapse of the evaluation does not happen if you use arbitrary precision Real numbers instead of integers. My guess is that WMA switch automatically the representation when it founds a so large number.