First time here? Check out the FAQ!

Ask Your Question
1

Segmentation fault when evaluating 3^3^3^3

asked 13 years ago

anonymous user

Anonymous

updated 2 years ago

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 "_sage_input_11.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# -- coding: utf-8 --\n" + _support_.preparse_worksheet_cell(base64.b64decode("M14zXjNeMw=="),globals())+"\n"); execfile(os.path.abspath("___code___.py")) File "", line 1, in <module>

File "/tmp/tmpsWGDUr/___code___.py", 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.

Preview: (hide)

Comments

Happens in the command line as well.

chaesloc2 gravatar imagechaesloc2 ( 13 years ago )

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 ( 13 years ago )
1

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

chaesloc2 gravatar imagechaesloc2 ( 13 years ago )

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

chaesloc2 gravatar imagechaesloc2 ( 13 years ago )

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 ( 13 years ago )

3 Answers

Sort by » oldest newest most voted
1

answered 13 years ago

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
else 
    set c = a
set b_0 = a
For each i in 1..d (Note: d = no of digits in bin. rep. of n)
do 
    b_i = b_{i-1}^2
    If a_i == 1
        c = c \cdot b_i
    else
        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

Preview: (hide)
link
1

answered 13 years ago

Volker gravatar image

This is now Trac #12266

Preview: (hide)
link

Comments

This bug is now fixed!

tmonteil gravatar imagetmonteil ( 10 years ago )
0

answered 13 years ago

parzan gravatar image

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

sage: ((3^3)^3)^3
7625597484987
sage: 3^(3^(3^3))
---------------------------------------------------------------------------
RuntimeError: exponent must be at most 2147483647
Preview: (hide)
link

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 13 years ago

Seen: 1,276 times

Last updated: Jan 05 '12