Skip to content

Instantly share code, notes, and snippets.

@javierhonduco

javierhonduco/gcd_limited_ops.py

Created March 30, 2016 07:30
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save javierhonduco/8be79ab8e1d6e57529293809814ce331 to your computer and use it in GitHub Desktop.
Save javierhonduco/8be79ab8e1d6e57529293809814ce331 to your computer and use it in GitHub Desktop.
Download ZIP
GCD computing without modulo neither division ops
Raw
gcd_limited_ops.py
# computes the greatest common divisor
# with a small subset of math operations
# that does not include `division` or `modulo`
def gcd(a, b):
while b>0:
c = a
a = b
while(c >= b):
c -= b
b = c
return a
if __name__ == '__main__':
from fractions import gcd as gcd_
for i in xrange(20):
print gcd(13, i), gcd_(13, i)
print gcd(20, i), _(20, i)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment