On Thursday, 23 June 2016 at 17:22:55 UTC, Andrei Alexandrescu
wrote:
So I was looking for an efficient exponentiation
implementation, and http://www.stepanovpapers.com/PAM.pdf has a
nice discussion starting at page 54. Stepanov's solution,
however, duplicates code, so I eliminated it:
https://dpaste.dzfl.pl/e53acb41885a
The cost is the use of one goto. Can the code be restructured
to not need it?
Thanks,
Andrei
The inner loop is not a loop, so that's not a problem:
// Loop invariant: r * (b ^^ e) is the actual result
while(true) {
if (e % 2 != 0) {
r = mul(r, b, overflow);
if (e == 1) return r;
}
b = mul(b, b, overflow);
e /= 2;
}