Efficiency
Akhavi and Vallée proved that binary GCD can be about 60% more efficient (in terms of the number of bit operations) on average than the Euclidean algorithm. However, although this algorithm outperforms the traditional Euclidean algorithm, its asymptotic performance is the same, and it is considerably more complex thanks to the availability of division instruction in all modern microprocessors.
In addition, real computers operate on more than one bit at a time, and even assembly language binary GCD implementations have to compete against carefully designed hardware circuits for integer division. Overall, Knuth (1998) reports a 15% gain over Euclidean GCD, and according to one comparison, the greatest gain was about 60%, while on some popular architectures even good implementations of binary GCD were marginally slower than the Euclidean algorithm.
In general, with implementations of binary GCD similar to the above C code, the gain in speed over the Euclidean algorithm is always less in practice than in theory. The reason is that the code uses many data-dependent branches. Many branches may be removed by computing min(a,b) and |a-b| using mixtures of Boolean algebra and arithmetic.
The only data-dependent branch that these techniques do not remove is the loop condition marked Loop X, which can be replaced by a single count trailing zeros (CTZ) operation and shift. Depending on platform, CTZ may be performed either by a single hardware instruction, by an equivalent instruction sequence, or with the aid of a lookup table.
Read more about this topic: Binary GCD Algorithm
Famous quotes containing the word efficiency:
“I’ll take fifty percent efficiency to get one hundred percent loyalty.”
—Samuel Goldwyn (1882–1974)
“Nothing comes to pass in nature, which can be set down to a flaw therein; for nature is always the same and everywhere one and the same in her efficiency and power of action; that is, nature’s laws and ordinances whereby all things come to pass and change from one form to another, are everywhere and always; so that there should be one and the same method of understanding the nature of all things whatsoever, namely, through nature’s universal laws and rules.”
—Baruch (Benedict)
““Never hug and kiss your children! Mother love may make your children’s infancy unhappy and prevent them from pursuing a career or getting married!” That’s total hogwash, of course. But it shows on extreme example of what state-of-the-art “scientific” parenting was supposed to be in early twentieth-century America. After all, that was the heyday of efficiency experts, time-and-motion studies, and the like.”
—Lawrence Kutner (20th century)