Python Segfault, from range?

Question

So i am trying to generate primes less than 2000000 and find their sum.. For a sample size I tried primes to 40000, but got a Segmentation Fault. I tried many values and I find the number 35044 to be the crashing point of the program.

import sys
sys.setrecursionlimit(100000000)
def stuff(total, rnge):
    for n in rnge:
        ubound=int(n**0.5)+1
        print ubound
        for x in range(3, ubound, 2):
            if n % x == 0:
                stuff(total, range(n+2, 35044, 2))
        #print n
        total = total + n
            #print total
    print total
    exit()
stuff(17, range(11, 35044, 2))

This is the error that results: "Run Command: line 1: 2942 Segmentation fault: 11 python "$1" "${@:3}" Side note: Finder also says python crashed and gives me a crash report, including these two bits of interesting info:

Exception Type:  EXC_BAD_ACCESS (SIGSEGV)
Exception Codes: KERN_PROTECTION_FAILURE at 0x00007fff5f3fffb8

Not sure if this is useful.

Also, for those who are wondering, I am on the latest 15-inch rMPB with 16 GB RAM and 2.7 Ghz processor, when I run the program eat eats up all 14GB or something of free RAM then crashes after it prints the number 181 a few times.

Works fine for me. I think you should add the details of your platform etc ... — dusual, Sep 10 '13 at 04:44
Even though you've set a very high limit on recursion, python is still limited by the size of its process' stack. It sounds like you've found the hard limit. — FatalError, Sep 10 '13 at 04:48
@Smac89 agree, and the recursive call `stuff(total, range(n+2, 35044, 2))` is likely creating a huge number of quite large lists. Fixing `stuff` to use xrange would be a much better implementation in terms of memory/stack usage. — John Lyon, Sep 10 '13 at 04:54
Your function and variable names are terrible. How exactly is this code working? — , Sep 10 '13 at 04:57
@Lego Stormtroopr its working because I can name functions/variables whatever I want if there is no confliction — dillonh2, Sep 12 '13 at 04:19
@icehockey38 See [this link](http://stackoverflow.com/a/135669/2089675) — smac89, Sep 12 '13 at 06:11
@Smac89 Si do I just replace all range with xrange, because it still crashes as it did before, or do i change other things — dillonh2, Sep 14 '13 at 21:42
@icehockey38 From the description of your problem, it seems that even your ram is being exhausted by this program. I would suggest scrapping this idea and going with one of the answers below. Or find an iterative method for this — smac89, Sep 15 '13 at 05:13

score 2 · Accepted Answer · 2013-09-10T05:13:35.787

2

There really is no reason to use recursion as you run into stack issues like you've discovered, especially if your target language doesn't support tail-call optimisation - like Python.

This is an alternate, really naive implementation (O(n^2)), but it does so without recursion so it can be used to sum any number of primes, albeit ever slowly as the candidate window get larger.

from math import sqrt    
total = 1+2
for i in range(3,2000000):
    for j in range (2,int(sqrt(i)+1)):
        if i%j==0:break
    else:
        total+=i
print total

edited Sep 10 '13 at 05:13

answered Sep 10 '13 at 05:08

Off by 1? Usually one isn't considered a prime, but it's being included in the initial value of `total` for some reason. Otherwise this is a good answer! – Blckknght Sep 12 '13 at 04:45
@Blckknght Yeah I guess that could be it. Easy enough to fix though. – Sep 12 '13 at 04:51
1

@LegoStormtroopr Yes as it turns it it was off by one, thanks a bunch! – dillonh2 Sep 14 '13 at 21:39

score 1 · Answer 2 · answered Sep 10 '13 at 04:46

1

Could it be possible that the recursive calls to your function are exhausting the available memory of your system?

answered Sep 10 '13 at 04:46

Anthony

3,492
1
14
9

Not the recursion, the `range` calls. This is obviously python2, and OP is creating two huge ranges with every recursion. The recursion overhead itself is likely a very minor factor. – l4mpi Sep 10 '13 at 07:55
@l4mpi so how do i fix this then? – dillonh2 Sep 12 '13 at 04:23
@icehockey38 the simplest change would be using [`xrange`](http://docs.python.org/2/library/functions.html#xrange) instead of range, as Smac89 commented on your question two days ago. Quoting [the docs](http://docs.python.org/2/library/stdtypes.html#typesseq-xrange), "The xrange type is an immutable sequence which is commonly used for looping. The advantage of the xrange type is that an xrange object will always take the same amount of memory, no matter the size of the range it represents." Please learn how to use google to look up these things yourself... – l4mpi Sep 12 '13 at 08:55

Python Segfault, from range?

2 Answers2