0

So here's my question. What is causing the segfault on a seemingly unrelated change in code?

#include <iostream>
#include <stdio.h>
#include <set>
#include <vector>
#include <math.h>
std::set<int> atkin(int m){
    int r=0; bool s[m+2]; std::set<int> set;
    for(int i=0;i<m+2;++i)
        s[i]=false;
    s[2]=s[3]=true;
    int xr=pow((m-1)/4,.5);
    for(int x=1;x<=xr;++x){
        int yr=pow(m-4*x*x,.5);
        for(int y=1;y<=yr;++y) {
            int n=4*x*x+y*y;
            int nm=n%12;
            if(nm==1||nm==5)s[n]=!s[n];
        }
    }
    xr=pow((m-1)/3,.5);
    for(int x=1;x<=xr;++x){
        int yr=pow(m-3*x*x,.5);
        for(int y=1;y<=yr;++y) {
            int n=3*x*x+y*y;
            int nm=n%12;
            if(nm==7)s[n]=!s[n];
        }
    }
    xr=pow(2*m/3,.5); //was xr=pow(m+1)/3,.5); <- this worked fine.
    for(int x=1;x<=xr;++x){
        int yr=pow(3*x*x-m-1,.5);
        for(int y=1;y<=yr;++y) {
            int n=3*x*x-y*y;
            int nm=n%12;
            if(x>y && nm==11)s[n]=!s[n];
        }
    }
    for(int i=5;i<=pow(m,.5);++i){
        if(s[i]){
            int k=i*i;
            while(k<=m) {
                s[k]=false;
                k+=i*i;
            }
        }
    }
    for(int i=2;i<=m;++i){
        if(s[i]) {set.insert(i); printf("%03d ", i); if(++r%20==0) printf("\n");} //segfault directs here on gdb and valgrind
    }
    return set;
}

what's going on? I assume it is because of the larger value of xr, but I don't see how that connects to the set.insert(i); also this file gets included into a second one which calls atkin() I have had this problem on both windows 8 and arch linux. Thank you for your help and I'm sorry if my code enrages you in any way.

Luke Smith
  • 681
  • 3
  • 7
  • 15
  • 1
    Compile with -g and run with valgrind on Linux. It will give you lots of information. Post the output if you don't know how to interpret it. – kec May 03 '14 at 05:27
  • thanks. should I run valgrind with -v? – Luke Smith May 03 '14 at 05:33
  • No need to use `-v` at first. – kec May 03 '14 at 05:34
  • Check out this post http://stackoverflow.com/a/22658693/2724703 . This would let your program to attach with GDB whenever actual problem occurs(.i.e. invalid memory read or write). – Mantosh Kumar May 03 '14 at 05:35
  • `bool s[m+2];` is illegal in Standard C++ - arrays must have constant dimension – M.M May 03 '14 at 05:39
  • 3
    Using a tool like valgrind, like the previous commenters suggested, should certainly be helpful. While I didn't try to understand the full code flow, I would bet just based on the symptoms that your code writes beyond the end of the `s` array, i.e. writes to it with an index >= `m + 2`. That would then overwrite the memory of your `set` variable, putting it into a state that causes a crash when you try to use it. These types of errors are commonly called "memory stompers", and can be hard to track down if they happen in large and complex software systems. – Reto Koradi May 03 '14 at 05:40
  • Writing past the bounds of this non-standard array is the most likely candidate; switch it to `vector` (not vector) and use `.at` instead of `[]`, then you will get a tidier handling of out-of-bounds access – M.M May 03 '14 at 05:42
  • 1
    For example, if `m == 6` then the block headed by `this worked fine.` accesses out of bounds of `s`: `x==2` and `y==1` produces `n==11`, but the array dimension is `8` – M.M May 03 '14 at 05:47
  • @RetoKoradi and Matt How would I fix this? should I check to make sure n < m? – Luke Smith May 03 '14 at 05:52
  • Your code would greatly benefit from more descriptive variable names – Paul Renton May 03 '14 at 06:22
  • The key missing piece is what's the value being used to call this function. i.e. what's the value of `m`? – R Sahu May 03 '14 at 06:35

0 Answers0