Fermat's last theorem algorithm

Question

I take this definition of Fermat's last theorem.

I tried to code the algorithm to check for small values:

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

And this is the exit screen:

How is this possible? Am I missing something about "large integers" in C ++ programming that might get the wrong result?

Answer 1

The pow () functions are full; remember that int has a limited size.

For example, pow (256, 4) will overflow with 32 bits, pow (256, 8) with 64 bits, even if you use unsigned data types.

Technically, an int overflow is an undefined behavior, so anything can happen, including wrapping (i.e. back to 0) or nasal daemons.

unsigned int calculations of modulo 2, raised to the degree of WIDTH according to the standard; those. will always be wrapped.

Answer 2

I'm missing something

You. Quite a bit of. Let me list.

• Types . Not all numbers in C ++ are integers. In particular, the result of pow not an integer.
• Accuracy . Those types that are not integers have limited precision in C ++. In math 1 and 1.0000000000000000000000000000000000000000000000000000982 - different numbers. In your C ++ program, good luck with that.
• Limitations Both integer and non-integer numbers in C ++ are limited in the range of values ​​that they can take. An int variable is guaranteed to be able to hold numbers from -32767 to 32767 inclusive. Many implementations actually support a little more than, say, from -2147483648 to 2147483647. Many implementations have other types that can contain large ranges of numbers, for example. 0 up to 18446744073709551616 or sometimes up to 340282366920938463463374607431768211456 or even up to 115792089237316195423570985008687907853269984665640564039457584007913129639936. (If you can take the logarithm from this, something is worth something that has something to do with that, you have something to do with that. For comparison, 927 Strength 104 376957467458457979751155893254582133603833255821602148851832991547421266649046326838345134050350882042675908426098865621401193999321757163912667101283653576225503152314408933435079267041822928198211089834145222519701307017745008621307049171220994632585789166175212394809510781938945415209193278956111609706241.

Answer 3

Values

int limited to 32 bits (including the signed bit), so high values ​​"wrap" outside 2147483647. C / C ++ does not have a built-in data type for arbitrarily large values.

To slightly reduce the problem, you can use the long or unsigned long (64-bit version on 64-bit platforms). Some compilers support 64-bit on 32-bit platforms if you use long long .

Edit: as indicated in the comment below, the restrictions do not apply equally to all C / C ++ implementations, but for most non-implemented systems that you will see today, these are the limits that you are going to use.