Skip to content
  • Zhaoxiu Zeng's avatar
    lib/GCD.c: use binary GCD algorithm instead of Euclidean · fff7fb0b
    Zhaoxiu Zeng authored
    The binary GCD algorithm is based on the following facts:
    	1. If a and b are all evens, then gcd(a,b) = 2 * gcd(a/2, b/2)
    	2. If a is even and b is odd, then gcd(a,b) = gcd(a/2, b)
    	3. If a and b are all odds, then gcd(a,b) = gcd((a-b)/2, b) = gcd((a+b)/2, b)
    
    Even on x86 machines with reasonable division hardware, the binary
    algorithm runs about 25% faster (80% the execution time) than the
    division-based Euclidian algorithm.
    
    On platforms like Alpha and ARMv6 where division is a function call to
    emulation code, it's even more significant.
    
    There are two variants of the code here, depending on whether a fast
    __ffs (find least significant set bit) instruction is available.  This
    allows the unpredictable branches in the bit-at-a-time shifting loop to
    be eliminated.
    
    If fast __ffs is not available, the "even/odd" GCD variant is used.
    
    I use the following code to benchmark:
    
    	#include <stdio.h>
    	#include <stdlib.h>
    	#include <stdint.h>
    	#include <string...
    fff7fb0b