Μία αποδεκτή λύση θα ήταν να κάνουμε ψευδοτυχαία επιλογή ανάμεσα στις ομάδες ροών που περιμένουν να λάβουν μία πίστωση. Ο στόχος λοιπόν στρέφεται στην επιλογή μιας γεννήτριας τυχαίων αριθμών με καλές ιδιότητες, εύκολη στην υλοποίηση και αρκετά γρήγορη για τις προδιαγραφές χρονισμού που έχουμε.
Εξετάζοντας διάφορες μεθόδους για γέννηση τυχαίων πραγματικών αριθμών ,
ομοιόμορφα κατανεμημένων μεταξύ 0 και 1
,
οι πιο δημοφιλείς γεννήτριες τυχαίων αριθμών σήμερα ακολουθούν τη μέθοδο
(πολλαπλασιαστικής) γραμμικής σύγκλισης, ή κάποια παραλαγή της.
Είναι μια μέθοδος από τις πιο απλές, παλιές (D.H. Lehmer,1948)
αλλά και πιο ευρέως χρησιμοποιούμενη.
Για να έχουμε λοιπόν μία ακολουθία τυχαίων αριθμών ( ) εφαρμόζουμε την
αναδρομική σχέση :
Αυτή ορίζεται ως μία γραμμική, συγκλίνων ακολουθία. Όλες οι ακολουθίες
που έχουν το γενικό τύπο έχουν ένα επαναλαμβανόμενο κύκλο
που ονομάζεται περίοδος. Στην περίπτωση των γραμμικών συγκλίνων γεννητριών
(linear congruential generators (LCG)) η περίοδος της ακολουθίας είναι m,
αφού η περίοδος δεν μπορεί να έχει παραπάνω από m στοιχεία. Η κατάλληλη επιλογή
των παραμέτρων m,a,c, και
εξαρτάται από την εφαρμογή και καθορίζει την
περίοδο αλλά και τις ιδιότητες τυχαιότητας των LCG's.
Από μαθηματική άποψη, μία ακολουθία τυχαίων αριθμών από γεννήτρια (βεβαίως αποκαλούνται ``τυχαίοι'', αν και είναι εντελώς ντετερμινιστικοί στο χαρακτήρα) πρέπει να έχει τις ακόλουθες ιδιότητες : μεγάλη περίοδο, ασυσχέτιστη ακολουθία, ομοιομορφία, μέσο όρο=1/2 και μεταβλητότητα=1/12. Αυτές οι ιδιότητες μπορεί να είναι επιθυμητές ή αναγκαίες αλλά όχι και ικανές για τυχαιότητα. Πολλές έννοιες έχουν εισαχθεί τα τελευταία χρόνια για την αποδοχή ή απόρριψη γεννητριών τυχαίων αριθμών. Επιπλέον, αρκετά τεστ, θεωρητικά και εμπειρικά έχουν εφαρμοστεί σε ακολουθίες για να ερευνηθεί η τυχαιότητα τους. Στο πλαίσιο αυτής της εργασίας δεν θα γίνει ανάλυση των οικογενειών από τεστ (λεπτομερής έρευνα βρίσκεται στον D.Knuth). Οι γραμμικές συγκλίνοντες ακολουθίες πρέπει να περνούν το ονομαζόμενο φασματικό τεστ προτού γίνουν αποδεκτές ως τυχαίες. Ο στόχος του φασματικού τεστ είναι να ανακαλυφθεί η συμπεριφορά της γεννήτριας όταν οι έξοδοί της χρησιμοποιούνται σχηματίζοντας d-tuples.
Αν και οι LCG's είναι από τις πιο ``ωραίες'', ``απλές'' και πιο αποδοτικές
μεθόδους, το βασικό τους μειονέκτημα είναι ότι οι d-tuples τέτοιων ακολουθιών
παρουσιάζουν μία κανονική επαναληπτική δομή όταν σχεδιαστεί σε d διαστάσεις.
Αυτό το πρόβλημα είναι εγγενής στις περιοδικές ακολουθίες. Μία κυκλική
ακολουθία m αριθμών, όταν την πάρουμε σε ζεύγη, εντοπίζεται πάνω στα m από
τα σημεία σε ένα δισδυάστατο πλέγμα m επί m. Εν γένη, τα
σημεία του πλέγματος θα είναι πάντα κενά στον n-διάστατο χώρο από τα n-tuples
που λαμβάνονται από μία ακολουθία περιόδου m, δηλαδή λείπουν τα περισσότερα γινόμενα
τομής. Επίσης, αυτές οι γεννήτριες έχουν αποδειχθεί ότι παρουσιάζουν συσχετίσεις
μεταξύ αριθμών που βρίσκονται σε απόσταση
μεταξύ τους.
Στην περίπτωσή μας πρέπει να γεννάμε ακεραίους μεταξύ 0 και 255. Βεβαίως μία
γεννήτρια με περίοδο μήκους 256 σχεδόν δεν μπορεί να είναι τυχαία [D.E81].
Εντούτοις, ας προσπαθήσουμε να κατασκευάσουμε την καλύτερη δυνατή πολλαπλασιαστική
γραμμική συγκλίνουσα γεννήτρια.
Προφανώς, m=256 ( ). Ακολουθώντας τις οδηγίες του Knuth, αν το m είναι
δύναμη του 2, το a πρέπει να επιλεγεί έτσι ώστε a mod 8 = 5. Πρέπει να σημειωθεί
ότι η επιλογή του a μαζί με την επιλογή του c μπορεί να εξασφαλίσει ότι η γεννήτρια
τυχαίων αριθμών θα παράγει όλες τις m διαφορετικές δυνατές τιμές προτού αρχίσει να
επαναλαμβάνεται. Υποθέτωντας η βάση αριθμών της μηχανής που χρησιμοποιούμε είναι
z=2, και
, τότε
. Η τιμή του c δεν έχει σημασία όταν το
a που χρησιμοποιούμε είναι καλός πολλαπλασιαστής. Έτσι μπορούμε να διαλέξουμε
c=1. Η αναδρομική σχέση τώρα παίρνει τη μορφή
και αυτή η εξίσωση δείχνει ότι μπορούμε να αποφύγουμε τον πολλαπλασιασμό, αρκούν ολισθήσεις και προσθέσεις. Επίσης, απαιτείται μόνο μία θέση μνήμης για να κρατάμε τον τελευταίο ακέραιο της ακολουθίας.
Μία κατάλληλη γεννήτρια LCG φαίνεται να είναι η .
Παρά την απλότητα της
, η υλοποίηση θα απαιτούσε έναν πολλαπλασιαστή
και έναν αθροιστή σε πρώτη ματιά. Εντούτοις, με ένα πιο προσεκτικό μάτι φαίνεται
από τη σχέση ότι αφού ο πολλαπλασιαστής είναι πάντα σταθερός, συγκεκριμένα το
πέντε, ο επόμενος ακέραιος
μπορεί να υπολογιστεί όπως φαίνεται στο σχήμα
3.21 (υποθέτοντας ότι
).
Συνεπώς, χρειάζεται ένας απλός αθροιστής των 8 bit και μία θέση μνήμης για να
κρατά την προηγούμενη τιμή
.
Figure 3.21: Η υλοποίηση της γεννήτριας
Παρόλα τούτα, για να ενσωματώσουμε αυτό το σχήμα στον αποκωδικοποιητή
προτεραιότητας (PE1) που ήδη χρειαζόμαστε αφού έχει γίνει το ψαξιμο στις
μνήμες CAM, πρέπει να χρησιμοποιηθεί ένας αποκωδικοποιητής 8-σε-256 και
άλλος ένας αποκωδικοποιητής προτεραιότητας (PE2) για να λειτουργεί στο
διάνυσμα που παράγεται από τον αποκωδικοποιητή, ώστε ο αρχικός PE1 να
λειτουργεί στο αποτέλεσμα .
Εμβαθύνοντας στο παραπάνω σχήμα, αφού η ακολουθία που γεννιέται από τον τύπο είναι καθορισμένη, δηλαδή η σειρά {0,1,6,31,156,13,...} πάντα θα εμφανίζεται με την ίδια σειρά, μπορούμε να εγκαταλείψουμε το γενικό σχήμα με τον αθροιστή και τον αποκωδικοποιητή. Αυτό που χρειαζόμαστε είναι μια σταθερή αλυσίδα από 256 D-flip-flops συνδεδεμένα σύμφωνα με την προκαθορισμένη ακολουθία (σχήμα 3.22). Αυτή η σταθερή αλυσίδα ουσιαστικά γεννά ένα ``ψευδοτυχαίο'' αρχικό σημείο λειτουργίας για τον αποκωδικοποιητή προτεραιότητας.
Figure 3.22: Υλοποίηση της γεννήτριας
Οι γεννήτριες LCG's αν και είναι αρκετά απλές στην υλοποίησή τους, έχουν κάποια μειονεκτήματα όπως ειπώθηκε. Γενικά, οι d-tuples παρουσιάζουν μια κανονική επαναληπτική δομή όταν σχεδιαστούν στις d διαστάσεις. Αυτό είναι εμφανές και για την παραπάνω γεννήτρια, όπως φαίνεται στο σχήμα 3.23, μια γραφική παράσταση με μπάρες στον δισδυάστατο χώρο.
Figure 3.23: Μία περίοδος (256) (ζεύγη συνεχόμενων σημείων ( )), στο δισδυάστατο χώρο
Οι γεννήτριες Φιμπονάτσι (Lagged Fibonacci Generators (LFGs)) επιχειρούν να
βελτιώσουν τις LCG's χρησιμοποιώντας περισσότερες από μία παλιά τιμή της
ακολουθίας στην ακολουθιακή σχέση, ώστε να μειώσουν τη συσχέτιση και να
αυξήσουν την περίοδο. Αυτές οι γεννήτριες ονομάστηκαν έτσι λόγω της
ομοιότητας τους με τη γνωστή ακολουθία Φιμπονάτσι ( ).
Βεβαίως, μελέτες έχουν δείξει ότι αυτή δεν είναι και τόσο καλό παράδειγμα
γεννήτριας τυχαίων ακολουθιών. Μία καλύτερη μέθοδος είναι οι ακολουθίες
Φιμπονάτσι με βραδυπορεία (lagged Fibonacci sequences), όπου ο κάθε
αριθμός είναι συνδυασμός δύο οποιαδήποτε προηγούμενων τιμών :
όπου τα k και l ονομάζονται lags, και το είναι οποιαδήποτε
αριθμητική πράξη, όπως
(bitwise exclusive OR).
Εδώ αντίθετα με πριν που είχαμε μία αρχική στις γεννήτριες LCG,
χρειαζόμαστε l αρχικές τιμές,
, για να
υπολογίσουμε το επόμενο στοιχείο της ακολουθίας. Υποθέτωντας ότι χρησιμοποιούμε
τον τελεστή πρόσθεσης έχουμε από τους πιο απλές και γρήγορές γεννήτριες RNGs.
Επίσης, έχει ελεγχθεί εκτενώς για ιδιότητες τυχαιότητας από τον Marsaglia
[G.M85] και έχει λάβει πολύ καλές κριτικές.
Αν το m είναι δύναμη του δύο, δηλαδή , και επιλεγούν σωστά οι πρώτες
l τιμές του X, τότε η περίοδος P αυτής της γεννήτριας είναι ίση με
.
Προφανώς η τιμή του m δεν περιορίζει την περίοδο της γεννήτριας, όπως
στην περίπτωση μιας LCG. Η περίοδος μπορεί να γίνει οσοδήποτε μεγάλη
αν αυξηθεί το μεγαλύτερο lag. Εμπειρικά τεστ έχουν δείξει ότι οι ιδιότητες
τυχαιότητας αυτών των γεννητριών βελτιώνονται παράλληλα με την αύξηση του lag.
Αυτό φυσικά σημαίνει ότι ταυτόχρονα αυξάνεται και ο αριθμός θέσεων μνήμης που
χρειαζόμαστε, σε αντίθεση με την περίπτωση των LCG, όπου μία μόνο θέση μνήμης
ήταν αρκετή. Είναι επίσης φανερό ότι η γεννήτρια δεν παράγει P διαφορετικές
τιμές, προτού αρχίσει να τις ανακυκλώνει.
Θεωρητικά μία γεννήτρια Φιμπονάτσι λειτουργεί το ίδιο όπως ένας γραμμικός
καταχωρητής ολίσθησης. Όταν η αριθμητική πράξη που χρησιμοποιείται είναι
το XOR, τότε οι LFGs αναφέρονται πιο συχνά ως γενικοποιημένες γεννήτριες
τύπου καταχωρητή ολίσθησης [TW73].
Μία γεννήτρια γραμμικού καταχωρητή ολίσθησης (SRG) παράγει ακολουθίες που
εξαρτώνται από το μήκος του καταχωρητή, τις συνδέσεις ανατροφοδότησης προς
τα πίσω, και τις αρχικές συνθήκες. Αν η SRG έχει L βαθμίδες, και η
ακολουθία εξόδου έχει μήκος , τότε ονομάζεται ακολουθία
μέγιστου δυνατού μήκους. Κάθε τιμή στην ακολουθία εμφανίζεται μόνο
μία φορά σε μια περίοδο. Δεδομένου του μήκους του καταχωρητή ολίσθησης,
οι συνδέσεις ανατροφοδότησης προς τα πίσω καθορίζουν αν η ακολουθία θα
είναι μέγιστου δυνατού μήκους ή όχι. Ο [W.W61] παρουσιάζει
πλήρεις πίνακες από τους οποίους μπορούμε να φτιάξουμε κατευθείαν μία
γεννήτρια ψευδοτυχαίων αριθμών.
Μία γεννήτρια SRG κατάλληλη για τις ανάγκες για τυχαία επιλογή μεταξύ 256 κυττάρων φαίνεται να είναι αυτή που απεικονίζεται στο σχήμα 3.24. Στο ίδιο σχήμα φαίνεται επίσης και μια ισορροπημένη επιλογή μεταξύ της οικογένειας των γεννητριών Φιμπονάτσι. Χρησιμοποιούνται δέκα καταχωρητές των 8 bit για να υλοποιήσουν μία LFG(10,7,8) με περίοδο P=130944. Το πρόβλημα αρχικοποίησής τους έχει προσεγγιστεί από τον [MSDM94]. Επίσης, από το σχήμα 3.25 είναι φανερό ότι το εξόφθαλμο μειονέκτημα των LCGs έχει ξεπεραστεί από το LFG(10,7,8).
Figure 3.24: Μία γεννήτρια SRG μήκους 8 με συνδέσεις [1,3,5,8] και μία LFG(10,7,8)
Figure 3.25: Γραφική παράσταση 1000 μόνο σημείων (περίοδος=130944) μίας γεννήτριας LFG(10,7,8)