Periodenlänge < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:12 Mi 05.01.2011 | | Autor: | rainerS |
Hallo!
Erstmal herzlich ![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]")
> kann jemand den Satz von Knuth / Carmichael beweisen wie
> die Werte seien müseen um eine max. Periodenlänge beim
> Linearen Kongruenz Generator zu erreichen?
Schau doch einfach bei Knuth nach: The Art of Computer Programming, gleich am Anfang von Band 2 (Abschnitt 3.2.1.2).
> Gibt es weitere interessante Werte für die Konstanten oder
> das Modul, die man untersuchen könnte?
Steht alles bei Knuth.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:13 So 13.03.2011 | | Autor: | Rat62 |
Der in Java verwendete Lineare Kongruenzgenerator der Klasse Random
benutzt
modulus m = 2^48 - 1 = 3*3*5*7*13*17*97*241*257*673
Multiplikator a = 0x5DEECE66D = 7 * 443 * 739 * 11003
Increment c = 11
Es gilt a-1 = 2*2*3*757*787*3527
Mit diesen Werten wird nach dem Satz von Knuth nicht die volle Periodenlänge m erreicht, sie muss also kürzer sein. Wie lang?
Ich habe als Startwert X0 = 0 gesetzt.
Sei P(X0,a,c,m) die Periodenlänge eines LCG mit den entsprechenden Parametern. Wenn ich Knuth 2, Kap 3.2.1.2 Lemma Q richtig verstanden habe, müsste ich die Periodenlänge des Java-Randomgenerators bestimmen können, indem ich die Periodenlängen der 9 Generatoren bestimme, die sich aus der Primfaktorzerlegung von m ergeben.
P(0,0x5DEECE66D mod 9,2,9) = 9
P(0,0x5DEECE66D mod 5,1,5) = 4
P(0,0x5DEECE66D mod 7,4,7) = 1
P(0,0x5DEECE66D mod 13,11,13) = 4
P(0,0x5DEECE66D mod 17,11,17) = 16
P(0,0x5DEECE66D mod 97,11,97) = 12
P(0,0x5DEECE66D mod 241,11,241) = 120
P(0,0x5DEECE66D mod 257,11,257) = 256
P(0,0x5DEECE66D mod 673,11,673) = 42
Das kleinste gemeinsame Vielfache dieser Einzelperioden ist nur 80640. Das ist aber ganz offensichtlich nicht die Periodenlänge des Random-Generators.
Ich sehe meinen Fehler nicht. Kann mir jemand helfen?
Danke
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 So 13.03.2011 | | Autor: | Rat62 |
Tach zusammen.
Ausprobieren hilft.
Mit *diesen* Werten hat man tatsächlich nur eine so kurze Periode.
Dass man das in Java mit der Klasse Random nicht nachvollziehen kann, liegt daran, dass ich den Modulus falsch angegeben hatte.
Die Rechenvorschrift ist
seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)
Die UND-Verknüpung entspricht einem modulo 2^48.
Dann passen auch die Voraussetzungen des Satzes von Knuth und die Periodenlänge ist die volle Länge 2^48.
Ich habe wieder dazugelernt.
Trotzdem vielen Dank für Eure Aufmerksamkeit.
Jetzt muss ich das noch irgendwie als erledigt markieren.
|
|
|
|
