Impossible de trouver la raison de la défaillance de segmentation dans mon code C++ Fibonacci

Question

Mon code est segfaulting. Je ne peux pas comprendre pourquoi. Cela pourrait avoir à faire avec la fonction "fermatPrimeTest()" que j'ai faite.

#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

Ligne 67:

while (lowerBound < three < upperBound) { 

Beaucoup de langues ne supportent pas la comparaison enchaînée comme cela correctement. Vous devez écrire ceci:

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

---

En C++, lowerBound < three < upperBound est interprété comme (lowerBound < three) < upperBound. L'expression lowerBound < three donnera toujours 0 (faux) ou 1 (true), cette boucle while toujours réussir depuis upperBound est 100.

Cela provoque la ligne result[i++] = three; à exécuter plus de 100 fois car il y a plus de 100 Fibonacci nombres premiers. Mais la taille de result est seulement 100. Lorsque i ≥ 100, le programme va écrire dans une zone mémoire invalide, ce qui provoque le défaut de segmentation.

---

Comme Andres a dit dans le commentaire, vous feriez mieux d'utiliser a vector, par exemple

#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

Je vois beaucoup de bugs potentiels.

Voici le bug causant votre accident:

Compte tenu de votre boucle principale:

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

Je pense que vous devriez vraiment dire pour protéger votre longueur du tableau indépendant de votre arrêt de l'algorithme.

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

Maintenant, pour le reste de ma critique: Compte tenu de cette ligne:

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

sizeof (résultat) retournera toujours 4 (ou 8 sur une compilation 64 bits) parce que vous calculez la taille d'un pointeur au lieu de sizeof pour un tableau statique. Le compilateur n'a aucune idée que ce pointeur est vraiment un tableau de taille statique.

Vous voulez probablement dire:

return i;