fork(2) download 
  1. s = '''
  2. import fractions
  3. a = 10
  4. b = 12
  5.  
  6. def b_gcd(m, n):
  7.     fact = 1
  8.  
  9.     while m > 1 and n > 1 and m != n:
  10.  
  11.         om, on = m & 1, n & 1
  12.  
  13.         if om and on:
  14.             m, n = abs(m - n)>>1, min(m, n)
  15.  
  16.         elif not (om or on):
  17.             fact, m, n = fact<<1, m>>1, n>>1
  18.  
  19.         else:
  20.             m, n = (m>>1, n) if on else (m, n>>1)
  21.  
  22.     m, n = (m, n) if n > m else (n, m)
  23.     return (m or n)<<(fact - 1)
  24.  
  25. def gcd3(m, n):
  26.     while m != 0 and n != 0:
  27.         if m > n:
  28.             m = m % n
  29.         else:
  30.             n = n % m
  31.     return (m + n)
  32.  
  33.  
  34. def gcd2(m, n):
  35.     factor = 1
  36.  
  37.     while m > 1 and n > 1:
  38.  
  39.         if m % 2 == 0 and n % 2 == 0:
  40.             factor *= 2
  41.             m /= 2
  42.             n /= 2
  43.             continue
  44.         elif m % 2 != 0 and n % 2 != 0:
  45.             m, n = abs(m - n) / 2, min(m, n)
  46.             continue
  47.  
  48.         if m % 2 == 0:
  49.             m /= 2
  50.  
  51.         if n % 2 == 0:
  52.             n /= 2
  53.  
  54.     if m == 0 or n == 0:
  55.         out = m + n
  56.     elif n == m:
  57.         out = n
  58.     elif m == 1 or n == 1:
  59.         out = 1
  60.  
  61.     return factor * out
  62.  
  63.  
  64. def gcd(m, n):
  65.     if m == 0:
  66.         return n
  67.  
  68.     if n == 0:
  69.         return m
  70.  
  71.     if m == n:
  72.         return n
  73.  
  74.     if m == 1 or n == 1:
  75.         return 1
  76.  
  77.     if m % 2 == 0 and n % 2 == 0:
  78.         return 2 * gcd(m / 2, n / 2)
  79.  
  80.     if m % 2 == 0 and n % 2 != 0:
  81.         return gcd(m / 2, n)
  82.  
  83.     if n % 2 == 0 and m % 2 != 0:
  84.         return gcd(m, n / 2)
  85.  
  86.     if m % 2 != 0 and n % 2 != 0:
  87.         if n > m:
  88.             return gcd((n-m)/2, m)
  89.  
  90.         else:
  91.             return gcd((m-n)/2, n)
  92. '''
  93. import random
  94. import timeit
  95. import fractions
  96.  
  97. # for test in range(100):
  98. #     a, b = random.randint(0, 100), random.randint(0, 100)
  99. #     fa = gcd(a, b)
  100. #     fb = gcd2(a, b)
  101. #     assert fa == fb, 'Not ok'
  102.  
  103. number = 10 ** 5
  104. print timeit.timeit('gcd(a, b)', setup=s, number=number)
  105. print timeit.timeit('gcd2(a, b)', setup=s, number=number)
  106. print timeit.timeit('gcd3(a, b)', setup=s, number=number)
  107. print timeit.timeit('b_gcd(a, b)', setup=s, number=number)
  108. print timeit.timeit('fractions.gcd(a, b)', setup=s, number=number)
  109. print 'ok'
  110.  
Success #stdin #stdout 0.98s 12112KB
comments (?)
stdin 
Standard input is empty
stdout 
0.272146940231
0.252383947372
0.0654129981995
0.2320997715
0.068596124649
ok
https://ideone.com/Q1ozvb
language:
Python (cpython 2.7.16)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!