Fermat letzter Satz Algorithmus

Question

Ich nehme this Definition von Fermat's Theorem zuletzt.

Ich habe versucht, einen Algorithmus zu kodieren es für kleine Werte zu überprüfen:

#include <iostream> 
#include <cmath> 
using namespace std; 

int main() 
{ 
    //a^n + b^n = c^n 

    int a, b, c, n, count = 0; 

    for (n = 3; n < 1000; n++) 
     for (a = 1; a < 1000; a++) 
      for (b = 1; b < 100; b++) 
       for (c = 1; c < 1000; c++) 
       { 
        if (a != b && b != c && a != c) 
        { 
         if (pow(a,n) + pow(b,n) == pow(c,n)) 
         { 
          cout << "\na: " << a << " b: " << b << " c: " << c << " n: " << n; 
          count++; 
         } 
        } 
       } 

    cout << count << " combinazioni"; 

} 

Und das ist ein Bildschirm eines Stückes Ausgabe:

Wie ist es möglich? Fehle ich etwas über "große Integer" in C++ - Programmierung, die ein falsches Ergebnis erhalten können?

Answer 1

Ihre pow() - Funktionen sind überfüllt; erinnere mich an eine int hat eine begrenzte Größe.

Zum Beispiel wird pow (256, 4) auf 32 Bit, pow (256, 8) auf 64 Bit überlaufen, auch wenn Sie unsigned Datentypen verwenden.

Technisch int Überlauf ist undefiniertes Verhalten so, etwas könnte passieren, einschließlich Wrap-around (das heißt zurück auf 0) oder nasal Dämonen.

unsigned int Berechnungen sind modulo 2 erhöht auf die Leistung von WIDTH gemäß dem Standard; d. h. wird sich immer umwickeln.

Answer 2

int Werte sind auf 32 Bit begrenzt (einschließlich des Vorzeichen-Bits), so dass hohe Werte über 2147483647 hinausgehen. C/C++ haben keinen eingebauten Datentyp für beliebig große Werte. Um das Problem etwas zu reduzieren, können Sie den Typ long oder unsigned long (64-Bit auf 64-Bit-Plattformen) verwenden. Einige Compiler unterstützen 64 Bit auch auf 32-Bit-Plattformen, wenn Sie long long verwenden.

Edit: wie in einem Kommentar unten erwähnt, gelten die Grenzen nicht gleichermaßen für alle Implementierungen von C/C++, aber für die meisten nicht eingebetteten Systeme, die Sie heute sehen werden, sind das die Grenzen, die Sie gehen sehen.

Answer 3

bin ich etwas fehlt

Sie sind. Ziemlich viel tatsächlich. Lass mich aufzählen.

1. Typen. Nicht alle Zahlen in C++ sind Ganzzahlen. Insbesondere ist das Ergebnis von pow keine ganze Zahl.
2. Präzision. Diese Typen, die keine Ganzzahlen sind, haben eine begrenzte Genauigkeit in C++. In Mathematik sind 1 und 1,00000000000000000000000000000000000000000000000000982 unterschiedliche Zahlen. In Ihrem C++ Programm, viel Glück damit.
3. Grenzen. Sowohl ganzzahlige als auch nicht ganzzahlige Zahlen in C++ sind in dem Wertebereich begrenzt, den sie annehmen können. Eine Variable vom Typ int kann garantiert Zahlen zwischen -32767 bis einschließlich 32767 enthalten. Viele Implementierungen unterstützen tatsächlich ein ganzes Stück mehr als das, sagen wir -2147483648 bis 2147483647. Viele Implementierungen haben andere Typen, die größere Zahlenbereiche enthalten können, z.0 bis 18446744073709551616 oder manchmal bis 340282366920938463463374607431768211456 oder sogar bis 115792089237316195423570985008687907853269984665640564039457584007913129639936. (Wenn Sie Logarithmen von 100-stelligen Zahlen in Ihrem Kopf nehmen können, werden Sie feststellen, dass alle diese Grenzen Potenzen von 2 oder etwas in der Nähe sind). Zum Vergleich: 927 an die Macht der 104 376957467458457979751155893254582133603833255821602148851832991547421266649046326838345134050350882042675908426098865621401193999321757163912667101283653576225503152314408933435079267041822928198211089834145222519701307017745008621307049171220994632585789166175212394809510781938945415209193278956111609706241.