Bug in the binary gcd code

[laszloladanyi]

The code on the line "a >>= az, b >>= bz;" is incorrect, it should be "a >>= shift, b >>= shift;"
Similarly, in the final version "b >>= bz;" is incorrect, it should be "b >>= shift;"

--Laci

PS: I wanted to submit a patch and pull request, but when I tried to submit the edited the page I got an error:
"Error while loading data from Github. This might be a temporary issue. Please try again later."
But it never worked in the course of 3 days... So I'm submitting the bug as an issue.

[sslotin]

I believe it is correct. You need to divide a and b by the largest power of two possible as a precondition for the loop. shift is calculated and saved to multiply it by the final gcd value in the end.

Maybe using shift instead of az and bz is also correct, but it possibly results in one more iteration or so.

[laszloladanyi]

My bad, you are right. You can safely remove the remaining powers of 2, since they can't be part of the gcd. Sorry :-(