Όπως ίσως δεν ξέρετε, όλοι οι τυχαίοι αριθμοί (και συνεπώς οι τυχαίες διαδικασίες, τα τυχαία φύλλα τράπουλας, τα τυχαία passwords, τα gotcha captcha κλπ. κλπ.) που χρησιμοποιεί ένας υπολογιστής είναι στην πραγματικότητα ψευδο-τυχαίοι. Δηλαδή δεν είναι καθόλου τυχαίοι αλλά, τουναντίον, ντετερμινιστικά προσδιορισμένοι με έναν αλγόριθμο συνήθως απλό, που έχει όμως την ιδιότητα να παράγει μεγάλα σύνολα αριθμών οι οποίοι ενώ δεν είναι, φαίνονται τυχαίοι. Αυτό σημαίνει οτι ο αλγόριθμος παράγει ένα πακέτο π.χ. 10 δις αριθμών που περνάνε με επιτυχία ένα μεγάλο σύνολο από τεστ φτιαγμένα για να ξεχωρίζουν τυχαία από μη τυχαία πακέτα (ανάμεσά τους σε επιφανή θέση και το τεστ πόκερ).
Στην πραγματικότητα οι ψευδοτυχαίοι αριθμοί είναι προτιμηταίοι σε κάθε εφαρμογή σχετική με υπολογιστή, κυρίως γιατί είναι τσάμπα (σε αντίθεση με πραγματικά τυχαίους αριθμούς που θα έπρεπε να συλλεχθούν από κάποια πραγματικά τυχαία φυσική διαδικασία) αλλά και γιατί είναι δυνατόν να ανακατασκευάσουμε τον κάθε αριθμό ξεχωριστά (χρήσιμο στην διαδικασία παρασκευής και ανάλυσης λογισμικού). [*]
Αν όμως κάποιος θέλει σώνει και ντε, πραγματικά, αληθινά, πέρα για πέρα τυχαίους αριθμούς (και είναι δύσκολο να φανταστεί κανείς γιατί, αλλά τέλος πάντων) μια από τις λίγες ασφαλείς λύσεις είναι να προσπαθήσει να τους εξάγει από μια εγγενώς τυχαία φυσική διαδικασία, την ραδιενεργό β-διάσπαση. Ενώ ο κατά μέσο όρο χρόνος διάσπασης ενός ραδιενεργού πυρήνα μας είναι γνωστός με μεγάλη ακρίβεια, το χρονικό σημείο στο οποίο θα διασπαστεί ένας συγκεκριμένος πυρήνας όχι μόνο είναι άγνωστος, αλλά επίσης εγγενώς τυχαίος. Συγκεκριμένα, έχει 50% πιθανότητα να διασπαστεί σε χρόνο μικρότερο απ’το μέσο όρο, και 50% πιθανότητα να το κάνει σε χρόνο μεγαλύτερο απ’το μέσο όρο. Μετρώντας το χρόνο ανάμεσα σε δυο διαδοχικές διασπάσεις συλλέγει κανείς μηδενικά και άσους αν είναι μικρότερος ή μεγαλύτερος απ’το μέσο όρο και μετατρέπει τα μηδενικά και τους άσσους σε floating point πραγματικούς με την επιθυμητή ακρίβεια στο επιθυμητό διάστημα.
Τώρα όλος αυτός ο τζερτζελές είναι διαθέσιμος και μέσω δικτύου, από την υπηρεσία Hotbits. Εκεί, ένας μετρητής Geiger-Mueller (ένα μαραφέτι που κάνει κλικ κάθε που ένα σωματίδιο ικανό να ιονίσει άτομα περνάει μέσα του) μπροστά από ένα δείγμα ραδιενεργού Καισίου 137 (το ίδιο είδος ατόμου αλλά διαφορετικό ισότοπο χρησιμοποιείται για να ορίσει το δευτερόλεπτο), μετράει τον χρόνο ανάμεσα σε διαδοχικές “εκπυρσοκροτήσεις” ατόμων Καισίου και σας σερβίρει φρέσκους και ζεστους αληθινά τυχαίους αριθμούς (αλλά και passwords). Καλή τύχη!
[*]στην πραγματικότητα μια απ’τις εφαρμογές που χρειάζονται τυχαίους αριθμούς είναι μια τεχνική αριθμητικής ολοκλήρωσης που, όχι τυχαία, αποκαλείται μέθοδος Μοντε Κάρλο. Στις περισσότερες των περιπτώσεων μπορεί κανείς να χρησιμοποιήσει σύνολα αριθμών που λέγονται Quasi-random, και όχι μόνο δεν είναι τυχαίοι, αλλά ούτε καν συμπεριφέρονται ως τυχαίοι: συμπεριφέρονται πολύ καλύτερα για τις εφαρμογές που συζητάμε (δείτε εδώ για μια made by lazopolis εισαγωγή).
Ωραίοι οι ψευδοτυχαίοι, αλλά να μην μιλήσω για την πχιότητα του σοφτγουέαρ (sic). Ευτυχώς που είσαι φυσικός
Ποιουνού σόφτγουέαρ;
“τα τυχαία passwords, τα gotcha”
Αγαπητέ lazopolis…μήπως εννοείς τα captcha?
http://en.wikipedia.org/wiki/Captcha
“Αυτό σημαίνει οτι ο αλγόριθμος παράγει ένα πακέτο π.χ. 10 δις αριθμών που περνάνε με επιτυχία ένα μεγάλο σύνολο από τεστ…”
Όμως αυτό δεν συμβαίνει στις “απλές” γεννήτριες ψευδοτυχαίων αριθμών, όπως αυτές που είναι βασισμένες σε κάποιο πολυώνυμο στο δυαδικό σύστημα (http://en.wikipedia.org/wiki/Linear_feedback_shift_register). Αν φτιάξεις μια τέτοια στα 8bit για παράδειγμα θα δείς το “ψεύδο” με κεφαλαία
Πραγματικά τυχαίες ακολουθίες (και αριθμοί) χρειάζοντε και στις τηλεπικοινωνίες όταν προσπαθείς να βγάλεις πειραματικά την επίδοση ενός “μακρύ” Forward Error Correcting Code (http://en.wikipedia.org/wiki/Forward_error_correction)
Αυτό με το hotbits δεν είναι καινούριο αν δεν κάνω λάθος (;)
ΑΑ καλώς ήρθες
Captcha, gotcha, whatever αυτά τέλος πάντων. Ευχαριστώ όμως για το λινκ γιατί έμαθα επιτέλους τί σημαίνει το ακρωνύμιο.
Σχετικά με τους ψευδοτυχαίους, η φτηνή παρασκευή τους είναι ένα είδος τέχνης. Οι απλούστεροι αλγόριθμοι που ξέρω με αρκετά μεγάλες περιόδους για ρεαλιστικές χρήσεις είναι linear congruence μέθοδοι με προσεγμένες παραμέτρους.
Στις επικοινωνίες γιατί χρειάζονται πραγματικά τυχαίες ακολουθίες; Αν σου δώσω μια ακολουθία αριθμών που περνάει τα στάνταρ τεστ τυχαιότητας και έχει σχετικά μεγάλη περίοδο, σε ενδιαφέρει αν είναι πραγματικά τυχαία ή ψευδοτυχαία;
Το hotbits σαν εφαρμογή δεν είναι καινούριο, το web interface δεν ξέρω αν προυπήρχε όμως. Πάντως εγώ τώρα το ανακάλυψα. Αν πιστέψουμε βέβαια την “Last update: September 2006 ” δήλωση στην ιστοσελίδα, ε, τότε, μάλλον δεν το λες και καινούριο
Ωραίο ποστ, αλλά δεν μας είπες πού τους βρίσκεις τους ψευδοτυχαίους. Εγώ χρησιμοποιώ τη sprng:
http://sprng.cs.fsu.edu/
το βασικό πλεονέκτημα της οποίας (πέρα από το γεγονός ότι μπορείς να επιλέξεις τη γεννήτρια) είναι ότι σου επιτρέπει να έχεις πολλά χωριστά streams και αν θέλεις κάνεις και spawning/branching από τα υπάρχοντα.
@agezerlis: καλώς ήρθες και ευχαριστώ για το σύνδεσμο.
Προσωπικώς χρησιμοποιώ δικές μου ρουτίνες για ψευδοτυχαίους αριθμούς, αλλά πρόκειται για απλές κωδικοποιήσεις πασίγνωστων αλγορίθμων που κάνουν τη δουλειά γρήγορα αλλά σωστά, όπως π.χ. ο RANLUX (δε βρίσκω πρόχειρο καλύτερο σύνδεσμο από αυτό το implementation το οποίο δε χρησιμοποιώ αλλά δίνει κάποια στοιχεία και την κλασσική αναφορά σε Luescher και James) που είναι κι αυτός ένας linear congruence algorithm.
Αλλά δεν έχει τύχει ακόμα να χρειαστώ πολλά χωριστά streams. Απ’την άλλη, κάθε υποσύνολο ψευδοτυχαίων αριθμών είναι (υποτίθεται) το ίδιο ψευδοτυχαίο με το αρχικό σύνολο, οπότε, τί σημαίνει branching; Εγγυάται οτι δεν δίνει πάνω από μια φορά τον ίδιο αριθμό στην ακολουθία;
Απ’ότι βλέπω η default γεννήτρια του SPRNG είναι απλώς ένας “48 Bit Linear Congruential Generator with Prime Addend”. Πολύς σαματάς αν θες να χρησιμοποιήσεις μόνο το single processor mode του, κατά την ταπεινή μου γνώμη (άσε που δεν κατάφερα να το στήσω στο μακ λόγω ενός απευθείας link στην stdc++).
Σχετικά με το branching και τα χωριστά streams: ο λόγος είναι όταν π.χ. έχεις 5000 χωριστούς walkers (ή όπως αλλιώς θέλεις να τους πεις) και τους στέλνεις σε π.χ. 100 επεξεργαστές. Αν χρησιμοποιείς ένα stream (αντί για 5000) τότε τη μία φορά θα αρχίσει να τρέχει πρώτα ο επεξεργαστής 34, μετά ο 76 κ.λπ., ενώ την επόμενη φορά θα αρχίσουν με διαφορετική σειρά (κι αυτό έχει να κάνει με τον cluster, συνήθως δεν το ελέγχουμε εμείς). Ακόμα όμως κι αν αρχίζουν πάντα με την ίδια σειρά, τι γίνεται όταν θέλεις να τρέξεις σε 55 επεξεργαστές, όχι 100; Το πρόβλημα λύνεται αν κάθε walker έχει δικό του stream. Τότε τρέχεις τον ίδιο κώδικα σε 50, 100, 200 επεξεργαστές και δίνει πάντα το ίδιο αποτέλεσμα. Το branching βασικά είναι ούτως ώστε να ξέρεις ότι το stream με αριθμό 5001 δεν ταυτίζεται με κανένα από τα προηγούμενα 5000 (σχετικά τετριμμένο στο παράδειγμα που έδωσα, αλλά αν είχες απ’ την αρχή εκατομμύρια streams τότε χοντραίνει το θέμα).
Σχετικά με την default γεννήτρια: συμφωνώ, και μάλιστα παλιότερα είχα πάθει ζημιά επειδή μου τελείωσε η περίοδος της… Συμφωνώ επίσης ότι για single-processor δουλειές παραείναι μεγάλος ο μπελάς.
Διόρθωση (είναι αργά εδώ
): αυτό με τον επεξεργαστή 34, μετά τον 76 κ.λπ. είναι λάθος. Το σωστό επιχείρημα είναι το επόμενο, δηλαδή ότι τρέχεις σε όποιον αριθμό επεξεργαστών θέλεις και το αποτέλεσμα είναι πάντα το ίδιο.
Εκατομμύρια streams; Μα τί κάνετε τέλος πάντων εκεί στη έρημο;;;
“η φτηνή παρασκευή τους είναι ένα είδος τέχνης.”
Όντως.
Ένας εναλακτικός τρόπος για να φτιάξεις πραγματικά τυχαίους αριθμούς είναι να πάρεις μια δίοδο, να τη πολώσεις ανάστροφα και να αυξήσεις το δυναμικό μέχρι κάποια περιοχή κοντά στη τάση διάσπασης (όχι απαραίτητα στο 100%), κρατόντας το ρεύμα χαμηλά ώστε να μη την κάψεις. Κάποια στιγμή αρχίζουν τα ηλεκτρόνια να “πηδάνε” το depletion region δίνοντας παλμούς. Μπορείς να ρυθμίσεις τη τάση ώστε η έξοδος να “μοιάζει” με ένα συνεχές σήμα. Απο εκεί και πέρα με ένα threshold (σε οποιαδήποτε τάση ανάμεσα στο 0 και τη τάση λειτουργίας) θα σου δώσει παλμούς με τυχαίο πλάτος όπως ακριβώς και στο hotbits.
“Στις επικοινωνίες γιατί χρειάζονται πραγματικά τυχαίες ακολουθίες; Αν σου δώσω μια ακολουθία αριθμών που περνάει τα στάνταρ τεστ τυχαιότητας και έχει σχετικά μεγάλη περίοδο, σε ενδιαφέρει αν είναι πραγματικά τυχαία ή ψευδοτυχαία;”
Το θέμα είναι να προέρχοντε απο μια πραγματικά επίπεδη κατανομή ώστε να μην υπάρχει bias. Ουσιαστικά η πηγή θα πρέπει να παράγει 0 και 1 με πιθανότητα 0.5
Αν δεν κάνω λάθος, δεν υπάρχει κάποια αναλυτική μέθοδος με την οποία να υπολογίζεις το πολυώνυμο που αναφέρω στο link παραπάνω…Ένα τυχαίο πολυώνυμο ίσως “παγιδεύεται” γύρω απο ένα υποσύνολο καταστάσεων (για δεδομένο μήκος λέξης). Οπότε δεν είναι απαραίτητο οτι ο αριθμός των 0 θα είναι περίπου ίσος με τον αριθμό των 1.
(Για το hotbits, ρισκάρω να πώ τουλάχιστον 1998
μπορεί να κάνω και λάθος όμως και να ήταν κάποιο παρόμοιο)
@AA: έχω την εντύπωση πως η κατηγορία feedback shift registers δεν είναι η καλύτερη που κυκλοφορεί. Επίπεδη κατανομή παίρνεις οπωσδήποτε με έναν σωστά ρυθμισμένο linear congruence αλγόριθμο για αρκετά μεγάλες ακολουθίες (αλλά όχι αστρονομικές). Αν ενδιαφέρεσαι για τη συμπεριφορά τους σε πολλές διαστάσεις (>10) ίσως έχει νόημα να κοιτάξεις και τους πιο hype Mersenne twister αλγόριθμους.
Πάντως το να είναι επίπεδη η κατανομή είναι το πρώτο και σχετικά εύκολο να επιτευχθεί σκαλοπάτι. Κάπως δυσκολότερο είναι να έχεις τη διασπορά και τις ψηλότερες ροπές που πρέπει. Αν σας ενδιαφέρει να είναι όσο πιο επίπεδη η κατανομή και χωρίς το clustering των (ψευδο)τυχαίων ακολουθιών, χρησιμοποιείστε κουάσι-ράντομ ακολουθίες (ότι πιο τρέντυ) !
Δεν διαφωνώ. Μπορείς όμως να τους φτιάξεις πολύ γρήγορα σε στοιχειώδες hardware. Τα πολυώνυμα ανακαλύπτοντε πειραματικά νομίζω.
Προσωπικά όταν το χρειάστηκα χρησιμοποίησα την απλή rand() που αν δεν κάνω λάθος είναι linear congruence (ο standard υπολογισμός με το modulo). (Μικρά codewords, λίγες επαναλήψεις, σε περιπτώσεις με πιο δυνατούς κώδικες χρειάζεται σίγουρα μια πιο δυνατή γεννήτρια και ευχαριστώ για τα links
)
Σε περισσότερες διαστάσεις γιατί να αλλάζει η συμπεριφορά; Αν χωρίσεις μια μονοδιάστατη ακολουθία τυχαίων σε υποσύνολα των Ν, τα σημεία στο χώρο που θα προκύψει δεν θα είναι και πάλι τυχαία κατανεμημένα με τα ίδια χαρακτηριστικά;
Σε περισσότερες διαστάσεις εμφανίζονται (μιλάμε πάντα για ψευδοτυχαίους) μυστήρια correlations, όπως ας πούμε να πέφτουν πολλά σημεία πάνω σε παράλληλα διαγώνια (υπερ)επίπεδα (δες Marsaglia effect).
Με αφορμή την κουβέντα μας, κοίταξα και πάλι στο The making of the atomic bomb (Μυθικό βιβλίο
) γιατί για κάποιο λόγο (καλό όπως αποδείχτηκε 
) ερχόταν στο μυαλό μου το όνομα του Von Neuman σε αυτή την “τυχαία” συζήτηση που ανοίξαμε.
Μετά το Marsaglia effect, νομίζω οτι ταιριάζει κάτι που είχε πεί ο ίδιος (και το βρήκα στο wikipedia).
“Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.”
Ίσως οι τύποι που σκαρφίζεται το ανθρώπινο κεφάλι να έχουν κάτι απο τηn προβλεψιμότητα του
γραψε τη γνωμη σου