Modulo Calculator

Η απόκλιση μεταξύ των συμβάσεων modulo στα μαθηματικά και τον προγραμματισμό πηγάζει από τον τρόπο με τον οποίο χειρίζονται την ακέραια διαίρεση. Το μαθηματικό modulo χρησιμοποιεί διαίρεση με στρογγυλοποίηση προς τα κάτω (στρογγυλοποίηση προς το αρνητικό άπειρο), οπότε το πηλίκο του αρνητικού 7 δια του 3 στρογγυλοποιείται προς τα κάτω στο αρνητικό 3, δίνοντας υπόλοιπο αρνητικό 7 μείον 3 επί αρνητικό 3 ίσον 2. Το modulo προγραμματισμού χρησιμοποιεί διαίρεση με αποκοπή (στρογγυλοποίηση προς το μηδέν), οπότε το πηλίκο αποκόπτεται στο αρνητικό 2, δίνοντας υπόλοιπο αρνητικό 7 μείον 3 επί αρνητικό 2 ίσον αρνητικό 1.

Η Python χρησιμοποιεί αποκλειστικά το μαθηματικό modulo (με στρογγυλοποίηση προς τα κάτω), ταιριάζοντας με τη σύμβαση που αναμένεται στην αφηρημένη άλγεβρα και τη θεωρία αριθμών. Οι C, C++, Java, JavaScript, Go και Rust χρησιμοποιούν modulo με αποκοπή. Η Ruby και η Perl ακολουθούν τη συμπεριφορά της Python.

Αυτή η διάκριση έχει σημασία στον πραγματικό κώδικα: η μετατροπή μιας αρνητικής γωνίας στο εύρος 0-359 απαιτεί μαθηματικό modulo (το αρνητικό 90 mod 360 ισούται με 270), αλλά ο τελεστής ποσοστού της C δίνει αρνητικό 90, απαιτώντας χειροκίνητη ρύθμιση.

Η αριθμητική υπολοίπων αποτελεί τη βάση για εκπληκτικά πολλά συστήματα στον πραγματικό κόσμο:

• Η αριθμητική ρολογιών είναι βασισμένη σε modulo: 10 π.μ. συν 5 ώρες ισούται με 3 μ.μ., επειδή το 15 mod 12 ισούται με 3.
• Οι ημέρες της εβδομάδας επαναλαμβάνονται κυκλικά με modulo 7.
• Οι πίνακες κατακερματισμού (hash tables) χρησιμοποιούν modulo για την αντιστοίχιση κλειδιών σε δείκτες κάδων: hash(key) mod table_size.
• Τα κρυπτογραφικά αλγόριθμοι όπως το RSA βασίζονται εξ ολοκλήρου στον εκθετικό υπολογισμό modulo και στη δυσκολία εύρεσης αντιστρόφων modulo για μεγάλους πρώτους αριθμούς.
• Τα ψηφία ελέγχου ISBN και πιστωτικών καρτών χρησιμοποιούν πράξεις modulo για την ανίχνευση σφαλμάτων (το ISBN-13 χρησιμοποιεί mod 10, ο αλγόριθμος Luhn για πιστωτικές κάρτες).
• Οι κυκλικές δομές δεδομένων όπως οι κυκλικές μνήμες buffer χρησιμοποιούν modulo για την αναδίπλωση δεικτών πινάκων: next_index ίσον (current συν 1) mod buffer_size.

Aκόμη και απλές εργασίες, όπως ο προσδιορισμός αν ένας αριθμός είναι άρτιος (n mod 2 ίσον 0) ή η εξαγωγή του τελευταίου ψηφίου (n mod 10), βασίζονται στο modulo.

Η πράξη modulo επεκτείνεται φυσικά στους πραγματικούς αριθμούς χρησιμοποιώντας τον ίδιο τύπο: r ισούται με a μείον b επί floor(a δια του b). Για παράδειγμα, το 5.5 mod 2 ισούται με 1.5 επειδή το floor(5.5/2) ισούται με 2, και 5.5 μείον 2 επί 2 ισούται με 1.5.

