Implementation of Euclid's algorithm in PythonsteemCreated with Sketch.

in #python7 years ago (edited)

Euklid.png
First of all let's have a quick look at the definition of the Euclidean algorithm from Wikipedia:

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an
efficient method for computing the greatest common divisor (GCD) of
two numbers, the largest number that divides both of them without
leaving a remainder. It is named after the ancient Greek mathematician
Euclid, who first described it in Euclid's Elements (c. 300 BC). It is
an example of an algorithm, a step-by-step procedure for performing a
calculation according to well-defined rules, and is one of the oldest
algorithms in common use.

So, basically we can compute the GCD(A,B) of two natural numbers A and B ≠ 0 using recursion:

  1. If A = 0, GCD(A,B) = B | STOP
  2. If B = 0, GCD(A,B) = A | STOP
  3. R := A mod B
  4. GCD(A,B) = GCD(B,R)

The implementation in Python is quite easy:

def gcd(a, b):
    if a == 0:  #1
        return b

    if b == 0:  #2
        return a

    r = a % b  #3

    return gcd(b, r)  #4

That's it, but there's to mention that some more efficient algorithms for this purpose have been found.

Image

Sort:  

Congratulations @luj1! You have completed some achievement on Steemit and have been rewarded with new badge(s) :

Award for the number of comments

Click on any badge to view your own Board of Honor on SteemitBoard.
For more information about SteemitBoard, click here

If you no longer want to receive notifications, reply to this comment with the word STOP

By upvoting this notification, you can help all Steemit users. Learn how here!

Congratulations! This post has been upvoted from the communal account, @minnowsupport, by Lucas from the Minnow Support Project. It's a witness project run by aggroed, ausbitbank, teamsteem, theprophet0, someguy123, neoxian, followbtcnews, and netuoso. The goal is to help Steemit grow by supporting Minnows. Please find us at the Peace, Abundance, and Liberty Network (PALnet) Discord Channel. It's a completely public and open space to all members of the Steemit community who voluntarily choose to be there.

If you would like to delegate to the Minnow Support Project you can do so by clicking on the following links: 50SP, 100SP, 250SP, 500SP, 1000SP, 5000SP.
Be sure to leave at least 50SP undelegated on your account.