Skip to content

Instantly share code, notes, and snippets.

@berdario

berdario/gcd.factor

Created December 16, 2013 17:58
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 berdario/7991399 to your computer and use it in GitHub Desktop.
Save berdario/7991399 to your computer and use it in GitHub Desktop.
Download ZIP
Both snippets are mostly the same: the factor solution is a recursive word, while the python one has an imperative iteration. The complexity of the function (in number of steps) is linear with the size of the smaller input
Raw
gcd.factor
: gcd ( a b -- c ) over zero? [ nip ] [ over mod swap gcd ] if ;
Raw
gcd.py
def gcd(a, b):
while b:
a, b = b, a % b
return a
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment