Thread: Not working as intended

So this is returning a crazy number. It's not working as intended because the number it returns... well, it's impossible to be right because (99*99*99*99*99) = 9509900499, and the returned number is greater, therefore something is broken.

It's supposed to return the greatest product of 5 adjacent numbers in the 20x20 array.

Code:

#include <iostream>

using namespace std;

int grid[20][20] = { { 8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8 },
							{ 49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0 },
							{ 81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65 },
							{ 52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91 },
							{ 22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80 },
							{ 24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50 },
							{ 32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70 },
							{ 67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21 },
							{ 24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72 },
							{ 21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95 },
							{ 78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 04, 62, 16, 14, 9, 53, 56, 92 },
							{ 16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57 },
							{ 86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58 },
							{ 19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40 },
							{ 4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66 },
							{ 88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69 },
							{ 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36 },
							{ 20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16 },
							{ 20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54 },
							{ 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48 } };

int main() {
	int i = 0;
	int m0 = 0;
	int m1 = 1;
	int m2 = 2;
	int m3 = 3;
	int m4 = 4;
	unsigned long long int ans = 0;

	while (i < 20)	{
			while (m4 < 20) {
				unsigned long long int temp = (grid[i][m0] * grid[i][m1] * grid[i][m2] * grid[i][m3] * grid[i][m4]);
				if (temp > ans)
					ans = temp;
				m0++; m1++; m2++; m3++; m4++;
			}
		m0 = 0, m1 = 1, m2 = 2, m3 = 3, m4 = 4;
		i++;
	}
        cout << ans;
}

edit: the number I get is: 18446744071741414188

The problem may be with the unsigned long long type. I tested your program on the MinGW port of g++ and got the same wrong answer. Changing to unsigned long gave a more reasonable answer. In any case, unsigned long long is not one of the built-in types mentioned in the C++ Standard, and there might be a bug in this MinGW port of the g++ compiler extension.

Hmm you're right, that does appear to be the case, I just tried with 'long' and got a more reasonable answer aswell. Hopefully that's all it was, thanks for the help. If I find out it was something else I'll post again

The error appears to be due to integer overflow. You multiply 5 int's and the largest results overflow, only then do you convert the result to unsigned long long which is long enough. Since you are essentially casting a negative value, the upper bits of the result will be all 1, whereas the lower 32 bits contain the correct result - and altogether looking like a complete mystery. You could cast one of the multipliers to unsigned long long to start with if you want to use that type.

(What a relief that it didn't really turn out a compiler bug! )

Originally Posted by anon

The error appears to be due to integer overflow. You multiply 5 int's and the largest results overflow, only then do you convert the result to unsigned long long which is long enough.

Yes, that seems to be the case. Changing to unsigned long happened to work due to implementation defined behaviour.

Originally Posted by anon

What a relief that it didn't really turn out a compiler bug!

I wish I had carefully documented my problems when I attempted to use long long with MinGW in the past; perhaps I similiarly encountered such an overflow without realising it.