Το modulo κινητής υποδιαστολής χρησιμοποιείται ευρέως στα γραφικά υπολογιστών για την αναδίπλωση υφών (texture wrapping, όπου το u mod 1.0 αντιστοιχίζει οποιαδήποτε συντεταγμένη στο εύρος 0 έως 1), την κανονικοποίηση γωνιών (το theta mod 360 διατηρεί τις γωνίες εντός μίας πλήρους περιστροφής) και την επεξεργασία σήματος για υπολογισμούς φάσης.

Σημαντικές οριακές περιπτώσεις:

• Το modulo με το μηδέν δεν ορίζεται και θα προκαλέσει σφάλματα διαίρεσης με το μηδέν σε οποιαδήποτε γλώσσα.
• Το modulo όπου ο διαιρετέος είναι μηδέν επιστρέφει πάντα μηδέν (το 0 mod b ισούται με 0 για οποιοδήποτε μη μηδενικό b).
• Όταν και τα δύο τελεστέα είναι θετικά και ο διαιρετέος είναι μικρότερος από τον διαιρέτη, το αποτέλεσμα ισούται με τον διαιρετέο (το 3 mod 7 ισούται με 3).

Αυτές οι ιδιότητες καθιστούν το modulo προβλέψιμο για θετικούς αριθμούς, αλλά απαιτούν προσεκτικό χειρισμό με αρνητικές ή δεκαδικές εισόδους.

Η πράξη modulo επιστρέφει το υπόλοιπο που απομένει μετά τη διαίρεση ενός ακέραιου με έναν άλλον, γραφόμενη ως a mod b ή a % b. Δεδομένου ενός διαιρετέου a και ενός μη μηδενικού διαιρέτη b, απαντά στην ερώτηση: αφού αφαιρεθούν όσα περισσότερα ακέραια αντίγραφα του b είναι δυνατόν από το a, τι απομένει;

Για παράδειγμα, 17 mod 5 = 2 επειδή το 5 χωράει στο 17 τρεις φορές (15), αφήνοντας 2. Σύμφωνα με το Wolfram MathWorld, η συνάρτηση modulo ορίζεται επίσημα ως το υπόλοιπο του a διαιρεμένου με το b, και ικανοποιεί πάντα τη σχέση 0 <= r < |b| υπό τη μαθηματική σύμβαση.

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

Για να υπολογίσετε το a mod b με το χέρι, χρησιμοποιήστε τον τύπο r = a - b * q, όπου q είναι το πηλίκο. Οι δύο συμβάσεις διαφέρουν μόνο ως προς τον τρόπο υπολογισμού του q. Το μαθηματικό modulo (με στρογγυλοποίηση προς τα κάτω) θέτει q = floor(a/b), στρογγυλοποιώντας προς το αρνητικό άπειρο· το modulo στυλ C (με αποκοπή) θέτει q = trunc(a/b), στρογγυλοποιώντας προς το μηδέν.

Αναλυτικά ανά περίπτωση:

• Για το 17 mod 5: floor(17/5) = 3, οπότε r = 17 - 5*3 = 2.
• Για το -7 mod 3 (μαθηματικό): floor(-7/3) = floor(-2.33) = -3, οπότε r = -7 - 3*(-3) = 2.
• Για το -7 % 3 (στυλ C): trunc(-2.33) = -2, οπότε r = -7 - 3*(-2) = -1.

Όπως σημειώνει η Ψηφιακή Βιβλιοθήκη Μαθηματικών Συναρτήσεων του NIST, η στρογγυλοποίηση προς τα κάτω και η αποκοπή συμπίπτουν για θετικά τελεστέα, γι' αυτό και οι δύο συμβάσεις συμφωνούν όταν το a και το b είναι θετικά.

Ο υπολογισμός του a mod b είναι μια διαδικασία τεσσάρων βημάτων. Ας εξετάσουμε το 23 mod 6.

• Βήμα 1: διαιρούμε, 23 / 6 = 3.833.
• Βήμα 2: παίρνουμε το πηλίκο ως ακέραιο αριθμό, floor(3.833) = 3.
• Βήμα 3: πολλαπλασιάζουμε ξανά, 3 * 6 = 18.
• Βήμα 4: αφαιρούμε, 23 - 18 = 5.

