Let \(a,b\in\mathbb{Z}\) and \(a\le b\). The algorithm \(\gcd(a,b)\) calculates correctly the greatest common divisor of \(a\) and \(b\) and requires \(\mathcal O(\log |b|)\) (worst case and average case) division operations, which corresponds to \(\mathcal O(\log^2 |b|)\) bit operations.
def gcd(a, b): a = abs(a) b = abs(b) r = b while r > 0: r = a % b a = b b = r d=a return d
print(gcd(5159, 4823))
Proofs: 1
