math.gcd() vs Euclidean Algo

Question

What is the most efficient way to find the gcd of two numbers, using math.gcd() function after importing math library or

def computegcd(x,y):
    while(y):
        x,y = y,x%y
    return x

user_5052365 · Answer

you can use timeit to check it yourself :)

run this:

from timeit import timeit
import math
import random

x = random.randint(9 ** 6, 9 ** 7)
y = random.randint(5 ** 5, 5 ** 6)


def with_math():
    return math.gcd(x, y)


def with_euclid():
    xx = x
    yy = y
    while yy:
        xx, yy = yy, xx % yy
    return xx


print(with_math() == with_euclid())  # Make sure result is same
print(timeit(with_math, number=10**7))
print(timeit(with_euclid, number=10**7))

on my current laptop it outputs:

True
3.021651975000168
7.143860205000237

math.gcd() vs Euclidean Algo

1 Answers