Content deleted Content added
No edit summary |
→Why (u | v) & 1 == 0 is the correct test: new section |
||
Line 246:
}
</source>
== Why (u | v) & 1 == 0 is the correct test ==
Regarding edits by [[Special:Contributions/94.43.147.234|94.43.147.234]] ([[User talk:94.43.147.234|talk]]): Step 2 states:{{quote|text=If u and v are both even, then gcd(u, v) = 2·gcd(u/2, v/2), because 2 is a common divisor.}}
Therefore, before ''u'' and ''v'' may both be halved and ''shift'' incremented, the [[Least significant bit|LSB]] of ''u'' must be zero, '''and''' the LSB of ''v'' must be zero. The test (in line 12 of the C code fragment) would look like:
for (shift = 0; (u & 1) == 0 & (v & 1) == 0; ++shift) {
By [[de Morgan's laws]], this can be rewritten as
for (shift = 0; !((u & 1) == 1 | (v & 1) == 1); ++shift) {
As the only non-zero result of ''x'' & 1 is 1, the equalities disappear:
for (shift = 0; !((u & 1) | (v & 1)); ++shift) {
& is [[Distributive property|distributive]] over | so the two & 1 operations can be combined:
for (shift = 0; !(((u) | (v)) & 1); ++shift) {
Comparing with zero is equivalent to the Boolean negation. After removing redundant parentheses we obtain the test as originally written:
for (shift = 0; ((u | v) & 1) == 0; ++shift) {
As a further test, the code fragment as it stood (comprising <tt>((u & v) & 1) == 0</tt>) was ''compiled'', and <tt>gcd(1,2)</tt> was called. As ''u'' and ''v'' have no two bits set in the same column, the test never became false and the code hung in a loop between lines 12–15. ''u'' | ''v'' also corresponds to the ARM code (<tt>ORRS</tt>) which has been tested. – [[User:Regregex|Regregex]] ([[User talk:Regregex|talk]]) 16:28, 11 July 2011 (UTC)
| |||