Τμήμα Μαθηματικών

Πληροφορική Ι

Εβδομάδα 11 · Ευκλείδειος Αλγόριθμος, Ακριβής Υπολογισμός, Συνεχή Κλάσματα

(Οδηγίες χρήσης του διαδραστικού κώδικα: δείτε την αρχική σελίδα.)

1 Ευκλείδειος Αλγόριθμος και Ακριβής (Συμβολικός) Υπολογισμός

1.1 Ο Ευκλείδειος αλγόριθμος

Ο αλγόριθμος του Ευκλείδη υπολογίζει τον Μέγιστο Κοινό Διαιρέτη (ΜΚΔ) δύο ακεραίων, στηριζόμενος στην παρατήρηση ότι \(\gcd(x, y) = \gcd(y, x \bmod y)\), με βασική περίπτωση \(\gcd(x, 0) = x\) (τον είδαμε αναδρομικά στην Εβδομάδα 9):

Κάθε βήμα αντικαθιστά το ζεύγος (x, y) με (y, x % y) — οι αριθμοί μικραίνουν γρήγορα μέχρι το y να μηδενιστεί:

Γεωμετρικά, ο \(\gcd(a,b)\) είναι η πλευρά του μεγαλύτερου τετραγώνου με το οποίο μπορούμε να «στρώσουμε» πλήρως ένα ορθογώνιο \(a \times b\). Ο αλγόριθμος κόβει επαναληπτικά το μεγαλύτερο δυνατό τετράγωνο (γράφημα με το matplotlib):

Σημείωση

Η πρότυπη βιβλιοθήκη της Python περιλαμβάνει ήδη μια βελτιστοποιημένη υλοποίηση, την math.gcd(x, y). Το να ξέρουμε να γράψουμε τον αλγόριθμο εμείς οι ίδιοι δεν είναι άσκοπο όμως: μας βοηθά να καταλάβουμε γιατί δουλεύει, και είναι απαραίτητο όποτε χρειαζόμαστε μια παραλλαγή του — όπως η επεκτεταμένη εκδοχή που ακολουθεί.

1.2 Ο επεκτεταμένος Ευκλείδειος αλγόριθμος (extended gcd)

Το ταυτοτικό του Bézout λέει ότι, για οποιουσδήποτε ακέραιους \(a, b\), υπάρχουν ακέραιοι \(x, y\) (όχι απαραίτητα θετικοί) τέτοιοι ώστε

\[ a x + b y = \gcd(a, b). \]

Ο επεκτεταμένος Ευκλείδειος αλγόριθμος δεν υπολογίζει μόνο τον \(\gcd(a,b)\), αλλά και συγκεκριμένα \(x, y\) που ικανοποιούν την παραπάνω σχέση — “επεκτείνοντας” κάθε αναδρομική κλήση με τους συντελεστές της:

Αυτό δεν είναι απλώς μια θεωρητική περιέργεια: είναι το βασικό εργαλείο για τον υπολογισμό του αντιστρόφου modulo \(n\) (κρίσιμο στην κρυπτογραφία δημοσίου κλειδιού, π.χ. RSA), αφού αν \(\gcd(a, n) = 1\), τότε η ίδια εξίσωση \(ax + ny = 1\) δίνει \(ax \equiv 1 \pmod{n}\) — δηλαδή το \(x\) (αναχθέν modulo \(n\)) είναι ακριβώς ο πολλαπλασιαστικός αντίστροφος του \(a\).

1.3 Ακριβής (συμβολικός) υπολογισμός έναντι float

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

Οι ακέραιοι της Python δεν έχουν αυτό το πρόβλημα: κανένα όριο μεγέθους, και κάθε πράξη πάνω τους (πρόσθεση, πολλαπλασιασμός, ο Ευκλείδης) είναι απόλυτα ακριβής — όσο μεγάλοι κι αν γίνουν οι αριθμοί:

Αυτού του είδους ο υπολογισμός λέγεται ακριβής ή συμβολικός (exact/symbolic computation), σε αντιδιαστολή με τον αριθμητικό υπολογισμό κινητής υποδιαστολής (numerical/floating-point computation) της προηγούμενης εβδομάδας, όπου δεχόμαστε εξαρχής ότι θα υπάρχει ένα (μικρό, ελπίζουμε) σφάλμα στρογγύλευσης.

Η ίδια ιδέα επεκτείνεται και στα κλάσματα, με το module fractions της πρότυπης βιβλιοθήκης: το Fraction αναπαριστά ρητούς αριθμούς ως ζεύγη (αριθμητής, παρονομαστής) αντί για δεκαδικό ανάπτυγμα, οπότε οι πράξεις είναι πάντα ακριβείς:

