Here I will explain quickly how to find the greatest common divisor of 2 numbers very fast. First of all Euclid;s algorithm states that GCD(x,y) equals GCD(x-y,y) which is true for x>y. But we can improve the performance significantly when replacing the operator "-" with operator % (reminder ) which means GCD(x,y)=GCD(x%y,y) where x>y.
No comments:
Post a Comment