Thuật toán lý thuyết cuối cùng của Fermat

Question

Tôi lấy định nghĩa this Định lý cuối cùng của Fermat.

Tôi cố gắng để mã hóa một thuật toán để xác nhận nó cho giá trị nhỏ:

#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"; 

} 

Và đây là một màn hình của một mảnh đầu ra:

Làm thế nào là nó có thể? Tôi có thiếu một cái gì đó về "số nguyên lớn" trong lập trình C++ có thể có được một kết quả sai?

Answer 1

Các hàm pow() của bạn đang tràn; hãy nhớ rằng int có kích thước giới hạn.

Ví dụ: pow (256, 4) sẽ tràn trên 32 bit, pow (256, 8) trên 64 bit, ngay cả khi bạn sử dụng loại dữ liệu chưa được ký.

Về mặt kỹ thuật int tràn là không xác định hành vi như vậy, bất cứ điều gì có thể xảy ra, bao gồm bọc xung quanh (ví dụ: trở về 0), hoặc quỷ mũi.

unsigned int tính toán là modulo 2 được nâng lên sức mạnh của WIDTH theo tiêu chuẩn; tức là sẽ luôn quấn quanh.

Answer 2

int giá trị được giới hạn ở 32 bit (bao gồm bit dấu), sao cho giá trị cao "bọc" vượt quá 2147483647. C/C++ không có loại dữ liệu được tích hợp cho các giá trị lớn tùy ý.

Để giảm bớt sự cố, bạn có thể sử dụng loại long hoặc unsigned long (64 bit trên nền tảng 64 bit). Một số trình biên dịch hỗ trợ 64 bit trên nền tảng 32 bit, nếu bạn sử dụng long long.

Chỉnh sửa: như được chỉ ra trong nhận xét bên dưới, giới hạn không áp dụng như nhau cho tất cả triển khai C/C++, nhưng đối với hầu hết các hệ thống không được nhúng bạn sẽ thấy hôm nay, đó là giới hạn bạn sẽ nhìn.

Answer 3

Tôi có thiếu cái gì

Bạn đang. Khá nhiều. Hãy để tôi liệt kê.

1. Loại. Không phải tất cả các số trong C++ đều là số nguyên. Đặc biệt, kết quả của pow không phải là số nguyên.
2. Precision. Những loại không phải là số nguyên có độ chính xác giới hạn trong C++. Trong toán học, 1 và 1.000000000000000000000000000000000000000000000000982 là các số khác nhau. Trong chương trình C++ của bạn, chúc bạn may mắn với điều đó.
3. Giới hạn. Cả số nguyên và số nguyên trong C++ được giới hạn trong phạm vi giá trị mà chúng có thể giả định. Biến số int được đảm bảo để có thể giữ số từ -32767 đến 32767 một cách toàn diện. Nhiều triển khai thực tế hỗ trợ nhiều hơn một chút so với điều đó, giả sử -2147483648 đến 2147483647. Nhiều triển khai có các loại khác có thể chứa phạm vi số lớn hơn, ví dụ:0 đến 18446744073709551616 hoặc đôi khi đến 340282366920938463463374607431768211456 hoặc thậm chí đến 115792089237316195423570985008687907853269984665640564039457584007913129639936. (Nếu bạn có thể lấy logarit có số 100 chữ số trong đầu, bạn sẽ nhận thấy rằng tất cả các giới hạn này là quyền hạn của 2 hoặc một cái gì đó gần với điều đó). Để so sánh, 927 với sức mạnh của 104 là 376957467458457979751155893254582133603833255821602148851832991547421266649046326838345134050350882042675908426098865621401193999321757163912667101283653576225503152314408933435079267041822928198211089834145222519701307017745008621307049171220994632585789166175212394809510781938945415209193278956111609706241.