Zufallszahl in Assembler...

  • Hallo.


    ich übersetze gerade zum Spaß ein paar Basicprogramme in Assembler und bin auf der Suche nach einer Lösung, um Zufallszahlen zu generieren. In Basic ist das ja mit RND kein Problem. Aber wie mache ich das in Assembler ? Ich habe beim Apple 2 Plus keine Timer, geschweigedenn einen pseudo random generator. Das einzige was ich gefunden hatte war dieKeyin Subroutine $FD1B. Diese wartet auf einen Tastendruck und erzeugt eine Zufallszahl. Aber ich will nicht auf einen Tastendruck warten.. :)

    Evtl. finde ich bei dieser Routine ja die Lösung im ROM Listing. Oder hat einer von euch ne gute Idee, eine random routine zu programmierenß


    Gruß Jan

  • Hallo Jan,


    such doch mal nach "6502 pnrg", da gibt es verschiedene fertige Lösungen mit Dokumentation usw.


    Schöne Grüße,

    Hans

    Habe: TI-99/4A + PEB, Sharp MZ-800, Apple IIe, Symbolics MacIvory 2, ZX Spectrum, Macintosh IIfx, C64, VAX 4000-600, VAX 4000-105A, VAXStation 4000/90A, VAXStation VLC, Digital Personal Workstation 500au, Schneider CPC 464, CBM 3032 Biete: Atari 800XL, TI-99/4A, Atari Mega 1, Atari 1040STfm Suche: 1/2'' Bandlaufwerk SCSI, Reparaturbedürftiges 8+16bit

    Retrocomputing Slack @hanshuebner

  • Also irgendetwas, was nicht völlig vorhersehbar ist, wirst du brauchen, damit du einen Seed für einen Pseudo-Zufallszahlen-Algorithmen bekommst.

    Die Zeit, bis ein physisches/analoges Ereignis eintritt, könnte da helfen. Am einfachsten ist das, wenn eine Benutzereingabe nötig ist - und man die Zeit bis zu dieser Eingabe zählt.

    Aber es könnte auch gehen, dass man verschiedene Sektoren auf einer Diskette anfragt und die Zeit einbezieht, die gebraucht wird, um die Sektoren zu finden (sollte ja jedesmal ein klein wenig anders sein).



  • Aber es könnte auch gehen, dass man verschiedene Sektoren auf einer Diskette anfragt und die Zeit einbezieht, die gebraucht wird, um die Sektoren zu finden

    Wie wär's mit der Zeit bis der erste / zu lesende Sektor gefunden ist.

    Keiner kann wissen, wo die Diskette bis dahin gedreht wurde.


    Aber ist die Frage, ob sich sowas ausmessen lässt, bzw sowas einen anständigen Anfangswert ergibt.

    ;------------------------------------
    ;----- ENABLE NMI INTERRUPTS
    (aus: IBM BIOS Source Listing)

  • Ich kann mir irgendwie gerade nicht vorstellen, daß ein Homecomputer nicht igendwo einen "Timer" hat. Und wenns der Videostrahl ist.

    Da kenn ich 'ne Menge.

    Beim Z80 wurde gerne das Refresh Register für sowas genommen.

    ;------------------------------------
    ;----- ENABLE NMI INTERRUPTS
    (aus: IBM BIOS Source Listing)

  • Ich kann mir irgendwie gerade nicht vorstellen, daß ein Homecomputer nicht igendwo einen "Timer" hat. Und wenns der Videostrahl ist.

    Ich kenne den Apple nicht, daher weiß ich nicht, ob der sowas integriert hat. Im Schneider CPC gibt es vom Betriebssystem einen Timer. Sobald man da aber die Firmware nicht mehr verwendet, ist man auch auf sich selbst gestellt.

    Ein Timer bringt nur was, wenn du sicher stellst, dass ein zufälliges Element enthalten ist, wann er ausgelesen wird. Im Schneider CPC funktioniert das gut, weil nach Start des Computers IMMER Nutzeraktionen nötig sind. Der Timerwert zählt zwischenzeitlich alle 1/300s um eins hoch. Bis das Programm gestartet ist, hat man einen für die meisten Anwendungen hinreichend zufälligen Seed.

    Wenn deine Firmware das nicht übernimmt und dein Programm selbst einen Timer startet und dann nach exakt X Zyklen wieder ausliest, ist das nicht zufällig. Eine Nutzerinteraktion braucht es, oder ein irgendetwas anderes, dass der Timerwert nicht vorhersehbar wird.

  • Ich kann mir irgendwie gerade nicht vorstellen, daß ein Homecomputer nicht igendwo einen "Timer" hat. Und wenns der Videostrahl ist.

    Da kenn ich 'ne Menge.

    Beim Z80 wurde gerne das Refresh Register für sowas genommen.


    Kennst du welche für den Apple 2+? Ich glaub das war spezifisch für dieses System.

    Das R-Register im Z80 ist oft "good enough", man muss aber aufpassen, da es nur 128 Werte annimmt und solange es keine unvorhersehbare Interaktion wie eine Nutzereingabe gibt, ist nach dem ersten Zugriff auf das R-Register die Folge dann auch wieder perfekt vorhersehbar.

    Aber ist die Frage, ob sich sowas ausmessen lässt, bzw sowas einen anständigen Anfangswert ergibt.

    Hängt sicher auch vom System ab. Eine einzelne Aktion wird wohl keinen ausreichend zufälligen Seed haben. Aber mehrere, und jeweils bei der Zeitmessung nur das niedrigste Bit nehmen, dann könnte das hinreichend Zufall beinhalten. Müsste man mal ausprobieren.

  • Gruß Torsten

    BFZ MFA, ZX80Core, AX81, ZX81, ZX81NU, Spectrum+, Harlequin, MSX VG8010, Amstrad NC100, Cambridge Z88, C64, C128D, Amiga 500 & 1200, Atari Portfolio, HP200LX, IBM PC5155, TP755c, TP755cx, T20, T41, T61, PS/2 (Model 40SX), PS/2E, Accura 101, Apple //e, Sharp PC1401 & PC1403H, TI59 m. PC-100c, HP48SX & HP48GX


    ::matrix::

  • Hallo Jan1980 ,

    die Lösung hängt von deinen Anforderungen an die (pseudo)Zufallzahl ab, d.h. welche Anforderungen du an Gleichverteilung, Zykluslänge etc. stellst. Wenn es eine Folge der Werte x'00 - x'FF in zufälliger Anordnung schon tut (z.B. für Spiele), ist der Tipp mit 6502 PNRG von hans super, zumal du die Routine auch von 8 auf mehr Bit ausweiten kannst.


    Wenn du Basicprogramme in Assembler übersetzt, die RND nutzen, brauchst du in der Regel auch eine Floatingpoint-Bibliothek, um die weiteren Berechnungen mit RND in Assembler nachzuvollziehen. Wenn du das hast, dann ist folgender Algorithmus recht gut:


    RND(i+1) = INT(997 * RND(i) ) mit RND(i=1) = 0,5284163 oder jede andere Dezimalzahl mit 7 Stellen nach dem Komma, wobei die 7. Nachkommastelle eine 1, 3, 7 oder 9 sein muss.


    Die generierten Zufallszahlen sind gleichverteilt und haben eine Periode von 500.000 (Quelle: hp Stat Pak für hp67)


    In einem Programm gebe ich dem Generator gerne einen Vorlauf von n Perioden, wobei ich n aus irgendeiner Nutzerinteraktion ableite.


    Mit dem Generator bist du Plattform-unabhängig und er ist bzgl. statistischem verhalten geprüft.


    Ein sehr schöner optischer Test der Zufallszahlen ist übrigens, wenn wenn du { RND(i), RND(i+1) } ; { RND(i+1), RND(i+2) } ; usw ... als Punktmuster plottest. Wenn du da statt einer sich gleichförmig füllenden Fläche mit Punktenebel irgendwelche Muster siehst, ist irgend etwas faul.


    Roland

  • Man kann auch ein paar niederwertige Bits der Joystick-Eingänge als Seed verwenden - die sind nicht besonders reproduzierbar und haben immer ein leichtes Rauschen drauf - Mehrfach abfragen und jeweils die niederwertigen Bits verwenden, um z.B. ein Byte zusammenzubauen.

  • nach dem ersten Zugriff auf das R-Register die Folge dann auch wieder perfekt vorhersehbar.

    Das Problem hast du bei Pseudo-Zufallszahlen immer. Ist eben nur eine Berechnung.

    ;------------------------------------
    ;----- ENABLE NMI INTERRUPTS
    (aus: IBM BIOS Source Listing)

  • In der Datenbank FileMaker habe ich eine Zufallszahl so gemacht:


    Die Zeit abgefragt und dann die Sekunden genommen. Diese dann

    durch 60 geteilt, so habe ich einen Wert von 0 - 1 erhalten. Dies ist

    aber noch nicht zufällig, da der Wert während einer Minute von

    0 auf 1 steigt. Damit diese Zahl zufällig wird, habe ich den Wert

    durch einer Primzahl, z.B. 13 geteilt. Von diesem Ergebnis habe ich

    dann die 3. Nachkommastelle genommen.


    Oder wenn ich eine zweistellige Zahl brauchte, habe ich die

    3. und 5. Nachkommastelle genommen.


    Natürlich kann man die Zahl auch mit einer Primzahl multiplizieren

    und dann z.B. die beiden Nachkommastellen nehmen. Da gibt es

    sicher noch mehr Varianten, aber der Ansatz bleibt sich gleich.


    LG Rappi

  • Man kann auch ein paar niederwertige Bits der Joystick-Eingänge als Seed verwenden - die sind nicht besonders reproduzierbar und haben immer ein leichtes Rauschen drauf - Mehrfach abfragen und jeweils die niederwertigen Bits verwenden, um z.B. ein Byte zusammenzubauen.

    Charmant!

    Was man natürlich noch bedenken sollte (heutzutage) ist, dass analoge Inputs nur in realer Hardware ein Rauschen haben - in Emulatoren dürfte das ggf. nicht klappen - jedenfalls nicht, wenn der Programmierer des Emulators dieses Rauschen nicht vorgesehen hat. Gilt entsprechend auch für meine Idee mit dem Laufwerk, wo der Zugriff im Emulator komplett determiniert sein dürfte.

  • Charmant!

    Was man natürlich noch bedenken sollte (heutzutage) ist, dass analoge Inputs nur in realer Hardware ein Rauschen haben - in Emulatoren dürfte das ggf. nicht klappen - jedenfalls nicht, wenn der Programmierer des Emulators dieses Rauschen nicht vorgesehen hat. Gilt entsprechend auch für meine Idee mit dem Laufwerk, wo der Zugriff im Emulator komplett determiniert sein dürfte.

    Nein, mit einem Emulator funktioniert das wahrscheinlich nicht (wobei: Emus sind neuerdings oft ganz schön pfiffig... AppleWin z.B. kann den Analogstick des PCs benutzen - da dürfte auch ein Rauschen draufsein).


    Aber wer benutzt schon einen Emulator, wenn er was besseres hat... ;)

  • Vielen Dank für die ganzen Antworten. Einige Ideen hatte ich schon selber, zB die Abfrage der Paddles in Anbetracht des Rauschens. Die Idee mit der Abfrage des Diskettenlaufwerks ist interessant. Allerdings soll es funktionieren ohne Peripherie.

    Ich wollte das Programm Kaleidoskop von Basic nach ASM übersetzen. In Basic sind das ja nur ein paar Zeilen. In Assembler über ne DIN A4-Seite versteht sich. Im Grunde genommen nichts schwieriges wäre da nicht die Sache mit dem random.


    Bei anderen Systemen wüsste ich, wie ich die Routine verwirklichen könnte. Speziell beim Apple 2 aber nicht.


    Der Apple 2 hat:


    - Keine Rasterzeilenabfrage

    - Keine eingebaute Uhr

    - Keinen pseudo random generator

    - Keinen Timer

    - Tastaturabfrage über polling


    Anscheinend hatte es Woz nicht so mit Interrupts und Timern ?!


    In der Zeropage an den Adressen $4e und $4f ist die Ablage für rdkey/random Routine. Ich hab gestern Abend mal in das ROM Listing geschaut. Da wurde nur inkrementiert, geshiftet und dekrementiert. Also nichts halbes und nix ganzes. Ich schau mir jetzt erstmal die ganzen Links von euch an und wollte mal kucken wie Applesoftbasic RND realisiert.


    Achso. Die Zufallszahl soll eine Integerzahl zwischen $00 und $ff sein.



    Gruß Jan

  • Der Apple 2 hat:


    - Keinen pseudo random generator

    Einen Pseudo Random Number Generator (PNRG) "hat" ein Rechner nicht, den muss man sich eben programmieren. Darauf bezog sich mein Hinweis. Wenn Du dann möchtest, dass der PNRG nicht jedes Mal die gleiche Zahlenfolge erzeugt, musst Du ihn initialisieren, und dafür brauchst Du eine mehr oder weniger zufällige Zahl. Eine Idee noch: Wenn Du vom Benutzer irgendwelche Tasten abfragen musst, dann mach das doch mit Polling und messe dabei, wie viel Zeit zwischen den Tastendrücken vergeht (also mit einem einfachen Zähler). Den kannst Du dann für die Initialisierung des PNRG benutzen.


    -Hans

    Habe: TI-99/4A + PEB, Sharp MZ-800, Apple IIe, Symbolics MacIvory 2, ZX Spectrum, Macintosh IIfx, C64, VAX 4000-600, VAX 4000-105A, VAXStation 4000/90A, VAXStation VLC, Digital Personal Workstation 500au, Schneider CPC 464, CBM 3032 Biete: Atari 800XL, TI-99/4A, Atari Mega 1, Atari 1040STfm Suche: 1/2'' Bandlaufwerk SCSI, Reparaturbedürftiges 8+16bit

    Retrocomputing Slack @hanshuebner

  • Das Problem ist, dass die Zufallszahl ohne Äußere Einflüsse entstehen soll, d.h. ohne Tastendruck. Andernfalls könnte ich das mit einem Counter realisieren, wie von dir erwähnt.


    So würde er zB das X-Register andauernd dekrementieren bis man Space drücken würde, dann bekäme man eine Zufallszahl. Aber hier is wieder der äußere Einfluss im Sinne des Drückens der Space-Taste..



    Gruß Jan

  • Naja, er will nur nicht für jede Zufallszahl auf einen Tastendruck warten, aber vielleicht geht das ja einmal beim Start des Programms, um den PRNG zu initialisieren?

    Habe: TI-99/4A + PEB, Sharp MZ-800, Apple IIe, Symbolics MacIvory 2, ZX Spectrum, Macintosh IIfx, C64, VAX 4000-600, VAX 4000-105A, VAXStation 4000/90A, VAXStation VLC, Digital Personal Workstation 500au, Schneider CPC 464, CBM 3032 Biete: Atari 800XL, TI-99/4A, Atari Mega 1, Atari 1040STfm Suche: 1/2'' Bandlaufwerk SCSI, Reparaturbedürftiges 8+16bit

    Retrocomputing Slack @hanshuebner

  • Ah jetzt rutscht der Groschen. Nehmen wir mal folgendes an:


    1. Es erscheint ein Startbildschirm, der das Programm bzw. den Namen desselben anzeigt und zum beginnen muß man eine Taste drücken.

    2. Der Counter läuft direkt los mit erscheinen des Startbildschirms.

    3. Die Zeit zwischen Programmstart und drücken der Taste wird immer eine andere und immer zufällig sein.


    Somit würde man schon zu Beginn des Spiels bzw. Programms das "Verhalten" desselben bzgl des späteren Verlaufs beeinflussen.


    Man könnte auch anstatt einem Register mehrere Counter in der Zeropage laufen lassen und dann daraus eine Zahl berechnen.


    So könnte man eine richtige Zufallszahl erzeugen lassen..


    EDIT: Man könnte parallel Counter in einem Register, in der Zeropage und in einer normalen Speicherstelle laufen lassen. Das Zählen wäre unterschiedlich schnell und daus könnte man eine Zahl errechnen.


    Gruß Jan

  • So könnte man eine richtige Zufallszahl erzeugen lassen..

    Ja, eine zufällige Zahl zur Initialisierung des PNRG. Der PNRG erzeugt dann zwar eine vorhersagbare Zahlenfolge, aber eben eine durch die zufällige Zahl ausgewählte von tausenden verschiedenen.

    Habe: TI-99/4A + PEB, Sharp MZ-800, Apple IIe, Symbolics MacIvory 2, ZX Spectrum, Macintosh IIfx, C64, VAX 4000-600, VAX 4000-105A, VAXStation 4000/90A, VAXStation VLC, Digital Personal Workstation 500au, Schneider CPC 464, CBM 3032 Biete: Atari 800XL, TI-99/4A, Atari Mega 1, Atari 1040STfm Suche: 1/2'' Bandlaufwerk SCSI, Reparaturbedürftiges 8+16bit

    Retrocomputing Slack @hanshuebner

  • EDIT: Man könnte parallel Counter in einem Register, in der Zeropage und in einer normalen Speicherstelle laufen lassen. Das Zählen wäre unterschiedlich schnell und daus könnte man eine Zahl errechnen.


    Das klingt kongenial, aber wie willst Du das lösen ? Das Erhöhen passiert ja nun nicht automatisch.

  • EDIT: Man könnte parallel Counter in einem Register, in der Zeropage und in einer normalen Speicherstelle laufen lassen. Das Zählen wäre unterschiedlich schnell und daus könnte man eine Zahl errechnen.

    Das wird so nicht gehen - die drei Operationen brauchen zwar unterschiedlich viel Zeit, können aber nicht gleichzeitig ausgeführt werden (außer, du hast einen 3-Core-6502.... - Und wenn du die drei Aktionen in eine Schleife packst, dann zählen sie auch gleichzeitig hoch.

  • Aufgrund dessen, dass diese Methode bisher noch nicht gefallen ist mische ich mich jetzt doch noch mal kurz ein. :S


    Von meinem DREAM 6800 weiß ich, dass das darauf laufende Betriebssytem einen sehr simplen und dennoch relativ gut funktionierenden Zufallsgenerator in Assembly besitzt. Dieser verwendet laut Beschreibung den beinahe zufälligen Maschinencode im ROM als Quelle für zufällige Zahlen.

    Allerdings wird, wenn man mit einem schwarzen Bildschirm anfängt und man ein Programm schreibt welches zufällig ausgewählte Pixel auf dem Bildschirm bemalt, der Bildschirm nach längerer Laufzeit wieder komplett schwarz, das ganze ist also eher Pseudo-Zufällig. Aber immerhin.


    Hier die kurze Beschreibung dazu wie dies funktioniert:

    Achtung: die hier beschriebene "CXKK"-Instruction ist keine MC6800-Instruction, sondern eine etwas höher-levelige Anweisung für die im Betriebssystem CHIPOS implementierte Sprache "CHIP-8".

    Eine, meiner Meinung nach, sehr schöne Implementation einer etwas einfacher zu verstehenden Programmiersprache in nur 1KiB EPROM!

    Mehr Infos zum (auch sehr eleganten) Computer und dem darauf laufenden Betriebssystem gibts auf dieser Seite: http://www.mjbauer.biz/DREAM6800.htm


    In MC6800 Assembly bin ich leider nicht so gut, aber ich poste trotzdem mal die dafür relevanten Abschnitte aus dem Listing:

    (Ich hoffe das ist alles was dafür verantwortlich ist, wenn was unklar ist oder fehlt befindet sich das Listing auch auf der oben genannten Webseite.)


    Wie gesagt bin ich in MC6800 Assembly relativ ratlos, aber soweit wie ich das verstehe geht das Programm abhängig vom "Startwert" durch die Daten im EPROM und behandelt diese einfach wie zufällige Zahlenwerte. Danach wird das dann noch ein bisschen durcheinandergeworfen und heraus kommen (fast) zufällige Zahlen.

    Einziger Nachteil ist (soweit ich das der Funktionsweise nach deuten würde), dass diese Funktion bei gleichem Startwert auch die gleiche Zahlenfolge liefert, somit also nur zufällige Zahlen vorgetäuscht werden. Kommt natürlich sehr darauf an wofür die Zufallszahlen verwendet werden sollen.


    Ich hoffe ich konnte vielleicht ein bisschen helfen oder zumindest eine neue Idee anstubsen... angst


    Beste Grüße,

    Magnus

  • Hier die kurze Beschreibung dazu wie dies funktioniert:

    Das ist natürlich ein Thema, das eigentlich nur Leute mit ausreichendem mathematischen Hintergrund diskutieren sollten - Dennoch, die Beschreibung riecht für mich nach Bullshit. Wenn das ein gutes Verfahren wäre, dann würde es sicherlich nicht nur in einem obskuren 6800-Betriebssystem verwendet werden.


    Aber was weiss ich schon von Mathematik? Ich steige beim Lesen der umfangreichen Wikipedia-Seite zu linear rückgekoppelten Schieberegistern, mit denen PNRGs meistens implementiert sind, bei der ersten Formel aus und überlege mir, was ich brauche: Ich will lange pseudozufällige Sequenzen, ich möchte davon eine aus möglichst vielen auswählen (gemäß unserer Diskussion über den Seed-Wert), und ich möchte, dass die Berechnung der nächsten "Zufallszahl" schnell geht. Damit gehe ich dann in die Bibliothek und nehme mir einen passenden Algorithmus, fertig.

    Ein sehr schöner optischer Test der Zufallszahlen ist übrigens, wenn wenn du { RND(i), RND(i+1) } ; { RND(i+1), RND(i+2) } ; usw ... als Punktmuster plottest. Wenn du da statt einer sich gleichförmig füllenden Fläche mit Punktenebel irgendwelche Muster siehst, ist irgend etwas faul.

    Das ist ein sehr guter Vorschlag, mit dem man sich veranschaulichen kann, ob ein Zufallszahlengenerator zufällig aussieht. Wenn etwas zufällig aussieht, ist das natürlich noch keine Garantie dafür, sich die Periodizität von zwei verschiedenen Sequenzen desselben Generators nicht stark überschneidet oder wiederholt. Wenn man aber Muster oder Klumpen erkennen kann oder Wertebereiche ganz fehlen, dann will man die Lösung vielleicht doch lieber gleich nicht nehmen - Wer will schon einen Würfel, bei dem die Seitenwahrscheinlichkeit nicht gleich ist?


    Es gibt so viele Sachen, bei denen sich neue Ideen lohnen. Das Thema Zufall ist aber ziemlich durchgespielt und "Ich nehme den Binärcode, guckst Du: Ist nur zufälliger Datensalat!" scheint mir nicht so originell und klug, als dass sich das als Ansatz lohnen würde. Bei solchen Fragestellungen empfiehlt es sich normalerweise, auf gut beschriebene Standardlösungen zu setzen - Zumindest, wenn man darüber sprechen/schreiben möchte :)


    P.S.: Vielleicht habe ich unrecht und ich lasse mich auch gerne korrigieren!

    Habe: TI-99/4A + PEB, Sharp MZ-800, Apple IIe, Symbolics MacIvory 2, ZX Spectrum, Macintosh IIfx, C64, VAX 4000-600, VAX 4000-105A, VAXStation 4000/90A, VAXStation VLC, Digital Personal Workstation 500au, Schneider CPC 464, CBM 3032 Biete: Atari 800XL, TI-99/4A, Atari Mega 1, Atari 1040STfm Suche: 1/2'' Bandlaufwerk SCSI, Reparaturbedürftiges 8+16bit

    Retrocomputing Slack @hanshuebner

  • zuAufgrund dessen, dass diese Methode bisher noch nicht gefallen ist mische ich mich jetzt doch noch mal kurz ein. :S


    Von meinem DREAM 6800 weiß ich, dass das darauf laufende Betriebssytem einen sehr simplen und dennoch relativ gut funktionierenden Zufallsgenerator in Assembly besitzt. Dieser verwendet laut Beschreibung den beinahe zufälligen Maschinencode im ROM als Quelle für zufällige Zahlen.

    Allerdings wird, wenn man mit einem schwarzen Bildschirm anfängt und man ein Programm schreibt welches zufällig ausgewählte Pixel auf dem Bildschirm bemalt, der Bildschirm nach längerer Laufzeit wieder komplett schwarz, das ganze ist also eher Pseudo-Zufällig. Aber immerhin.

    Das ist zwar ein simples, aber nicht besonders gut funktionierendes Verfahren, das keinen der mathematischen Ansprüche an einen Zufallszahlengenerator auch nur annähernd erfüllt:

    1. Wahrscheinlich kommen nicht alle möglichen Werte zwischen 0 und 255 überhaupt im ROM vor - vielleicht, weil der Opcode gar nicht belegt ist - manche Zufallszahlen werden also gar nicht erzeugt
    2. Wenn alle Zahlen tatsächlich vorkommen, dann sicher nicht statistisch gleichverteilt -So ein Generator wird also manche Zahlenfolgen bevorzugt vor anderen erzeugen
    3. Um ein zufälliges Byte aus dem ROM zu holen, braucht man ja auch wieder einen zufälligen Index - wo nimmt man denn den her? Das Probem des Random Seed bleibt also.
    4. Da man ja vorher nicht weiß, was eigentlich im ROM steht, kann es sein, dass sich bei dem Verfahren lokale Schleifen bilden (man also überhaupt nicht alle Bytes des ROMs garantiert benutzt)

    Solche Verfahren kann man nehmen, wenn man keine hohen Ansprüche an einen PRNG stellt - Spiele z.B.


    Ein halbwegs "richtiger" PRNG mit z.B. einem 16-Bit rückgekoppelten Schieberegister ist auch nicht wesentlich aufwendiger (das sind ein paar Zeilen Assembler), garantiert aber die Erfüllung der Ansprüche von oben. Der PRNG im z.B. Sinclair ZX Spectrum erfüllt diese Ansprüche, ist aber nur ca. 10 Zeilen Z80-Assembler lang. Holt man sich den Seed für den PRNG z.B. aus dem Z80-Refresh-Register, hat man schon einen ziemlich guten RNG.

  • geht das Programm abhängig vom "Startwert"

    Der Startwert ist ja das Problem hier. Egal welcher Algorithmus verwendet wird, wenn der Startwert nicht hinreichend zufällig ist, dann sind es auch die Zufallszahlen nicht. Ob man jetzt einen Pseudo-Zufallszahlengeneratoren nimmt, oder ins ROM schaut, wenn dein Seed determiniert ist, dann sind es auch die erzeugten Zahlen. Du brauchst immer eine Entropiequelle.

    Aus Wikipedia:

    Quote

    Die Entropie der generierten Zufallszahl kann jedoch nicht größer sein als die des Startwerts.

    Anders formuliert: wenn du immer mit dem gleichen Startwert deine Funktion aufrufst, dann bekommst du immer die gleiche Zufallszahlensequenz. D.h. du musst den Startwert irgendwie durch einen echten(!) Zufall ermitteln, damit deine anderen Zahlen auch zufällig erscheinen. Dazu gehört das immer wieder erwähnte "warten auf Tasten" oder das Rauschen auf den analogen Joystickports. Wenn du es jetzt schaffst 256 zufällige Startwerte zu generieren, dann hast du (bis zu) 256 verschiedene Sequenzen - aber eben auch nicht mehr. In einem Spiel könnte das schon dazu führen, dass ein intensiver Spieler nach den ersten paar Spielzügen weiß, wie der Computer weiter agieren wird. Bei einem 16 Bit Seed wären es schon (bis zu) 65536 verschieden Sequenzen.

  • Wirf mal nen Blick in Band 2 von Knuths "The Art of Programming". Das handelt von allen möglichen PRNGs, die in seinem Pseudo-Assembler programmiert sind. Ich schicke dir das Buch gleich per Mail.