Κεφάλαιο 5Αλγόριθμοι Χαμηλού Επιπέδου

Από όλα τα κλασικά διδακτικά βιβλία Αρχιτεκτονικής Υπολογιστών γνωρίζουμε τι είναι οι αθροιστές (adders). Για παράδειγμα, έστω ότι δίνονται δύο ακέραιοι αριθμοί υπό δυαδική μορφή $a_{k-1}{a}_{k-2}\mathrm{\dots }{a}_0$ και $b_{k-1}{b}_{k-2}\mathrm{\dots }{b}_0$ που αντιστοιχούν στους ακεραίους $a_{k-1}{2}^{k-1}+a_{k-2}{2}^{k-2}+\mathrm{\dots }+a_0{2}^0$ και $b_{k-1}{2}^{k-1}+b_{k-2}{2}^{k-2}+\mathrm{\dots }+b_0{2}^0$ υπό δεκαδική μορφή. Ο $i$-οστός αθροιστής που δέχεται εισόδους τα $a_i,b_i$ και $c_{i-1}$, όπου $c_{i-1}$ είναι το κρατούμενο από τον προηγούμενο αθροιστή. Στο Σχήμα 5.1 παρουσιάζεται η πρόσθεση δύο ακεραίων σε δεκαδικό και δυαδικό σύστημα. Είναι προφανής η σάρωση των δυαδικών αριθμών από τα δεξιά προς τα αριστερά. Συνεπώς, η πολυπλοκότητα της πρόσθεσης είναι γραμμική ως προς το μήκος σε bits των τελεσταίων, δηλαδή Θ($k$), με μία κρυμμένη σταθερά ίση με 2 λόγω του κρατούμενου $c_i$.

                   8          1000
                  +3         +0011
                  --          ----
                  11          1011

              αφαίρεση       πρόσθεση     πρόσθεση
               αριθμών    συμπληρώματος    μονάδας
     8          1000          1000          0100
    -3         -0011         +1100            +1
    --          ----          ----          ----
     5          1011          0100          0101

Η πράξη της αφαίρεσης είναι παρόμοια προς την πράξη της πρόσθεσης και στηρίζεται στο συμπλήρωμα. Στο Σχήμα 5.2 παρουσιάζεται η αντίστοιχη διαδικασία. Το συμπλήρωμα, όπως και η διαδικασία της πρόσθεσης, ουσιαστικά είναι μία σάρωση, άρα είναι μία γραμμική διαδικασία, ενώ η τελική πρόσθεση του άσσου έχει σταθερό κόστος. Συνεπώς, η πολυπλοκότητα είναι τελικά και πάλι γραμμική, δηλαδή Θ($k$).

Έστω δύο ακέραιοι αριθμοί υπό δυαδική μορφή $a_{k-1}{a}_{k-2}\mathrm{\dots }{a}_0$ και $b_{k-1}{b}_{k-2}\mathrm{\dots }{b}_0$ που δίνονται προς πολλαπλασιασμό. Οι αριθμοί τοποθετούνται στους καταχωρητές Α και Β, αντίστοιχα, ενώ στον καταχωρητή Ρ θα τοποθετηθεί το γινόμενό τους. Ο πολλαπλασιασμός θα γίνει με τα εξής δύο βήματα:

1. 1.

   αν το λιγότερο σημαντικό ψηφίο του Α είναι 1, τότε ο καταχωρητής Β προστίθεται στο Ρ, αλλιώς προστίθεται το 00…00. Το άθροισμα τίθεται πάλι στον καταχωρητή Ρ.

2. 2.

   οι καταχωρητές Α και Ρ ολισθαίνουν προς τα δεξιά, ενώ το κρατούμενο του αθροίσματος μετακινείται στο υψηλότερο (αριστερότερο) bit του καταχωρητή Ρ και το χαμηλότερο bit του Ρ μετακινείται στον καταχωρητή Α, όπου το δεξιότερο bit διολισθαίνει προς τα έξω καθώς δεν θα χρησιμοποιηθεί στη συνέχεια.