Άρα, 23 mod 6 = 5, και πράγματι 23 = 6*3 + 5. Για έναν αρνητικό διαιρετέο όπως το -23 mod 6 (μαθηματική σύμβαση), floor(-23/6) = floor(-3.833) = -4, οπότε -23 - 6*(-4) = -23 + 24 = 1.

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

Η αριθμητική υπολοίπων είναι ένα σύστημα αριθμητικής για ακέραιους αριθμούς όπου οι αριθμοί αναδιπλώνονται αφού φτάσουν σε μια σταθερή τιμή που ονομάζεται modulus. Δύο ακέραιοι a και b λέγεται ότι είναι ισότιμοι modulo n, γραφόμενο ως a ≡ b (mod n), όταν αφήνουν το ίδιο υπόλοιπο κατά τη διαίρεση με το n, ή ισοδύναμα όταν το n διαιρεί τη διαφορά τους.

Για παράδειγμα, 17 ≡ 5 (mod 12) επειδή και οι δύο αφήνουν υπόλοιπο 5 όταν διαιρούνται με το 12, γι' αυτό και μια ώρα 17:00 διαβάζεται ως 5 μ.μ. σε ένα ρολόι 12 ωρών.

Η Encyclopaedia Britannica περιγράφει την αριθμητική υπολοίπων ως αριθμητική σε ένα πεπερασμένο σύνολο υπολοίπων, η οποία επισημοποιήθηκε από τον Carl Friedrich Gauss στο έργο του Disquisitiones Arithmeticae το 1801. Οι σχέσεις ισοτιμίας διατηρούν την πρόσθεση και τον πολλαπλασιασμό, καθιστώντας τις τον αλγεβρικό πυρήνα της κρυπτογραφίας και των κωδίκων ανίχνευσης σφαλμάτων.

Το modulo εμφανίζεται πολύ συχνότερα απ' ό,τι οι περισσότεροι συνειδητοποιούν:

• Για να ελέγξετε αν ένας αριθμός είναι άρτιος, ελέγξτε n mod 2 == 0· για να εξαγάγετε το τελευταίο ψηφίο ενός ακέραιου, υπολογίστε n mod 10.
• Οι κυκλικές μνήμες buffer και οι κυκλικές ουρές αναδιπλώνουν τη θέση εγγραφής τους με index = (index + 1) mod capacity, ώστε ο δείκτης να μην ξεπερνά ποτέ το τέλος του πίνακα.
• Οι πίνακες κατακερματισμού (hash tables) αντιστοιχίζουν κλειδιά σε θύρες χρησιμοποιώντας hash mod table_size.
• Η μαθηματική διαχείριση χρόνου και ημερολογίου βασίζεται σε modulo: η ημέρα της εβδομάδας προχωρά κατά (day + shift) mod 7, και τα ρολόγια λειτουργούν με mod 12 ή mod 24.
• Τα ψηφία ελέγχου για ISBN-13 (mod 10) και αριθμούς δρομολόγησης τραπεζών, συν ο αλγόριθμος Luhn πίσω από την επικύρωση πιστωτικών καρτών, βασίζονται όλοι στο modulo για τον εντοπισμό τυπογραφικών λαθών.
• Στην κρυπτογραφία, ο εκθετικός υπολογισμός modulo τροφοδοτεί το RSA και τη ανταλλαγή κλειδιών Diffie-Hellman.

Το υπόλοιπο υπακούει σε αρκετές χρήσιμες αλγεβρικές ιδιότητες που απλοποιούν τους υπολογισμούς και τις αποδείξεις.

Οι επιμεριστικού τύπου κανόνες για τις ισοδυναμίες ορίζουν ότι (a + b) mod n = ((a mod n) + (b mod n)) mod n, και ομοίως (a * b) mod n = ((a mod n) * (b mod n)) mod n· αυτοί σας επιτρέπουν να μειώσετε μεγάλες ενδιάμεσες τιμές πριν από τον πολλαπλασιασμό, αποτρέποντας έτσι την υπέρβαση χωρητικότητας.

Βασικές ταυτότητες που πρέπει να θυμάστε:

