Αλγόριθμοι Πολλαπλασιασμού (μέρος ΙΙ)
Το παρόν άρθρο είναι η συνέχεια του παλαιότερου άρθρου όπου αναφερθήκαμε στις σημαντικότερες μεθόδους πολλαπλασιασμού που έχουν αναπτυχθεί από την αρχαιότητα μέχρι σήμερα σε διάφορους πολιτισμούς. Το άρθρο απαιτεί βασικές γνώσεις μαθηματικών Λυκείου, επομένως μπορεί να διαβαστεί από όλους τους φοιτητές ΑΕΙ, ΤΕΙ, ΕΑΠ, και από όσους μαθητές ενδιαφέρονται για παρόμοια θέματα.
Δ. Κινέζικος Πολλαπλασιασμός (με γραμμές)
Μια παραλλαγή της μεθόδου Γ (με κόσκινο) αποτελεί η μέθοδος πολλαπλασιασμού με γραμμές (ξυλάκια) ή κινέζικη μέθοδος όπως έχει γίνει πιο γνωστή. Η διαδικασία εδώ όμως είναι αρκετά πιο χρονοβόρα, αν οι αριθμοί είναι μεγάλοι. Επίσης χρειάζεται περισσότερο χώρο. Το πλεονέκτημα της μεθόδου είναι ότι δεν χρειάζεται κανέναν πίνακα πολλαπλασιασμού (προπαίδεια) για να δουλέψει, σε αντίθεση με την μέθοδο με κόσκινο ή την κλασσική μέθοδο. Το μόνο που απαιτείται είναι η γνώση της πρόσθεσης και η ικανότητα απαρίθμησης. Ας δούμε το παράδειγμα του πολλαπλασιασμού 285x46:
Βήμα 1:
Τοποθετούμε τον ένα αριθμό κατακόρυφα και τον άλλο οριζόντια όπως στο παρακάτω σχήμα (παρόμοια με τη μέθοδο με κόσκινο). Στη συνέχεια σχεδιάζουμε οριζόντιες και κατακόρυφες γραμμές ίσες με τα ψηφία των αριθμών. (Εναλλακτικά μπορούν να χρησιμοποιηθούν ξυλάκια) Δείτε το σχήμα:
Βήμα 2:
Βρίσκουμε όλα τα σημεία τομής των ευθειών και τα σημειώνουμε με κουκίδες.
Βήμα 3:
Απαριθμούμε όλα τα σημεία που βρίσκονται στις διαγωνίους του σχήματος (όπως με τη μέθοδο με κόσκινο), ξεκινώντας από την ομάδα των κάτω δεξιά σημείων. Γράφουμε από κάτω μόνο τις μονάδες του αποτελέσματος και μεταφέρουμε τις δεκάδες (ως κρατούμενο) στην απαρίθμηση των σημείων της επόμενης διαγωνίου. Στην τελευταία ομάδα (πάνω αριστερά) γράφουμε και τις δεκάδες και τις μονάδες του αποτελέσματος. Όπως φαίνεται στο σχήμα το αποτέλεσμα είναι ίσο με 13110.
Ε. Αιγυπτιακός Πολλαπλασιασμός (Ρώσικος πολλαπλασιασμός ή πολλαπλασιασμός του χωρικού)
Πρόκειται για μια από τις αρχαιότερες μεθόδους πολλαπλασιασμού, για την οποία γνωρίσουμε ότι ήταν σε χρήση στην αρχαία Αίγυπτο. Συνήθως καλείται αιγυπτιακός πολλαπλασιασμός, αλλά είναι επίσης γνωστός ως Αιθιοπικός πολλαπλασιασμός, πολλαπλασιασμός του χωρικού ή ρώσικος πολλαπλασιασμός. Το βασικό του χαρακτηριστικό είναι ότι δεν χρησιμοποιεί κανέναν πολλαπλασιαστικό πίνακα. Απαιτεί μόνο γνώση της πρόσθεσης, του πολλαπλασιασμού με το 2 και της διαίρεσης με το 2.
Η μέθοδος αναλύει τον έναν από τους δύο αριθμούς σε άθροισμα δυνάμεων του 2 κάνοντας διαδοχικές διαιρέσεις, ενώ ο δεύτερος αριθμός πολλαπλασιάζεται με το δύο αντίστοιχες φορές. Αυτή η διαδικασία βοηθούσε πολύ, επειδή οι αρχαίοι Αιγύπτιοι είχαν πίνακες με τις δυνάμεις του δύο και έτσι μπορούσαν να κάνουν την ανάλυση σχετικά εύκολα. Επίσης γνώριζαν από εμπειρία ότι η ανάλυση ενός αριθμού σε αθροίσματα δυνάμεων του δύο γίνεται με μοναδικό τρόπο. Μπορούμε να πούμε ότι ο αιγυπτιακός πολλαπλασιασμός είναι ταυτόσημος με τον κλασσικό αλγόριθμο πολλαπλασιασμού στο δυαδικό σύστημα. Επειδή ακριβώς το δυαδικό σύστημα αποτελεί τη βάση της συγκεκριμένης μεθόδου, είναι αναμενόμενο ότι χρησιμοποιείται ευρέως σε ψηφιακά κυκλώματα. Η μέθοδος μπορεί να δωθεί σε δύο διαφορετικές μορφές. Η πρώτη βασίζεται στην αρχαία αιγυπτιακή τεχνική (με σύγχρονο συμβολισμό) ενώ η δεύτερη είναι η μορφή που συνήθως αναφέρεται ως ρώσικη μέθοδος ή μέθοδος του χωρικού.
Ας δούμε ένα παράδειγμα (285x46) με βάση την αρχαία αιγυπτιακή μέθοδο:
Βήμα 1: Επιλέγουμε τον αριθμό που θα αναλύσουμε ως άθροισμα δυνάμεω του 2. Στο παρακάτω παράδειγμα επιλέγουμε τον 46. Γράφουμε τους αριθμούς 1 και 285 τον ένα δίπλα στον άλλο, έτσι ώστε να σχηματίσουν δύο στήλες. Στη συνέχεια πολλαπλασιάζουμε επί 2 και τους δύο αριθμούς γράφοντας τα αποτελέσματα το ένα κάτω από το άλλο διαδοχικά. Η διαδικασία τερματίζεται όταν ο αριθμός που γράφεται στη στήλη της μονάδας ξεπεράσει το μισό του 46.
285 | 1
570 | 2
1140 | 4
2280 | 8
4560 | 16
9120 | 32
Βήμα 2: Από τη στήλη του 1 σημειώνουμε τους αριθμούς που αθροίζουν στον αριθμό 46 (βρίσκουμε δηλαδή την ανάλυση του 46 ως άθροισμα δυνάμεων του 2). Σημειώνουμε και τους αριθμούς της στήλης του 285 που βρίσκονται στις αντίστοιχες θέσεις.
285 | 1
570 | 2
1140 | 4
2280 | 8
4560 | 16
9120 | 32
Βήμα 3: Το αποτέλεσμα του πολλαπλασιασμού δίνεται από το άθροισμα 570 + 1140 + 2280 + 9120 = 13110.
Ουσιαστικά, η αιγυπτιακή μέθοδος αναλύει έναν αριθμό σε άθροισμα δυνάμεων του δύο και χρησιμοποιεί την επιμεριστική μέθοδο:
285 x 46 = 285 x (32 + 8 + 4 + 2) = 285 x (2^5 + 2^3 + 2^2 + 2^1) = 285x2^5 + 285x2^3 + 285x2^2 + 285x2 = 9120 + 2280 + 1140 + 570.
Από τις παραπάνω σχέσεις είναι φανερό για ποιο λόγο επιλέγουμε να αθροίσουμε τους συγκεκριμένους αριθμούς.
Αξίζει να παρατηρήσουμε ότι (όπως αναφέρθηκε παραπάνω), την ίδια ακριβώς τεχνική χρησιμοποιεί και ο κλασσικός αλγόριθμος πολλαπλασιασμού. Η διαφορά είναι ότι η κλασική μέθοδος χρησιμοποιεί το δεκαδικό σύστημα (δηλαδή αναλύει τον αριθμό σε μονάδες, δεκάδες, εκατοντάδες κ.λ.π.), ενώ η αιγυπτιακή μέθοδος το δυαδικό.
Η ρώσικη μέθοδος ή μέθοδος του χωρικού είναι μια απλούστερη εκδοχή της αιγυπτιακής μεθόδου. Aς δούμε τον πολλαπλασιασμό 285x46 με βάση την ρώσικη μέθοδο:
Βήμα 1: Γράφουμε τους αριθμούς 285 και 46 τον ένα δίπλα στον άλλο, έτσι ώστε να σχηματίσουμε δύο κατακόρυφες στήλες. Επιλέγουμε έναν από τους δύο (π.χ. τον 46) για να κάνουμε τις διαδοχικές διαιρέσεις με το 2, ενώ τον άλλο τον πολλαπλασιάζουμε με το 2. Σε κάθε διαίρεση γράφουμε το πηλίκο στην αντίστοιχη στήλη, το ένα κάτω από το άλλο. Τονίζουμε ότι εκτελούμε ακέραια διαίρεση. Για παράδειγμα η διαίρεση 23:2 δίνει πηλίκο 11 (το οποίο γράφουμε στη στήλη) και υπόλοιπο 1 (το οποίο αγνοούμε). Η διαδικάσια τερματίζεται όταν η διαίρεση δώσει πηλίκο ίσο με 1.
285 | 46
570 | 23
1140 | 11
2280 | 5
4560 | 2
9120 | 1
Βήμα 2: Στη συνέχεια σημειώνουμε τους αριθμούς από τη στήλη των πολλαπλασιασμών, που δίπλα τους (στη στήλη των διαιρέσεων) έχουν περιττό αριθμό:
285 | 46
570 | 23
1140 | 11
2280 | 5
4560 | 2
9120 | 1
Βήμα 3: Προσθέτουμε όλους του αριθμούς της στήλης των πολλαπλασιασμών που σημειώσαμε στο Βήμα 2. Το αποτέλεσμα του πολλαπλασιασμού είναι:
570 + 1140 + 2280 + 9120 = 13110.
Εννοείται ότι αν αλλάξουμε την επιλογή του αριθμού τον οποίο διαρούμε διαδοχικά, το αποτέλεσμα που θα προκύψει θα είναι το ίδιο, για παράδειγμα:
285 | 46
142 | 92
71 | 184
35 | 368
17 | 736
8 | 1472
4 | 2944
2 | 5888
1 | 11776
Το αποτέλεσμα είναι και πάλι ίσο με 46 + 184 + 368 + 736 + 11776 = 13110.
Σε δυαδικό σύστημα, η μέθοδος του χωρικού είναι ακόμα απλούστερη, αφού βασίζεται μόνο σε μετατοπίσεις ψηφίων (shifts). Σε κάθε αριθμητικό σύστημα, ο πολλαπλασιασμός με τον αριθμό βάσης ισοδυναμεί με μια μετατόπιση προς τα αριστερά, ενώ η διαίρεση με τον αριθμό βάσης με μια μετατόπιση προς τα δεξιά. Ας δούμε το παραπάνω παράδειγμα στο δυαδικό σύστημα:
285 | 46
100011101 | 101110
1000111010 | 10111
10001110100 | 1011
100011101000 | 101
1000111010000 | 10
10001110100000 | 1
Στο δυαδικό σύστημα οι περιττοί αριθμοί έχουν τελευταίο ψηφίο τη μονάδα. Επομένως, το αποτέλεσμα δίνεται από το άθροισμα
1000111010
10001110100
100011101000
10001110100000 +
---------------
11001100110110
Ο αριθμός αυτός είναι ο 13110 σε δυαδική αναπαράσταση.
ΣΤ. Πολλαπλασιασμός με Τέταρτα Τετραγώνων
Η μέθοδος αυτή χρησιμοποιεί την παρακάτω ταυτότητα:
όπου η αγκύλη (χωρίς την πάνω γωνία) εκφράζει το ακέραιο μέρος (floor) του αντίστοιχου αριθμού. Δεν είναι δύσκολο να αποδείξουμε ότι η παραπάνω σχέση πράγματι ισχύει:
Από την σχέση που αποδείξαμε γίνεται προφανές ότι αν κάποιος είχε πρόσβαση σε ένα πίνακα με τέταρτα τετραγώνων ακεραίων αριθμών, θα μπορούσε να υλοποιήσει τον επιθυμητό πολλαπλασιασμό με μια απλή αφαίρεση. Για παράδειγμα ας θεωρήσουμε τον παρακάτω πίνακα:
Ο παραπάνω πίνακας μπορεί να χρησιμοποιηθεί για την υλοποίηση πολλαπλασιασμών μονοψήφιων αριθμών. Για παράδειγμα ο πολλαπλασιασμός 5x9 μπορεί να γίνει ως εξής:
Όπως φαίνεται η συγκεκριμένη μέθοδος είναι απλή, αφού ανάγεται σε απλές προσθέσεις και αφαιρέσεις, αλλά απαιτεί γνώση ενός μεγάλου πίνακα τετραγώνων. Τέτοιοι πίνακες αναπτύχθηκαν από μαθηματικούς τον 19ο αιώνα. Συγκεκριμένα το 1817 ο Antoine Voisin ανέπτυξε έναν πίνακα με τα τετράγωνα τετραγώνων μέχρι και το 1000, ενώ αρκετά χρόνια αργότερα, ο Samuel Laundy (1856) και ο Joseph Blater (1888) ανέπτυξαν πίνακες που έφταναν στο 100000 και στο 200000 αντίστοιχα. Κάποιοι ερευνητές (εδώ) θεωρούν ότι αυτή η μέθοδος αναπτύχθηκε από μαθηματικούς στην αρχαία Βαβυλώνα.
Η μέθοδος των τετάρτων τετραγώνων χρησιμοποιήθηκε για την υλοποίηση πολλαπλασιασμού σε αναλογικά κυκλώματα. Επίσης, η μέθοδος χρησιμοποιήθηκε και για την υλοποίηση πολλαπλασιασμού (μέσω λογισμικού) σε ψηφιακούς υπολογιστές όπως ο θρυλικός MOS 6502.
Comments