Μετά από $n$ βήματα, το γινόμενο εμφανίζεται στους καταχωρητές Ρ και Α, όπου ο Α αποθηκεύει τα λιγότερο σημαντικά ψηφία του αποτελέσματος. Το Σχήμα 5.3 δείχνει τον πολλαπλασιασμό δύο ακεραίων, των A=6 και B=3, τους οποίους παριστούμε με τους αντίστοιχους δυαδικούς 110 και 011. Εφόσον το μήκος των αριθμών σε bits είναι 3, έπεται ότι θα υπάρξει ένας βρόχος τριών επαναλήψεων των δύο βημάτων. Το τελικό αποτέλεσμα είναι 010010, δηλαδή 18. Παρατηρούμε ότι για κάθε bit του A εκτελείται μία πρόσθεση όλων των bits του B. Συνεπώς, η πολυπλοκότητα του πολλαπλασιασμού δύο ακεραίων που αναπαριστώνται με $k_1$ και $k_2$ bits αντίστοιχα είναι Θ($k_1{k}_2$).

                                 A      B      P
   Βήμα 1 (πρόσθεση Β στο Ρ)    110    011    000
   Βήμα 2 (ολίσθηση δεξιά)      011    011    000
   Βήμα 1 (πρόσθεση Β στο Ρ)    011    011    011
   Βήμα 2 (ολίσθηση δεξιά)      101    011    001
   Βήμα 1 (πρόσθεση Β στο Ρ)    101    011    100
   Βήμα 2 (ολίσθηση δεξιά)      010    011    010

Στην πράξη της διαίρεσης δύο δυαδικών αριθμών, με μία διαδικασία παρόμοια προς την προηγούμενη, οι αριθμοί τοποθετούνται στους καταχωρητές Α και Β, ενώ το αποτέλεσμα τοποθετείται στον καταχωρητή Ρ. Η διαίρεση θα γίνει με τα εξής τέσσερα βήματα:

1. 1.

   ολισθαίνουμε το ζεύγος των καταχωρητών Α και Ρ μία θέση προς τα αριστερά.

2. 2.

   αφαιρούμε το περιεχόμενο του καταχωρητή Β από τον καταχωρητή Ρ και τοποθετούμε το αποτέλεσμα στον καταχωρητή Ρ.

3. 3.

   αν το αποτέλεσμα του προηγούμενου βήματος είναι αρνητικό, τότε βάζουμε 0 στο χαμηλότερο ψηφίο του Α, αλλιώς βάζουμε το 1.

4. 4.

   αν το αποτέλεσμα του ιδίου βήματος είναι αρνητικό, τότε αποκαθιστούμε την παλιά τιμή του Ρ προσθέτοντας το περιεχόμενο του Β στο Ρ.

Για παράδειγμα, έστω ότι θέλουμε να διαιρέσουμε τους αριθμούς A=14=1110${}_2$ και B=3=11${}_2$. Το Σχήμα 5.4 παρουσιάζει την αλληλουχία των βημάτων. Στο τέλος των τεσσάρων (όσο το μήκος του A) επαναλήψεων των τεσσάρων βημάτων στον καταχωρητή Α είναι αποθηκευμένο το πηλίκο (δηλαδή 4), ενώ στον καταχωρητή Ρ είναι αποθηκευμένο το υπόλοιπο (δηλαδή 2).

                                  Ρ      Α      Β
   Αρχική κατάσταση               00    1110    11
   Βήμα 1 (ολίσθηση αριστερά)     01    110     11
   Βήμα 2 (αφαίρεση Β από Ρ)     -10    110     11
   Βήμα 3 (χαμηλό bit του A)     -10    1100    11
   Βήμα 4 (αποκατάσταση Ρ)        01    1100    11
   Βήμα 1 (ολίσθηση αριστερά)     11    100     11
   Βήμα 2 (αφαίρεση Β από Ρ)      00    100     11
   Βήμα 3 (χαμηλό bit του A)      00    1001    11
   Βήμα 1 (ολίσθηση αριστερά)     01    001     11
   Βήμα 2 (αφαίρεση Β από Ρ)     -10    001     11
   Βήμα 3 (χαμηλό bit του A)     -10    0010    11
   Βήμα 4 (αποκατάσταση Ρ)        01    0010    11
   Βήμα 1 (ολίσθηση αριστερά)     10    010     11
   Βήμα 2 (αφαίρεση Β από Ρ)     -01    010     11
   Βήμα 3 (χαμηλό bit του A)     -01    0100    11
   Βήμα 4 (αποκατάσταση Ρ)        10    0100    11