• Εάν ο διαιρετέος είναι μικρότερος από τον διαιρέτη και οι δύο είναι θετικοί, το αποτέλεσμα είναι απλώς ο διαιρετέος, οπότε 3 mod 7 = 3.
• Ένας διαιρετέος ίσης με μηδέν δίνει πάντα μηδέν: 0 mod b = 0.
• Οποιοδήποτε πολλαπλάσιο του μέτρου δίνει μηδέν, οπότε 20 mod 5 = 0.
• Το αποτέλεσμα ενός mod b είναι πάντα αυστηρά μικρότερο από το |b| σύμφωνα με τον μαθηματικό συμβατικό κανόνα.

Αυτές οι ταυτότητες, οι οποίες καταγράφονται σε πηγές όπως η καταχώριση ισοδυναμίας του Wolfram MathWorld, καθιστούν τον υπολογισμό υπολοίπων γρήγορο και προβλέψιμο.

Προσέξτε αυτά τα συχνά σφάλματα:

• Η υπόθεση ότι κάθε γλώσσα επιστρέφει το ίδιο πρόσημο για αρνητικούς τελετέους. Το -7 % 3 της Python δίνει 2, αλλά η Java, η C και η JavaScript δίνουν -1, οπότε η αντιγραφή ενός τύπου μεταξύ γλωσσών χωρίς προσαρμογή μπορεί να εισαγάγει λεπτά σφάλματα, ειδικά στην τύλιξη γωνιών ή στο κατακερματισμό.
• Η προσπάθεια υπολογισμού υπολοίπου με μηδέν, η οποία είναι απροσδιόριστη και προκαλεί σφάλμα χρόνου εκτέλεσης σε κάθε γλώσσα· να επικυρώνετε πάντα ότι ο διαιρέτης δεν είναι μηδέν.
• Η σύγχυση ως προς την κατεύθυνση στρογγυλοποίησης του πηλίκου, ξεχνώντας ότι η διαίρεση με στρογγυλοποίηση προς τα κάτω και η αποκομμένη διαίρεση αποκλίνουν για τα αρνητικά.
• Η εφαρμογή ακέραιου υπολοίπου σε τιμές κινητής υποδιαστολής χωρίς να λαμβάνεται υπόψη η στρογγυλοποίηση μπορεί να παράγει μικρά σφάλματα· 5.5 mod 2 = 1.5 ακριβώς, αλλά η συσσωρευμένη μετατόπιση κινητής υποδιαστολής μπορεί να δώσει 1.4999999.
• Η χρήση του n mod 2 == 1 για τον εντοπισμό περιττών αριθμών αποτυγχάνει για τα αρνητικά σε αποκομμένες γλώσσες, όπου -3 % 2 = -1· δοκιμάστε το n mod 2 != 0 αντί αυτού.

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

• Το αποκομμένο υπόλοιπο (με το πρόσημο του διαιρετέου) χρησιμοποιείται από τις C, C++, C#, Java, JavaScript, Go, Rust και Swift, οπότε το -7 % 3 αποτιμάται σε -1 σε όλες αυτές.
• Το υπόλοιπο με στρογγυλοποίηση προς τα κάτω (με το πρόσημο του διαιρέτη, πάντα μη αρνητικό για θετικούς διαιρέτες) χρησιμοποιείται από τις Python, Ruby και Perl, οπότε το -7 % 3 αποτιμάται σε 2.

Ορισμένες γλώσσες παρέχουν και τα δύο: η Python διαθέτει το math.fmod για το αποκομμένο αποτέλεσμα τύπου C, και πολλές τυπικές βιβλιοθήκες εκθέτουν μια αποκλειστική συνάρτηση floor-mod όπως το Math.floorMod της Java, η οποία επιστρέφει 2 για το floorMod(-7, 3).

Κατά τη μεταφορά αριθμητικού κώδικα, να επιβεβαιώνετε πάντα ποια σύμβαση χρησιμοποιεί η γλώσσα-στόχος. Αυτή η αριθμομηχανή εμφανίζει τόσο το μαθηματικό αποτέλεσμα (με στρογγυλοποίηση προς τα κάτω) όσο και το αποτέλεσμα τύπου C (αποκομμένο) διπλά-διπλά, ώστε να μπορείτε να ταιριάξετε όποιο περιμένει το περιβάλλον σας.