CODEWITHSUNDEEP
pythonpython-3.x
crazysra
crazysra

Reputation: 151

math.gcd() vs Euclidean Algo

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

Upvotes: 2

Views: 191

Answers (1)

Adam.Er8
Adam.Er8

Reputation: 13413

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

Upvotes: 3

Related Questions