Στο παράδειγμα αυτό, σαρώνουμε $k_1$ φορές (δηλαδή, όσο το μέγεθος σε bits του καταχωρητή Α) τον καταχωρητή Ρ μεγέθους $k_2$ bits (δηλαδή, όσο το μέγεθος σε bits του καταχωρητή Β). Συνεπώς, όπως και στην περίπτωση του πολλαπλασιασμού, η πολυπλοκότητα της διαίρεσης δύο ακεραίων που αναπαριστώνται με $k_1$ και $k_2$ bits αντίστοιχα είναι Θ($k_1{k}_2$).  

Θέλουμε να υπολογίσουμε τη δύναμη $a^b$, όπου τα $a,b$ είναι ακέραιοι αριθμοί. Ας υποθέσουμε ότι θα εφαρμόσουμε τη γνωστή συνάρτηση power1, που την υπενθυμίζουμε στη συνέχεια, ώστε να αντιληφθούμε το μηχανισμό του υπολογισμού αυτού.

     function power1(a,b)
1.   power <-- 1;
2.   for i <-- 1 to b do power <-- power*a
3.   return power1

Με βάση όσα αναφέραμε προηγουμένως για το κόστος του πολλαπλασιασμού προκύπτει ότι για να υπολογίσουμε το τετράγωνο $a^2$ χρειαζόμαστε Θ(${(\log a)}^2$) πράξεις σε bit, ενώ το μέγεθος του αποτελέσματος έχει μέγεθος $2\log a$ bits. Ομοίως, για τον υπολογισμό του $a^3$ θα εκτελέσουμε έναν πολλαπλασιασμό μεταξύ δύο αριθμών: ενός αριθμού μεγέθους $\log a$ bits και ενός αριθμού μεγέθους $2\log a$ bits. Συνεπώς, το αντίστοιχο υπολογιστικό κόστος θα είναι $\mathrm{\Theta }({(\log a)}^2)$ πράξεις με bit (με κρυμμένη σταθερά 2), ενώ το αποτέλεσμα της πράξης θα αποθηκευθεί σε χώρο $3\log a$ bits. Συνεχίζοντας το σκεπτικό αυτό καταλήγουμε στο συμπέρασμα ότι για τον υπολογισμό του $a^b$ θα εκτελέσουμε έναν πολλαπλασιασμό μεταξύ δύο αριθμών: ενός αριθμού μεγέθους $\log a$ bits και ενός αριθμού $(b-1)\log a$ bits. Συνεπώς, η χρονική πολυπλοκότητα της ύψωσης σε δύναμη $a^b$ είναι Θ($b^2{\log }^{2}a$), ενώ η χωρική πολυπλοκότητα είναι Θ($b\log a$).

Θέλουμε να υπολογίσουμε το άθροισμα ${\sum }_{i=1}^n{i}^2=n(n+1)(2n+1)/6$. Αρχικά μελετάμε το αριστερό σκέλος. Με βάση τα προηγούμενα, προκύπτει ότι το κόστος υπολογισμού του ενός τετραγώνου είναι Θ(${(\log n)}^2$) και, επομένως, το συνολικό κόστος για τον υπολογισμό όλων των $n$ τετραγώνων του αριστερού σκέλους θα είναι Θ($n{(\log n)}^2$). Καθώς το κόστος των προσθέσεων $n-1$ προσθέσεων είναι μικρότερο από το κόστος των πολλαπλασιασμών, προκύπτει ότι το προηγούμενο κόστος είναι και το τελικό σε σχέση με το αριστερό σκέλος. Απεναντίας, το κόστος υπολογισμού του δεξιού σκέλους είναι Θ(${(\log n)}^2$), γεγονός που εξηγείται με βάση το γεγονός ότι απλώς εκτελούνται τρεις πολλαπλασιασμοί και μία διαίρεση.

Ας υποθέσουμε ότι πρέπει να πολλαπλασιάσουμε δύο τετραγωνικούς πίνακες $n\times n$, ενώ το μέγεθος των στοιχείων των πινάκων είναι μικρότερο από $m>0$. Ο πίνακας που θα προκύψει από τον πολλαπλασιασμό θα έχει επίσης $n^2$ στοιχεία, κάθε ένα από τα οποία για να υπολογισθεί απαιτεί $n$ πολλαπλασιασμούς και $n-1$ προσθέσεις. Επειδή κάθε πολλαπλασιασμός απαιτεί ${(\log m)}^2$ πράξεις με bit, ενώ κάθε πρόσθεση απαιτεί $2\log m$ πράξεις με bit, έπεται ότι το συνολικό κόστος είναι $(n^2(n{(\log m)}^2+2(n-1)\log m))$ πράξεις με bits, και επομένως η πολυπλοκότητα είναι $\mathrm{\Theta }(n^3({(\log m)}^2+\log m))$.

