Ευκλείδεια διαίρεση

Στα μαθηματικά, Ευκλείδεια διαίρεση (ή αλγοριθμική διαίρεση) είναι ένας οποιοσδήποτε αλγόριθμο για την διαίρεση ενός ακεραίου αριθμού με έναν άλλον. Πιο συγκεκριμένα, ένας αλγόριθμος που έχει ως εισόδους δύο ακεραίους τον  (τον διαιρετέο) και τον διαιρέτη , και που επιστρέφει δύο άλλους ακεραίους, το πηλίκο  και το υπόλοιπο , ώστε
 και .
Για παράδειγμα, η Ευκλείδεια διαίρεση του  με το  δίνει ως αποτέλεσμα το πηλίκο  και υπόλοιπο , καθώς .

Το θεώρημα της διαίρεσης λέει ότι για δοσμένα  και , το πηλίκο  και το υπόλοιπο  υπάρχουν και είναι μοναδικά. Ο πιο κοινός αλγόριθμος για την διαίρεση είναι η κάθετη διαίρεση, αλλά υπάρχουν και άλλοι. 

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

 Παραδείγματα 
 Η Ευκλείδεια διαίρεση του  με το  δίνει ως αποτέλεσμα το πηλίκο  και υπόλοιπο , καθώς .
 Η Ευκλείδεια διαίρεση του  με το  δίνει ως αποτέλεσμα το πηλίκο  και υπόλοιπο , καθώς .

Και με αρνητικούς αριθμούς
 Η Ευκλείδεια διαίρεση του  με το  δίνει ως αποτέλεσμα το πηλίκο  και υπόλοιπο , καθώς .
 Η Ευκλείδεια διαίρεση του  με το  δίνει ως αποτέλεσμα το πηλίκο  και υπόλοιπο , καθώς .
 Η Ευκλείδεια διαίρεση του  με το  δίνει ως αποτέλεσμα το πηλίκο  και υπόλοιπο , καθώς .

 Θεώρημα διαίρεσης 

 Απόδειξη 
Η απόδειξη χωρίζεται σε δύο τμήματα, την ύπαρξη του πηλίκου και του υπολοίπου, και την μοναδικότητά τους. 

 Παραδείγματα αλγορίθμων 

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

 Επαναλαμβανόμενη αφαίρεση 

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

pair<int, int> euclidean_division(int D, int d) {
   int P = 0;
   int u = D;
   while (u > d) {
      P = P + 1;
      u = u - d;
   }
   return {P, u};
}

 Κάθετη διαίρεση 

Η κάθετη διαίρεση που μαθαίνουμε στο σχολείο είναι πολύ πιο γρήγορη καθώς χρειάζεται  πράξεις. Ο παρακάτω κώδικας δίνει μία υλοποίηση.

pair<int, int> euclidean_division(int D, int d) {
   int P = 0;
   int pow10 = 1;
   while (d * pow10 <= D) pow10 *= 10; 
   int u = D;
   while (u >= d) {
      int digit = 0;
      while ((digit + 1) * pow10 * d <= u) {
         digit = digit + 1;
      }
      u -= digit * pow10 * d;
      P += digit * pow10;
      pow10 /= 10;
   }
   return {P, u};
}

 Δείτε επίσης 
 Διαίρεση
 Κάθετη διαίρεση

 Σημειώσεις 

 Παραπομπές 

Κατηγορία:Θεωρία αριθμών