Ask Your Question

Segmentation fault when evaluating 3^3^3^3

asked 2012-01-04 10:35:08 +0200

anonymous user


updated 2023-01-10 00:01:09 +0200

tmonteil gravatar image

I evaluated "3^3^3^3" in the notebook and got a segmentation fault. Could somebody check if they can replicate this and file a bug report if appropriate?

Traceback (most recent call last): File "<stdin>", line 1, in <module> File "", line 10, in <module> exec compile(u'open("","w").write("# -- coding: utf-8 --\n" + _support_.preparse_worksheet_cell(base64.b64decode("M14zXjNeMw=="),globals())+"\n"); execfile(os.path.abspath("")) File "", line 1, in <module>

File "/tmp/tmpsWGDUr/", line 3, in <module> exec compile(u'_sage_const_3 *_sage_const_3 *_sage_const_3 **_sage_const_3 File "", line 1, in <module>

File "integer.pyx", line 1897, in sage.rings.integer.Integer.__pow__ (sage/rings/integer.c:12823) RuntimeError: Segmentation fault

EDIT: 4.7.2, compiled from source on Debian 6.0.3 64bit.

edit retag flag offensive close merge delete


Happens in the command line as well.

chaesloc2 gravatar imagechaesloc2 ( 2012-01-04 10:36:20 +0200 )edit

2^2^2^2 is fine. 4^4^4^4 gives "RuntimeError: exponent must be at most 9223372036854775807", which is not properly documented (not in "Integer?").

chaesloc2 gravatar imagechaesloc2 ( 2012-01-04 10:38:51 +0200 )edit

Something completely unrelated: when one asks a question anonymously, one would expect their comments on that question to be anonymous too.

chaesloc2 gravatar imagechaesloc2 ( 2012-01-04 10:40:55 +0200 )edit

2^(2^31) is a segfault. 2^(2^31-1) cannot allocate enough memory, so I assume it works.

chaesloc2 gravatar imagechaesloc2 ( 2012-01-04 10:45:57 +0200 )edit

3^(2^31-1) is a segfault. 3^(2^30-1) isn't. Anyway, I can't imagine this being very helpful to anybody, sorry for spamming comments. I won't actively try to watch this question, so don't expect replies from me, and certainly don't suggest that I file a bug report myself.

chaesloc2 gravatar imagechaesloc2 ( 2012-01-04 10:55:08 +0200 )edit

3 Answers

Sort by ยป oldest newest most voted

answered 2012-01-05 01:36:48 +0200

I dont know how the "power" algorithm is implemented in sage. But you can use the binary method for power (or repeated squaring method). It goes like this:

To compute a^n, write down binary representation of n say

n = \sum_{i=1}^d a_i 2^i.

Then if a_i = 1, then square, else (i.e. a_i=0) do nothing.

Here is the algorithm:

If a_0 = 0
    set c = 1
    set c = a
set b_0 = a
For each i in 1..d (Note: d = no of digits in bin. rep. of n)
    b_i = b_{i-1}^2
    If a_i == 1
        c = c \cdot b_i
        c = c

This algorithm comes very handy when you want to compute a^n(mod m). I hope this will help you to get rid of these limitation on index.

-- VInay

edit flag offensive delete link more

answered 2012-01-05 02:55:49 +0200

Volker gravatar image

This is now Trac #12266

edit flag offensive delete link more


This bug is now fixed!

tmonteil gravatar imagetmonteil ( 2015-02-07 22:56:20 +0200 )edit

answered 2012-01-04 12:57:00 +0200

parzan gravatar image

Note the order of actions is not the one you would have expected (I think):

sage: ((3^3)^3)^3
sage: 3^(3^(3^3))
RuntimeError: exponent must be at most 2147483647
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


Asked: 2012-01-04 10:35:08 +0200

Seen: 1,115 times

Last updated: Jan 05 '12