Παράδειγμα 3.8.2, Υπολογισμός του μέγιστου κοινού διαιρέτη (εκτός ύλης)

Ένα ιστορικό πρόβλημα είναι η εύρεση του μέγιστου κοινού διαιρέτη (μκδ) δύο ακεραίων αριθμών. Ο αλγόριθμος εύρεσης του μκδ ανήκει στον Ευκλείδη. Ωστόσο η υλοποίηση και αυτού του αλγορίθμου μπορεί να γίνει κατά πολλούς τρόπους. Στη συνέχεια δίνεται ένας πρώτος αλγόριθμος για τον υπολογισμό του μκδ δύο ακεραίων x και y. Η μέθοδος αυτή είναι αρκετά αργή (και δεν στηρίζεται στον αλγόριθμο του Ευκλείδη), αλλά απλώς δίνεται για να διαφανεί η βελτίωση στην επίδοση από τους επόμενους αλγορίθμους. Ουσιαστικά λαμβάνει το μικρότερο από τους δύο ακεραίους, τον z, και εξετάζει με τη σειρά όλους τους ακεραίους ξεκινώντας από τον z και μειώνοντας συνεχώς κατά μία μονάδα μέχρι και οι δύο αριθμοί, x και y, να διαιρούνται από τη νέα τιμή του z.

Αλγόριθμος Μέγιστος_Κοινός_Διαιρέτης
 Δεδομένα // x,y //
 Αν x < y τότε
    z ← x
 αλλιώς
    z ← y
 Τέλος_αν
 Όσο (x mod z ≠ 0) ή (y mod z ≠ 0) επανάλαβε
      z ← z-1
 Τέλος_επανάληψης
 Αποτελέσματα // z //
 Τέλος Μέγιστος_Κοινός_Διαιρέτης

Η επόμενη μέθοδος για την εύρεση του μκδ αποδίδεται στον Ευκλείδη, και προφανώς βελτιώνει την προηγούμενη εκδοχή, επειδή δεν εξετάζει με τη σειρά όλους τους ακεραίους.

Αλγόριθμος Ευκλείδης
 Δεδομένα // x,y //
 z ← y
 Όσο z ≠ 0 επανάλαβε
     z ← x mod y
     x ← y
     y ← z
 Τέλος_επανάληψης
 Αποτελέσματα // x //
 Τέλος Ευκλείδης

Για καλύτερη κατανόηση της μεθόδου, ας παρακολουθήσουμε πώς ο αλγόριθμος αυτός βρίσκει το μκδ των αριθμών 150 και 35. Ο επόμενος πίνακας δείχνει τις τιμές των μεταβλητών z, x και y, κατά τη διάρκεια των επαναλήψεων. Δηλαδή, πριν την έναρξη της επαναληπτικής δομής οι αρχικές τιμές των x και y είναι 150 και 35 (όπως φαίνεται στη δεύτερη γραμμή του πίνακα). Ο αλγόριθμος σταματά όταν γίνει 0 η τιμή του z, οπότε ο μκδ είναι η τιμή του x, δηλαδή το 5.

Ωστόσο η μέθοδος του Ευκλείδη μπορεί να υλοποιηθεί και με έναν εναλλακτικό αναδρομικό τρόπο, που δίνεται στη συνέχεια. Η τρίτη αυτή εκδοχή είναι πολύ απλή στον προγραμματισμό και την κατανόησή της.

Αλγόριθμος Ευκλείδης
 Δεδομένα // x, y //
 Αν y = 0 τότε
    z ← x
 αλλιώς
    z ← Ευκλείδης(y, x mod y)
 Τέλος_αν
 Αποτελέσματα // z //
 Τέλος Ευκλείδης