Αλγόριθμοι Πολλαπλασιασμού (μέρος Ι)
Στο παρόν άρθρο θα μελετήσουμε τις διάφορες μεθόδους πολλαπλασιασμού που έχουν αναπτυχθεί από την αρχαιότητα μέχρι σήμερα σε διάφορους πολιτισμούς. Το άρθρο απαιτεί βασικές γνώσεις μαθηματικών Λυκείου, επομένως μπορεί να διαβαστεί από όλους τους φοιτητές ΑΕΙ, ΤΕΙ, ΕΑΠ, και από όσους μαθητές ενδιαφέρονται για παρόμοια θέματα.
Α. Κλασσική Μέθοδος
Η μέθοδος αυτή (στα αγγλικά αναφέρεται συνήθως ως Long Multiplication method ή standard algorithm) είναι ο κλασσικός αλγόριθμος πολλαπλασιασμού που μαθαίνουμε στο σχολείο. Λόγω της συμπυκνωμένης μορφής του και της ταχύτητας με την οποία δίνει το αποτέλεσμα, έχει ενσωματωθεί στα εκπαιδευτικά συστήματα των περισσότερων δυτικών χωρών. Μειονέκτημά του είναι ότι απαιτεί πολύ καλή γνώση του πολλαπλασιαστικού πίνακα των μονοψήφιων αριθμών (η γνωστή σε όλους "προπαίδεια"), κάτι που δυσκολεύει αρκετούς μαθητές.
Στην κλασσική μέθοδο, οι δύο αριθμοί τοποθετούνται ο ένας κάτω από τον άλλο και ξεκινώντας από δεξιά, πολλαπλασιάζουμε διαδοχικά το πρώτο ψηφίου του αριθμού που βρίσκεται κάτω, με τα ψηφία του αριθμού που βρίσκεται από πάνω. Στην πρώτη γραμμή των αποτελεσμάτων γράφουμε το αποτέλσμα κάθε πολλαπλασιασμού. Αν όμως το αποτέλεσμα είναι διψήφιος αριθμός, τότε γράφουμε μόνο τις μονάδες και κρατάμε ένα "κρατούμενο" (carrier) το οποίο προσθέτουμε στον επόμενο πολλαπλασιασμό που θα κάνουμε. Αν φτάσουμε στο τελευταίο ψηφίο του πάνω αριθμού, τότε γράφουμε ολόκληρο το αποτέλεσμα, ακόμη και αν αυτό είναι διψήφιος αριθμός. Στη συνέχεια επαναλαμβάνουμε τη διαδικασία με το δεύτερο ψηφίο του κάτω αριθμού, τοποθετώντας τα αποτελέσματα κάτω από τα αποτελέσματα του προηγούμενου ψηφίου, αλλά μια θέση δεξιότερα, κ.ο.κ., μέχρι να τελειώσουν όλα τα ψηφία. Στο τέλος προσθέτουμε όλα τα επιμέρους αποτελέσματα. Το παρακάτω παράδειγμα είναι ενδεικτικό. Στο παράδειγμα έχουμε τοποθετήσει και τα κρατούμενα (αν υπάρχουν) κάθε επιμέρους πολλαπλασιασμού. Τα αποτελέσματα του πρώτου ψηφίου (6) γράφονται με μπλε χρώμα, ενώ αυτά του δεύτερου με κόκκινο.
2 8 5
x 4 6
-----------------
1 7 51 30
1 1 34 20
-----------------
1 3 1 1 0
Εδώ δίνουμε και ένα δεύτερο παράδειγμα
4 1 2 7
x 3 5 1
-----------------------
4 1 2 7
2 0 6 3 5
1 2 3 8 1
-----------------------
1 4 4 8 5 7 7
Β. Μέθοδος Πλέγματος (Grid Method, Box Method)
Στη μέθοδο αυτή σπάμε τους αριθμούς σε μονάδες, δεκάδες, εκατοντάδες, κ.λ.π. Στη συνέχεια, τοποθετούμε τους αριθμούς που προκύπτουν σε ένα πλέγμα και συμπληρώνουμε τα τετράγωνα κάνοντας τους αντίστοιχους πολλαπλασιασμούς. Το αποτέλεσμα προκύπτει αν αθροίσουμε τους αριθμούς όλων των τετραγώνων.
Παρακάτω δίνουμε ένα απλό παράδειγμα για τον πολλαπλασιασμό 285x46:
Βήμα 1. Φτιάχνουμε το πλέγμα:
Βήμα 2. Βρίσκουμε τα γινόμενα:
Βήμα 3. Προσθέτουμε όλα τα επιμέρους γινόμενα: 8000+3200+200+1200+480+30 = 13110
Ας επαναλάβουμε τη διαδικασία για τον πολλαπλασιασμό 4127x351:
Το αποτέλεσμα είναι:
1200000+30000+6000+2100+200000+5000+1000+350+4000+100+20+7 =
1448577
Ουσιαστικά το πρώτο παράδειγμα μπορεί να αναλυθεί ως εξής:
(200+80+5)x(40+6) = 200x40 + 200x6 + 80x40 + 80x6 + 5x40 + 5x6 = 13110.
Ομοίως μπορούμε να δουλέψουμε και στο δεύτερο παράδειγμα. Επομένως, είναι προφανές ότι η μέθοδος αυτή χρησιμοποιεί την επιμεριστική ιδιότητα και είναι απλούστερη από την κλασσική μέθοδο, αλλά πιο αργή και χρειάζεται περισσότερο χώρο. Για να πολλαπλασιάσουμε δεκαδικούς αριθμούς, σπάμε τα δεκαδικά μέρη σε δέκατα, εκατοστά κ.λ.π. και ακολουθούμε παρόμοια διαδικασία. Παρακάτω παρουσιάζουμε τον πολλαπλασιασμό 5.8x18.2:
Το αποτέλεσμα δίνεται από το άθροισμα 15+0.5+0.25+2.4+0.08+0.04 = 18.27.
Η μέθοδος αυτή χρησιμοποιείται στο εκπαιδευτικό σύστημα της Ουαλίας και της Αγγλίας από το 1990. Πολλοί πιστεύουν ότι, λόγω της απλότητάς της, ίσως θα έπρεπε να αντικαταστήσει την κλασσική μέθοδο στην εκπαιδευτική διαδικασία. Άλλωστε, με την εισαγωγή των Η/Υ και των κινητών στην καθημερινότητα, πολύ σπάνια οι μαθητές θα χρειαστεί να κάνουν πολλαπλασιασμούς με το χέρι. Επιπλέον, η μέθοδος αυτή γίνεται πιο εύκολα κατανοητή από τους μαθητές λόγω της άμεσης ερμηνείας της, μέσω της επιμεριστικής ιδιότητας.
Γ. Μέθοδος με Κόσκινο
Πρόκειται για έναν από τους παλαιότερους αλγορίθμους πολλαπλασιασμού που χρησιμοποιήθηκε σε διάφορους πολιτισμούς και είναι γνωστός με πολλά και διαφορετικά ονόματα (lattice multiplication, gelusia multiplication, sieve multiplication, shabakh, venetian squares, Hindu lattice, κ.λ.π.). Η μέθοδος πλέγματος, αποτελεί τη βάση της συγκεκριμένης τεχνικής ενώ, όπως υποδηλώνει και το όνομά της (shabakh = δίκτυο, lattice=πλέγμα, sieve=κόσκινο, κ.λ.π.), καί σε αυτή την περίπτωση χρησιμοποιείται ένα πλέγμα στο οποίο τοποθετούνται βοηθητικοί αριθμοί. Ας δούμε μερικά παραδείγματα ξεκινώντας με τον πολλαπλασιασμό 285x46
Βήμα 1
Δημιουργούμε έναν μικρό πίνακα (πλέγμα - κόσκινο) με δύο γραμμές και 3 στήλες γράφοντας πάνω από κάθε στήλη τα ψηφία του αριθμού 285 και δίπλα σε κάθε γραμμή τα ψηφία του αριθμού 46. (Θα μπορούσαμε βέβαια να το κάνουμε και ανάποδα) Χωρίζουμε κάθε τετράγωνο σε δύο μέρη φέρνοντας τη διαγώνιο:
Βήμα 2
Στη συνέχεια εκτελούμε τους πολλαπλασιασμούς μεταξύ όλων των δυνατών συνδυασμών ψηφίων του πρώτου (μπλε) και του δεύτερου (κόκκινο) αριθμού. Το αποτέλεσμα το βάζουμε στο αντίστοιχο τετραγωνάκι, προσέχοντας ώστε οι δεκάδες να μπουν στο πάνω αριστερά τρίγωνο και οι μονάδες στο κάτω δεξιά. Για παράδειγμα πολλαπλασιάζοντας τις μονάδες του πρώτου αριθμού με αυτές του δεύτερου παίρνουμε τον αριθμό 5x4 = 20, o οποίος τοποθετείται στο πάνω δεξιά τετράγωνο.
Βήμα 3
Τέλος αθροίζουμε τα ψηφία κατά μήκος όλων των "διαγώνιων" ζωνών που φαίνονται στο σχήμα, ξεκινώντας από την κάτω δεξιά ζώνη (κίτρινη) και συνεχίζοντας προς τα πάνω και αριστερά. Αν το αποτέλεσμα είναι διψήφιος αριθμός, τότε γράφουμε μόνο τις μονάδες και κρατάμε τις δεκάδες ως κρατούμενο για την επόμενη πρόσθεση.
Όπως φαίνεται στο παραπάνω σχήμα, δημιουργούνται 3+2=5 διαγώνιες ζώνες.
Η πρώτη περιέχει τον αριθμό 0.
Η δεύτερη περιέχει τους αριθμούς 0, 3, 8, άρα δίνει αποτέλεσμα 11. Γράφουμε το έχουμε κρατούμενο ίσο με 1.
Η τρίτη ζώνη περιέχει τους αριθμούς 2, 2, 4, 2, άρα (μαζί με το κρατούμενο) δίνει αποτέλεσμα 11.
Η τέταρτη ζώνη περιέχει τους αριθμούς 3, 8, 1, άρα (μαζί με το κρατούμενο) δίνει αποτέλεσμα 13.
Τέλος, η πέμπτη ζώνη περιέχει μόνο τον αριθμό 0, άρα δίνει αποτέλεσμα 1 (όσο το κρατούμενο).
Για να γράψουμε το αποτέλεσμα ξεκινάμε από τον πάνω δεξιά αριθμό και συνεχίζουμε με φορά αντίστροφη των δεικτών του ρολογιού. Έτσι προκύπτει ο αριθμός 13110!
Ας δούμε και τον πολλαπλασιασμό 4127x351 = 1448577.
Παρότι δεν είναι ακριβώς γνωστό πού αναπτύχθηκε η συγκεκριμένη μέθοδος, υπάρχουν αναφορές της τόσο σε αραβικά όσο και ινδικά κείμενα. Επίσης είναι γνωστό ότι χρησιμοποιήθηκε (αρκετά μεταγενέστερα) στην Οθωμανική αυτοκρατορία. Πιστεύεται ότι στην Ευρώπη (Ιταλία) εισήχθει από τον αραβικό κόσμο. Σε αυτό συνηγορεί το ιταλικό όνομο (gelusia) που έχει παρόμοια έννοια με τον αραβικό όρο (shabakh) που χρησιμοποιείται γι αυτή τη μέθοδο. Κατά μια εκδοχή, ο Ιταλός μαθηματικός Fibonacci ήταν ο πρώτος που εισήγαγε τη μέθοδο στην Ευρώπη, αν και η αναφορά του Fibonacci στο βιβλίο του "Liber Abaci" του 1202 αφορά μια παρόμοια τεχνική (όχι ακριβώς την ίδια). Άλλοι ερευνητές, δεν αποδίδουν στο Fibonacci το γεγονός.
Η συσκευή "Napier bones" (φωτογραφία) του άγγλου μαθηματικού Napier, που εκτελούσε αυτόματα αριθμητικές πράξεις (1617) είναι γνωστό ότι χρησιμοποιούσε τη μέθοδο του κόσκινου για να εκτελέσει πολλαπλασιασμό.
Χρησιμοποιώντας την συγκεκριμμένη μέθοδο, μπορούμε να πολλαπλασιάσουμε και δεκαδικούς αριθμούς. Η διαδικασία περιγράφεται παρακάτω:
Βήμα 1.
Εφαρμόζουμε τη μέθοδο του κόσκινου κανονικά αγνοόντας (αρχικά) τις υποδιαστολές:
Βήμα 2.
Στη συνέχεια, στις θέσεις των υποδιαστολών τραβάμε μια κατακόρυφη και μια οριζόντια γραμμή αντίστοιχα. Σημειώνουμε το σημείο στο οποίο συναντιούνται (τέμνονται).
Βήμα 3.
Από το σημείο τομής των δύο ευθειών τραβάμε μια διαγωνία γραμμή, μέχρι να βγούμε "έξω" από το κόσκινο. Εκεί τοποθετούμε την υποδιαστολή του γινομένου.
Επομένως το αποτέλεσμα της πράξης είναι ίσο με 18.27.
Το άρθρο συνεχίζεται εδώ.
Comments