CODEWITHSUNDEEP
pythonmathdictionarysegmentation-faultout-of-memory
Varghese George
Varghese George

Reputation: 71

Modified Ackermann Function in Python Segmentation fault

So I tried to create a modified version of the basic Ackermann function that uses a dictionary to store the already computed values, so that next time when the program comes across a similar function call it can use the already computed value, and this seems to speed up the process quiet considerably. Here is the code:

import sys
sys.setrecursionlimit(100000)

resultset ={}

def ackermann(m, n):
    """Computes the Ackermann function A(m, n)

    See http://en.wikipedia.org/wiki/Ackermann_function

    n, m: non-negative integers
    """
    if (m,n) in resultset:
        return resultset[(m,n)]
    if m == 0:
        ans = n+1;
    elif n == 0:
        ans = ackermann(m-1, 1)
    else:
        ans = ackermann(m-1, ackermann(m, n-1))
    if m != 0:
        resultset[(m,n)] = ans
    return ans;

for i in range(0,10) :
    for j in range(0,10) :
        print("ackermann(%d, %d): " % (i, j) + str(ackermann(i,j)))

Now the problem I have is that it stops execution after a very short while. The output is like:

ackermann(0, 0): 1
ackermann(0, 1): 2
ackermann(0, 2): 3
ackermann(0, 3): 4
ackermann(0, 4): 5
ackermann(0, 5): 6
...
...
...
ackermann(3, 2): 29
ackermann(3, 3): 61
ackermann(3, 4): 125
ackermann(3, 5): 253
ackermann(3, 6): 509
ackermann(3, 7): 1021
ackermann(3, 8): 2045
ackermann(3, 9): 4093
ackermann(4, 0): 13
ackermann(4, 1): 65533
Segmentation fault

My system is a core i5 with 12 GB of ram, and this program exits way before it reaches the mem limit, what could be the problem?

I also tried using Shelves instead of dictionary so that it would store the data on disk. Here is the code for that:

I also tried using shelves instead of dictionaries, so that I could see the usage on disk. Here is the code for that..

import sys
sys.setrecursionlimit(100000)

import shelve
resultset = shelve.open("file.o")

def ackermann(m, n):
    """Computes the Ackermann function A(m, n)

    See http://en.wikipedia.org/wiki/Ackermann_function

    n, m: non-negative integers
    """
    if str((m,n)) in resultset:
        return resultset[str((m,n))]
    if m == 0:
        ans = n+1;
    elif n == 0:
        ans = ackermann(m-1, 1)
    else:
        ans = ackermann(m-1, ackermann(m, n-1))
    if m != 0:
        resultset[str((m,n))] = ans
    return ans;

for i in range(0,6) :
    for j in range(0,6) :
        print("ackermann(%d, %d): " % (i, j) + str(ackermann(i,j)))

The output file comes to exactly 6MB and python crashes. Does anybody have a clue why?

Upvotes: 2

Views: 696

Answers (2)

Varghese George
Varghese George

Reputation: 71

Well a lot of trial and error, I was able to understand the problem was that the program was running out of stack space, because of the recursion. I was able to fix this on Linux by setting stack size as infinite. Unfortunately I don't think there is a similar solution on windows. Here is the code for what I did..

import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (resource.RLIM_INFINITY, resource.RLIM_INFINITY))
sys.setrecursionlimit(10**8)

resultset ={}

def ackermann(m, n):
    """Computes the Ackermann function A(m, n)

    See http://en.wikipedia.org/wiki/Ackermann_function

    n, m: non-negative integers
    """
    if (m,n) in resultset:
        return resultset[(m,n)]
    if m == 0:
        ans = n+1;
    elif n == 0:
        ans = ackermann(m-1, 1)
    else:
        ans = ackermann(m-1, ackermann(m, n-1))
    if m != 0:
        resultset[(m,n)] = ans
    return ans;

for i in range(0,6) :
    for j in range(0,6) :
        print("ackermann(%d, %d): " % (i, j) + str(ackermann(i,j)))

These two lines is where the magic happens:

resource.setrlimit(resource.RLIMIT_STACK, (resource.RLIM_INFINITY, resource.RLIM_INFINITY)) sys.setrecursionlimit(10**8)

Anyway thanks for your attempts. :)

Upvotes: 2

Ed King
Ed King

Reputation: 454

The Ackermann function gets really large, really fast.... the value for the next step (4, 2) is 2.00352993040684646497907235156025575044782547556975141... × 10^19728.

If you look at the segfault, you're probably getting something like this:

python[4413]: segfault at 7fff2bae5ff8 ip 000000000052185f sp 00007fff2bae6000 error 6 in python2.7[400000+2bd000]

Error 6 indicates a page write failure.

Upvotes: 1

Related Questions