2 Συνεχή Κλάσματα (Continued Fractions)

2.1 Τι είναι ένα συνεχές κλάσμα

Ένα συνεχές κλάσμα (continued fraction) εκφράζει έναν πραγματικό αριθμό στη μορφή

\[ x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cdots}}}, \]

όπου το \(a_0\) είναι ακέραιος και τα \(a_1, a_2, a_3, \ldots\) θετικοί ακέραιοι· συμβολίζουμε αυτό συνοπτικά \(x=[a_0; a_1, a_2, \ldots]\). Κάθε ρητός έχει συνεχές κλάσμα με πεπερασμένο πλήθος όρων, ενώ κάθε άρρητος με άπειρο πλήθος.

2.2 Υπολογισμός του συνεχούς κλάσματος ενός ρητού

Για έναν ρητό \(p/q\): \(a_0 = \lfloor p/q \rfloor\), και μετά συνεχίζουμε με το αντίστροφο του υπολοίπου. Δείτε πόσο μοιάζει με τον Ευκλείδειο αλγόριθμο παραπάνω — είναι στην ουσία ο ίδιος αλγόριθμος, απλώς καταγράφουμε το πηλίκο a σε κάθε βήμα, αντί να κρατάμε μόνο το τελευταίο μη μηδενικό υπόλοιπο:

Αντίστροφα, δεδομένων των όρων, ανακατασκευάζουμε τον ακριβή ρητό δουλεύοντας από το τέλος προς την αρχή, με Fraction όπως παραπάνω, για απόλυτη ακρίβεια:

2.3 Άπειρα συνεχή κλάσματα: οκνηρή αποτίμηση (lazy evaluation) με γεννήτριες

Ένας άρρητος έχει άπειρους όρους — δεν χωράνε σε καμία λίστα. Όπως και με την άπειρη ακολουθία Fibonacci στην Εβδομάδα 9, η λύση είναι μια γεννήτρια (generator): παράγουμε τους όρους έναν-έναν, “τεμπέλικα” (lazily), μόνο όσους χρειαζόμαστε. Το \(\sqrt{2}\) έχει το εντυπωσιακά απλό, περιοδικό \(\sqrt{2}=[1;2,2,2,\ldots]\):

Κόβοντας ένα άπειρο συνεχές κλάσμα στους πρώτους \(n\) όρους παίρνουμε μια συγκλίνουσα (convergent) — μια ρητή προσέγγιση που βελτιώνεται όσο αυξάνουμε το \(n\), και μάλιστα είναι η καλύτερη δυνατή ρητή προσέγγιση για το μέγεθος του παρονομαστή της:

Με μόλις \(7\) όρους, η συγκλίνουσα 239/169 προσεγγίζει το \(\sqrt{2}\) με σφάλμα μικρότερο από \(10^{-5}\) — και χωρίς ποτέ να αποθηκεύσουμε μια άπειρη ακολουθία, χάρη στην οκνηρή αποτίμηση: η γεννήτρια sqrt2_continued_fraction() “ξέρει” πώς να συνεχίσει επ’ άπειρον, αλλά υπολογίζει κάθε επόμενο όρο μόνο όταν της το ζητήσουμε ρητά με next().

Το σφάλμα κάθε συγκλίνουσας, σε λογαριθμικό άξονα — μια σχεδόν ευθεία γραμμή, δηλαδή εκθετικά γρήγορη σύγκλιση:

3 Σύνοψη

Σε αυτή την εβδομάδα είδαμε:

Τον αλγόριθμο του Ευκλείδη, και μια επεκτεταμένη εκδοχή του που υπολογίζει επιπλέον συντελεστές μαζί με τον ΜΚΔ.
Ακριβή (συμβολικό) υπολογισμό: απεριόριστους ακέραιους, και το module fractions.
Έναν αλγόριθμο υπολογισμού που είναι, δομικά, σχεδόν πανομοιότυπος με τον αλγόριθμο του Ευκλείδη — ίδια λογική, διαφορετική καταγραφή.
Οκνηρή αποτίμηση (lazy evaluation) με γεννήτριες: παραγωγή όρων μιας άπειρης ακολουθίας “κατ’ απαίτηση”, μόνο όσων χρειάζονται κάθε φορά.

⤺ Πίσω στην αρχική σελίδα / πρόγραμμα μαθήματος · Διαφάνειες αυτής της εβδομάδας