Не удается найти причину ошибки сегментации в моем коде Fibonacci C++

Question

Мой код является segfault. Я не понимаю, почему. Это может иметь отношение к функции «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, программа будет записывать в недопустимую область памяти, и это вызывает ошибку сегментации.

---

Как сказал Андрес в комментарии, вы бы лучше использовать a 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 (результат) всегда будет возвращать 4 (или 8 на 64-битной компиляции), потому что вы вычисляя размер указателя вместо sizeof для статического массива. Компилятор не знает, что этот указатель действительно представляет собой массив с установленным размером.

Вы, вероятно, хотите сказать:

return i;