Θεωρούμε γνωστή την Εξίσωση 2.35 για τον υπολογισμό του συνδυασμού των $n$ ανά $m$ αντικειμένων:

$$\left(\begin{array}{c}n\\ m\end{array}\right)=\frac{n\times (n-1)\times (n-2)\times \mathrm{\dots }\times (n-m+1)}{1\times 2\times 3\times \mathrm{\dots }\times m}$$

(5.1)

και απο το Κεφάλαιο 4.5 χρησιμοποιούμε τη γνωστή συνάρτηση comb4, που υπενθυμίζουμε στη συνέχεια.

     function comb4(n,m);
1.   if m>n-m then m <-- n-m
2.   t1 <-- 1;
3.   for i <-- n downto n-m+1 do t1 <-- t1*i;
4.   t2 <-- factorial2(m);
5.   return t1/t2

Σύμφωνα με τον αλγόριθμο αυτό αρχικά εκτελούνται $m-1$ πολλαπλασιασμοί για τον αριθμητή, στη συνέχεια άλλοι $m-1$ πολλαπλασιασμοί για τον παρονομαστή και τελικά μία διαίρεση. Αν υποθέσουμε ότι το μέγεθος του $n$ είναι $k=\log n$ bits, τότε με τη λογική που αντιμετωπίσαμε το πρόβλημα του υπολογισμού της ύψωσης σε δύναμη θα έχουμε τον εξής μηχανισμό.

Για να εκτελέσουμε τον πρώτο πολλαπλασιασμό χρειαζόμαστε Θ($k^2$) πράξεις σε bit, ενώ το μέγεθος του αποτελέσματος θα έχει μέγεθος $2k$ bits. Για το δεύτερο πολλαπλασιασμό θα θεωρήσουμε έναν αριθμό μεγέθους $k$ bits και έναν αριθμό μεγέθους $2k$ bits. Συνεπώς, το αντίστοιχο κόστος θα είναι $\mathrm{\Theta }(k^2)$ πράξεις με bit (με κρυμμένη σταθερά 2), ενώ το αποτέλεσμα της πράξης θα αποθηκευθεί σε χώρο $3k$ bits. Συνεχίζοντας το σκεπτικό αυτό καταλήγουμε στο συμπέρασμα ότι για την εκτέλεση του ($m-1$)-οστού πολλαπλασιασμού θα θεωρήσουμε έναν αριθμό μεγέθους $k$ bits και έναν αριθμό μεγέθους $(m-1)k$ bits. Συνεπώς, η χρονική πολυπλοκότητα για τον υπολογισμό του αριθμητή θα είναι $k^2{(m-1)}^2$, δηλαδή ισχύει η πολυπλοκότητα Θ($k^2{m}^2$). Το κόστος του υπολογισμού του παρονομαστή (εντολή 4) είναι ασφαλώς φραγμένο από επάνω από την ίδια πολυπλοκότητα του υπολογισμού του αριθμητή, δηλαδή Θ($k^2{m}^2$). Επομένως αυτή είναι και η τελική απάντηση σε σχέση με τη ζητούμενη πολυπλοκότητα.

Ας υποθέσουμε ότι δίνεται ένας ακέραιος $n$ υπό τη δυαδική μορφή $b_{k-1}{b}_{k-2}\mathrm{\dots }{b}_2{b}_1{b}_0$ και επιθυμούμε να βρούμε την ισοδύναμή του έκφραση στο δεκαδικό σύστημα. Θα μπορούσε να εφαρμοσθεί ένας αλγόριθμος της επόμενης μορφής.

     function bin2dec
1.   num <-- b_{k-1};
2.   for i <-- k-2 downto 0 do num <-- 2*num + b_i;

Καθώς κάθε μερικό αποτέλεσμα είναι μεγέθους το πολύ $k$ bits και ο βρόχος εκτελείται $k-1$ φορές, έπεται ότι ο συνολικός αριθμός πράξεων με bit είναι $\mathrm{\Theta }(k^2)=\mathrm{\Theta }({(\log n)}^2)$.

Στο Κεφάλαιο 4.1 μελετήσαμε διεξοδικά τον αλγόριθμο του Ευκλείδη για την εύρεση του μέγιστου κοινού διαιρέτη μεταξύ δύο ακεραίων $n>m$. Στο σημείο αυτό υπενθυμίζουμε τον αλγόριθμο.

     function euclid(m,n)
