Can't find reason for segmentation fault in my Fibonacci C++ code

Question

My code is segfaulting. I can't understand why. It might have to do with the "fermatPrimeTest()" function I made.

#include <iostream>
#include <cmath>
#include <cstdlib>
#include "fib.h"
using namespace std;

bool fermatPrimeTest( unsigned long int p )
{
  if ( p % 2 == 0 ) { // if even
    return false;
  } 
  else if ( p == 1 || p == 2 || p == 3 ) { // if 1, 2, or 3
    return true;
  }
  unsigned long a = 2 ; // just give it an initial value, make it happy
  for ( int i=0 ; i < 3 ; i++) {
    if (GCD(a, p-1) != 1) {
      a = rand() % (p-1) + 1;
    }
    // cout << "a=" << a << " ,p=" << p << GCD(a, p-1) << endl;
  }
  return true;
}

int GCD(unsigned long int a, unsigned long int b) {
  while( 1 ) {
    a = a % b;
    if( a == 0 )
      return b;
      // cout << "GCD-b=" << b << ", GCD-a=" << a << endl;

    b = b % a;

    if( b == 0 )
      return a;
      // cout << "GCD-a=" << a << ", GCD-b=" << b << endl;
  }
}

// fills array with Fibonacci primes
// returns number of primes
unsigned long findFibonacciPrimes (unsigned long lowerBound,
                                   unsigned long upperBound,
                                   unsigned long result[])
{  
  int i = 0;  //counter
  unsigned long maxElements = upperBound - lowerBound + 1;  // there can be no more array elements than this

  /*
  The array result is guaranteed to have enough space to store all the numbers found. 
  Your program will crash if it attempts to write past the end of the array, and no 
  marks will be awarded for any tests in which this occurs. You are also guaranteed that 
  1 < lowerBound < upperBound < 3,000,000,000.
  Every F_n that is prime has a prime  index n, with the exception of F_4=3. 
  However, the converse is not true (i.e., not every prime index p gives a prime F_p). 
  */

  unsigned long int one = 0, two = 1, three = one + two;   // element x-2, x-1, and x for Fib sequence
  result[i++] = 0;
  result[i++] = 1;

 while ( lowerBound < three < upperBound ) {
    if ( fermatPrimeTest(three) ) {
      result[i++] = three;
    }
    one = two;
    two = three;
    three = one + two;
  }
  return sizeof result / sizeof result[0];   // return size of array TODO!
}
int main() {
  unsigned long result[100];
  findFibonacciPrimes(1,100,result);
}

Answer 1

Line 67:

 while ( lowerBound < three < upperBound ) {

Many languages do not support chained comparison like this correctly. You need to write this instead:

 while ( lowerBound < three && three < upperBound ) {

---

In C++, lowerBound < three < upperBound is interpreted as (lowerBound < three) < upperBound. The expression lowerBound < three will always result in 0 (false) or 1 (true), so this while loop will always succeed since upperBound is 100.

This causes the line result[i++] = three; to be run over 100 times since there are over 100 Fibonacci primes. But the size of result is only 100. When i ≥ 100, the program will be writing to invalid memory region, and this causes the Segmentation Fault.

---

As Andres said in the comment, you'd better use a vector, e.g.

#include <vector>
...
std::vector<unsigned long> findFibonacciPrimes(unsigned long lowerBound,
                                               unsigned long upperBound) {
   std::vector<unsigned long> result;
   result.push_back(0);
   result.push_back(1);  // note that 0 and 1 aren't primes.
   ...
   while (lowerBound < three && three < upperBound ) {
      if ( fermatPrimeTest(three) ) {
        result.push_back(three);
      ...
   return result;
}

int main () {
   std::vector<unsigned long> result = findFibonacciPrimes(1, 100);
   // use result.size() to get the number of items in the vector.
   // use result[i]     to get the i-th item.
}

Answer 2

I see lots of potential bugs.

Here's the bug causing your crash:

Given your main loop:

 while ( lowerBound < three < upperBound ) {
    if ( fermatPrimeTest(three) ) {
      result[i++] = three;
    }
    one = two;
    two = three;
    three = one + two;
  }

I think you really should say this to protect your array length independent of your algorithm stopping.

 while ((i < maxElements) && (lowerBound < three) && (three < upperBound)) {
    if ( fermatPrimeTest(three) ) {
      result[i++] = three;
    }
    one = two;
    two = three;
    three = one + two;
  }

Now for the rest of my critique: Given this line:

return sizeof result / sizeof result[0];   // return size of array TODO!

sizeof(result) will always return 4 (or 8 on a 64-bit compile) because you are calculating the size of a pointer instead of the sizeof for a static array. The compiler has no idea that this pointer is really a staticly sized array.

You likely want to say:

return i;