I recently wrote an interpreter in C for a made up language. As a test of its performance, I coded up a powmod function, powmod(a, e, n) = a^e mod n (where ^ is

I recently wrote an interpreter in C for a made up language. As a test of its performance, I coded up a powmod function, powmod(a, e, n) = a^e mod n (where ^ is power not xor). The program contained the lines: if (n % 2 == 0) return (powmod(a, n/2, p) * powmod(a, n/2, p)) % p; else return (powmod(a, n/2, p) * powmod(a, (n+1)/2, p)) % p; The embarrassing thing is that even after having spent years writing mathematical code, it took me ages before I figured out it was not my interpreter, but this algorithm that was so ridiculously slow. Fortunately the interpreter is now really fast!