在我的Fibonacci C++代码中找不到分段错误的原因

Question

我的代码是segfaulting.我不明白为什么.它可能与我制作的"fermatPrimeTest()"函数有关.

#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

第67行:

 while ( lowerBound < three < upperBound ) {

许多语言都不支持这样的链式比较.你需要写这个:

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

在C++中,lowerBound < three < upperBound被解释为(lowerBound < three) < upperBound.表达式lowerBound < three总是会产生0(假)或1(真),所以这个while循环总是成功,因为它upperBound是100.

这导致线路result[i++] = three;运行超过100次,因为有超过100个斐波纳契素数.但是大小result只有100.当i≥100时,程序将写入无效的内存区域,这会导致分段错误.

正如安德烈斯在评论中所说,你最好使用一个vector,例如

#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

我看到很多潜在的错误.

这是导致崩溃的错误:

给出你的主循环:

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

我认为你应该这样说来保护你的数组长度,而不依赖于你的算法停止.

 while ((i < maxElements) && (lowerBound < three) && (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!

sizeof(result)将始终返回4(或64位编译时为8),因为您正在计算指针的大小而不是静态数组的sizeof.编译器不知道这个指针实际上是一个静态大小的数组.

你可能想说:

return i;