FilesExpand file tree

 master

/

gcd.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

63 lines (51 loc) · 1.34 KB

 master

/

gcd.py

Copy path

Top

File metadata and controls

• Code
• Blame

63 lines (51 loc) · 1.34 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

def gcd(a, b):

"""Computes the greatest common divisor of integers a and b using

Euclid's Algorithm.

gcd{𝑎,𝑏}=gcd{−𝑎,𝑏}=gcd{𝑎,−𝑏}=gcd{−𝑎,−𝑏}

See proof: https://proofwiki.org/wiki/GCD_for_Negative_Integers

"""

a_int = isinstance(a, int)

b_int = isinstance(b, int)

a = abs(a)

b = abs(b)

if not(a_int or b_int):

raise ValueError("Input arguments are not integers")

if (a == 0) or (b == 0) :

raise ValueError("One or more input arguments equals zero")

while b != 0:

a, b = b, a % b

return a

def lcm(a, b):

"""Computes the lowest common multiple of integers a and b."""

return abs(a) * abs(b) / gcd(a, b)

"""

Given a positive integer x, computes the number of trailing zero of x.

Example

Input : 34(100010)

~~~~~^

Output : 1

Input : 40(101000)

~~~^^^

Output : 3

"""

def trailing_zero(x):

cnt = 0

while x and not x & 1:

cnt += 1

x >>= 1

return cnt

"""

Given two non-negative integer a and b,

computes the greatest common divisor of a and b using bitwise operator.

"""

def gcd_bit(a, b):

tza = trailing_zero(a)

tzb = trailing_zero(b)

a >>= tza

b >>= tzb

while b:

if a < b:

a, b = b, a

a -= b

a >>= trailing_zero(a)

return a << min(tza, tzb)