1.   while m>0 do
2.      t <-- n mod m
3.      n <-- m
4.      m <-- t
5.   return n

Για να προχωρήσουμε σε μία εκτίμηση κόστους, κατ’αρχήν πρέπει να παρατηρήσουμε ότι στις διαδοχικές διαιρέσεις παράγονται συνεχώς μικρότερα υπόλοιπα. Επίσης, στο Κεφάλαιο 4.1 παρατηρήσαμε ότι . Με λίγα λόγια, μετά από κάθε δεύτερο βήμα το υπόλοιπο υποδιαιρείται και επομένως στη χειρότερη περίπτωση θα εκτελεσθούν $2\log m$ διαιρέσεις. Καθώς σε κάθε τέτοιο βήμα οι αριθμοί που υπεισέρχονται στις διαιρέσεις αυτές είναι μικρότεροι του $m$, έπεται ότι κάθε τέτοια πράξη απαιτεί στη χειρότερη περίπτωση Ο(${(\log m)}^2$). Επομένως, τελικά η πολυπλοκότητα είναι Ο(${(\log m)}^3$). Σημειώνουμε ότι με μία πιο σφικτή ανάλυση μπορεί να προκύψει ότι η πολυπλοκότητα είναι Ο(${(\log m)}^2$).

Από την Άσκηση 1.12 γνωρίζουμε ότι για την εύρεση των πρώτων αριθμών από 1 ως $n$, μπορεί να χρησιμοποιηθεί το κόσκινο του Ερατοσθένη. Ο μικρότερος πρώτος αριθμός είναι 2. Έτσι, αγνοούμε όλα τα πολλαπλάσια του 2 μέχρι την τιμή $n$. Από τους αριθμούς που απομένουν ο μικρότερος είναι και πάλι πρώτος, δηλαδή το 3. Έτσι αγνοούμε όλα τα πολλαπλάσια του 3 μέχρι την τιμή $n$. Σύμφωνα με το επόμενο θεώρημα, η διαδικασία αυτή πρέπει να συνεχισθεί για όλους τους ακεραίους μέχρι το $\sqrt{n}$, καθώς αυτό το όριο αρκεί για τον Ερατοσθένη.  

Θεώρημα.
Αν το $n$ είναι θετικός σύνθετος ακέραιος, τότε ο $n$ έχει έναν πρώτο αριθμό που δεν ξεπερνά το $\sqrt{n}$.  

Απόδειξη.
Αν το $n$ είναι θετικός σύνθετος ακέραιος, τότε ισχύει $n=a\times b$, όπου . Συνεπώς, $a\le \sqrt{n}$ γιατί αλλιώς θα έπρεπε $a\times b>n$.  

Ο έλεγχος ενός αριθμού για την εύρεση των πρώτων αριθμών του με τη μέθοδο του Ερατοσθένη είναι πολύ αναποτελεσματικός. Αν με Π($x$) συμβολίζουμε το πλήθος των πρώτων αριθμών που δεν υπερβαίνουν τον αριθμό $x$, τότε για να ελέγξουμε αν ο $x$ είναι πρώτος αρκεί να εκτελέσουμε Π($\sqrt{x}$) διαιρέσεις. Έχει αποδειχθεί ότι ασυμπτωτικά ισχύει $\mathrm{\Pi }(x)=x/\log x$ και επομένως το πλήθος των πρώτων αριθμών που δεν υπερβαίνουν τον αριθμό $\sqrt{n}$ είναι $\sqrt{n}/\log \sqrt{n}$. Καθώς κάθε τέτοια διαίρεση απαιτεί Θ(${(\log n)}^2$) πράξεις με bit, είναι ευνόητο ότι συνολικά απαιτούνται Θ($\sqrt{n}\log n$) πράξεις με bit, με την προϋπόθεση ότι διαθέτουμε μία λίστα με όλους τους πρώτους αριθμούς που δεν υπερβαίνουν την τιμή $\sqrt{n}$. Η πολυπλοκότητα αυτή είναι εκθετική ως προς $k=\lfloor \log n\rfloor +1$, ενώ αν διεκπεραιώναμε το πρόβλημα θεωρώντας μία συμβατική προσέγγιση για την ανάλυση του αλγορίθμου, τότε θα καταλήγαμε σε μία γραμμική πολυπλοκότητα.