Completely ridiculous bugs II
by math_explorer, Jan 26, 2014, 3:13 PM
Here's some modular-exponentiation code I was writing. What does it print if you input 100?
Click to reveal hidden text
#include <iostream> using namespace std; const long long MOD = 1000003; long long mod(long long x) { long long r = x % MOD; return r < 0 ? r + MOD : r; } long long modsq(long long x) { return mod(x * x); } long long pow(long long b, long long p) { if (p == 0) return 1; if (p == 1) return b; long long h = modsq(pow(b, p / 2)); return (p & 1) ? mod(h * b) : h; } int main() { long long x; cin >> x; cout << pow(2, x) << endl; }
Click to reveal hidden text
If you guessed 253109, you're right. (Really? You probably just guessed "whatever the right answer after all that modding is". That's what I would do. It's okay.)
If you guessed 1.26765e+30, because
Oops.
There you have it: a bug I couldn't find, or even reproduce or get warned about, on my own machine. (In my defense, I had about 5 minutes before the end of the contest in which this was an issue.)
I think the "correct" way to fix this in non-competition code would be to avoid
but it's just too useful for competitions, so the only way is to stay away from names of built-ins...
From what I remember, I also got Compile Errors that didn't appear on my own computer for defining things called "end", "distance", and "hash". But those errors told me what the compiler complained about; the above was a Wrong Answer. Ouch.
If you guessed 1.26765e+30, because
- the compiler on the judge machine has different settings and/or versions from those of the compiler on your computer;
- it silently links the math libraries into your namespace; and
- it decides to choose its pow(double, double) over your pow(long long, long long) because (drum roll) 2 is an int, not a long long
Oops.
There you have it: a bug I couldn't find, or even reproduce or get warned about, on my own machine. (In my defense, I had about 5 minutes before the end of the contest in which this was an issue.)
I think the "correct" way to fix this in non-competition code would be to avoid
using namespace std;
but it's just too useful for competitions, so the only way is to stay away from names of built-ins...
From what I remember, I also got Compile Errors that didn't appear on my own computer for defining things called "end", "distance", and "hash". But those errors told me what the compiler complained about; the above was a Wrong Answer. Ouch.