Diskussion:Multiply-with-carry

Generelle Überarbeitungshinweise

Ja, diese Seite bedarf dringend der Überarbeitung. Als inhaltliche Vorlage kann und sollte der entsprechende Beitrag über MWC-RNG aus der englischen Wikipedia genommen werden. Dort wird zum einen die für das Verständnis des Verfahrens benötigte Mathematik ausführlich erklärt, und darüberhinaus sind die angegebenen Beispiele dort auch richtig und somit nachvollziehbar. Ich vermute, dass sich durch die drastische inhaltliche Kürzung in der deutschen Fassung ungewollt eine Reihe von Fehler eingeschlichen haben, welche nun aber unbedingt korrigiert werden sollten. Bisher sind mir beim ersten Betrachten der deutschen Seite schon die folgenden Dinge aufgefallen:

0) Die Rekursionsformel für allgemeine MWC-RNG (mit r > 0 Zustandsregistern) lautet meines Erachtens x[n] = (a * x[n-r] + c[n-r]) mod b, usw., darauf wird im Deutschen gar nicht eingegangen, da ist in der Beschreibung überall automatisch r = 1 gesetzt, was eigentlich ein unüblicher Spezialfall ist. Anders dagegen im dazu angegebenen Quelltext, was man im ersten Moment dann gar nicht verstehen kann. Das relativ groß gewählte r=(512,1024,4096,...) ist aber für die lange Periode dieser RNG hier entscheidend (und im Englischen auch ausführlich beschrieben).

1) Wieso ist das Carry c eines Produktes in der numerischen Welt in der textuellen Beschreibung maximal nur 31 Bit lang? Im angegebenen Quelltext kann es maximnal 32 Bit lang sein. Wenn ich z.B. für eine Im-Kopf-Rechnung a=x=255=0xff und b=2^8=256=0x100 nehme, was theoretisch durchaus möglich wäre, ergibt sich bei der numerischen Multiplikation von (a * x) bereits ein 16 Bit langes Produkt mit (a * x) = (0x00ff * 0x00ff) = 0xfe01. Mit anderen Worten, das höchte Bit im Carry des numerischen Produkt ist schon gesetzt, obwohl der alte c-Wert noch gar nicht dazu addiert wurde. Wenn noch ein Carry c < a z.B. mit c = 0x00fe dazu addiert wird, erhält man maximal sogar (0xfe01 + 0x00fe) = 0xfeff Das dürfte doch mit b=2^32 absolut analog sein. Das Carry eines Produktes besteht in der numerischen Welt meines Erachtens deshalb maximal aus genausoviel Bits wie zur Darstellung von (b-1) benötigt werden. Bei Binärpolynomen ist das selbstverständlich anders z.B. (0xff)^2 = (x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + x^0)^2 = (x^14 + ...), aber wir sind hier doch in der numerischen Welt, oder?

2) Das (extra neu erstellte?) Beispiel für den MWC-Algorithmis stimmt meines Erachtens an mehreren Stellen nicht. Es ergibt sich (für die angegebenen Ausgangswerte a=6, x[1]=3 und c[1]=2) der erste berechnete Wert x[2] mit a * x[1] + c[1] = 6*3+2 = 20 und nicht 33 wie in der Tabelle angegeben, damit x[2]=33 stimmt, müßte x[1]=5 sein, denn erst 6*5+3=33.

3) Die Dezimalbruchentwicklung von 33/59 ergibt (laut Windows-Taschenrechner) 0,55932203389830508474576271186441, die wenigen errechneten und in der Tabelle angegebenen Sequenzwerte in umgekehrter Reihenfolge also ...28813... kann ich in der Dezimalbruchentwicklung aber nirgendwo finden. Das ist natürlich im englischen Beispiel auch ganz anders.

4) In der Computerwelt ist es eigentlich üblich, alle Indizies mit 0 beginnen zu lassen, was auf der englischen Seite auch der Fall ist, warum nicht auch im Deutschen?

5) Warum übernimmt man nicht gleich das zum einen funktionierende und zum anderen ausführliche Beispiel von der englischen Seite? Gibt es da etwa lizenzrechtliche Gründe - ich will es doch nicht hoffen!

6) Wenn b = 2^32 ist, dann ist aber (b - 1) = 0xffffffff und nicht 0xfffffffe, wie im Quelltext für den CMWC-RNG angegeben. Trotzdem ist der Quelltext für den CMWC-RNG an dieser Stelle offensichtlich richtig, verglichen mit dem Rest des Internets. Warum ist das so, habe ich da etwas nicht mitbekommen?

7) Welche mathematische Notwendigkeit steckt hinter der Quelltextzeile "if (x < c) { ++x; ++c; }" aus dem Quelltext für CMWC-RNG? Die suchte ich in der textuellen Beschreibung bisher vergeblich. Hängt das evtl. mit 6) zusammen?

8) Das man aus praktischen Gründen lieber Primzahlen der Form q = (a * b^r + 1) wählt, statt p = (a * b^r - 1), wird auf der deutschen Seite ebenfalls überhaupt nicht erwähnt. Den Unterschied sieht man aber in der Binärdarstellung der Primzahl q dafür um so deutlicher bei (q-1) = (a|0|0|0|...|0|0). Diese sehr sehr vielen Nullen im gesamten unteren Teil erleichtern das Rechnen mit wirklich langen Zahlen drastisch.

9) Ein Link auf eine lange Liste mit möglichst vielen Primzahlen der Form p = (a * b^r - 1) bzw. q = (a * b^r + 1) mit b = 2^32 wäre sicherlich nicht verkehrt, das würde das fehlerträchtige Selber-Rechnen komplett ersparen.

Zum Schluß noch eine inhaltliche Frage: Gibt es den MWC-RNG evtl. irgendwo auch in der Welt der Binärpolynome? Dort ist das Generieren von irreduziblen Polynomen einer vorgegebenen Länge (das entspricht einer Primzahl in der numerischen Welt) nämlich wesentlich einfacher, sicherer und schneller. Irgendwelche Probleme mit der Periodenbestimmung wie in der numerischen Welt l=(p-1)=(a * b^r - 2), gibt es dort dann auch nicht. Denn die hängt bei Binärpolynomen nur von der Länge (also dem Grad) des Polynoms und nicht vom konkreten Polynom selbst ab. Der Übergang von b = 2^32 zu b = (2^32 - 1) wäre auch nicht notwendig, weil es ein Additions-Carry dort nicht gibt, denn bei Binärpolynomen wird bekanntlich nur mit XOR addiert und subtrahiert. Nur die binäre Carry-Multiplikation müßte dann per Softwareroutine ausgeführt werden, was sicherlich etwas langsamer wäre, als die numerische Multiplikation in einer ALU. Generell scheint mir die für numerische MWC/CMWC-RNG benötigte Mathematik bei binären MWC-RNG deutlich einfacher zu sein.

--Aragorn321 (Diskussion) 19:05, 2. Dez. 2012 (CET)

Zu 0) Ja, das stimmt.

Zu 1) Welches 31 Bit breite Carry meinst du? Ich sehe es gerade nicht.

Zu 2) Keine Ahnung, was du mit "neu erstellt" meinst. Stimmt, die korrekten Anfangswerte sind x_1 = 5, c_1 = 3.

Zu 3) Dann zeigt dir der Windows-Taschenrechner offensichtlich nicht das komplette Ergebnis.

Zu 4) In Mathe fängt man überlichweise mit Eins an und die benannte Nummerierung ist kein Quellcode. Außerdem: Spielt das wirklich eine Rolle?

Zu 5) Was soll an dem Beispiel im englischen Wiki besser sein? (Und: meinst du das lange oder das kurze?)

Zu 6) Weil $x\mod 2^{32}-1\rightarrow x\in [0\dots 2^{32}-2]$

Zu 7) Das ist für den Fall eines Overflows bei der Addition der unteren und oberen 32 Bit von t.

Zu 8) Ja, diese Erwähnung fehlt.

Zu 9) Für die Theorie ja. Ich denke, die meisten verwenden für b = 2³²-1 wie im Beispiel.

Alles in allem, bleibt nur zu unterstreichen, dass dieser Artikel noch ausbaufähig ist. -- Plankton314 (Diskussion) 21:04, 2. Dez. 2012 (CET)

Vielen Dank für die schnelle Reaktion, damit hatte ich nicht gerechnet.

Re 1) Man suche auf der deutschen Webseite nach "oberen" dann findet man die Textstelle mit "den Übertrag c (die oberen 31 Bits)".

Re 2) Das Beispiel auf der englischen Webseite dividiert durch 69, was ja nun wirklich keine Primzahl ist (3*23=69). Da auf der deutschen Webseite die Tatsache, dass man den MWC-RNG auch mit solchen Parametern konstruieren kann, weggelassen wurde und nur die Konstruktion des MWC-RNG mit Primzahlen der Form p = a*b-1 vorgestellt wurde, nahm ich an, dass das Beispiel, welches durch die 59, also durch eine Primzahl teilt, extra passend dazu neu erstellt wurde. Sorry, wenn das eine Falschannahme meinerseits war.

Re 3) Da im Beispiel auf der deutschen Webseite m = a*b-1 = 5*10-1 = 59 tatsächlich eine Primzahl ist, ist die Periodenlänge L des MWC-RNG L = m-1 = 58. Klar das der Taschenrechner von Windows das nicht alles anzeigt. Es wäre daher hilfreich, diese 58 Zahlen lange Sequenz (und ein paar Zahlen mehr) im Beispiel auf der Webseite zu sehen, damit man die Aussage "Der MWC gibt in umgekehrter Reihenfolge die Dezimalbruchentwicklung von 33 \over 59 aus." auch leicht überprüfen kann. Die Periodenlänge L ist aber nur dann gleich p-1, wenn auch (ord(b) in MG(p) = p-1) ist, also #sequence(10^i mod 59) = 58, was tatsächlich hier auch der Fall ist. sequence(10^i mod 59)=(01,10,41,56,29,54,09,31,15,32,25,14,22,43,17,52,48,08,21,33,35,55,19,13,12,02,20,23,53,58,49,18,03,30,05,50,28,44,27,34,45,37,16,42,07,11,51,38,26,24,04,40,46,47,57,39,36,06)

Das folgende Gegenbeispiel zeigt, dass die Aussage "Die Konstanten a und b sollten so gewählt werden, dass m = ab-1 eine Primzahl ist. Dann gibt der Generator für jede nicht-trivialen Startwerte x_1 und c_1 eine Sequenz mit der Periodenlänge l = m-1 aus." so allgemein nicht stimmen kann. Sei für einen MWC-RNG a = 3 und b = 4, so ist p = a*b-1 = 3*4-1 = 11 nicht nur eine Primzahl, sondern sogar noch eine sogenannte "SavePrime", also p = 2*q+1 mit q ist wiederum eine Primzahl, in unserem Fall ist q = 5. Hier ist ord(b) in MG(p) = #sequence(4^i mod 11) = #sequence(01,04,05,09,03) = 5 und somit deutlich kleiner als (p-1). Ein Testlauf dieses MWC-RNG mit den Initialwerten c0 = 0 und x0 = 1 zeigt, das tatsächlich bereits nach 5 Schritten der Ausgangszustand wieder erreicht ist.

 i a*x+c  c x  mit a = 3 und b = 4 = 2^2
 0   -    0 1
 1   3    0 3 
 2   9    2 1 
 3   5    1 1
 4   4    1 0
 5   1    0 1 

Re 6) Ja klar, wenn b = 2³²-1, dann ist b-1 = 0xfffffffe, das sagte ich ja schon. Aber ich habe immer nur gefunden, das b = 2³² ist und beim CMWC-RNG von (b-1) subtrahiert werden muss. Also wo bitte schön kommt die zweite -1 her, die muss ich irgendwo verpasst haben.

Re 9) Woher kommt denn b = 2³²-1 ? Im Beispiel ist doch b = 2³², oder? Das ist doch genau das Problem, was ich unter 6) meinte.

Eine Frage zur Periodenlänge eines RNG allgemein:

Wenn ein RNG korrekt initialisiert wurde, und damit eine Periodenlänge L mit (L > 1) garantiert wird, erwartet man doch in der Ausgabesequenz des RNG keine Wiederholung nur ein und derselben Zahl, wie in output_sequence = (6,6,6,6,6,6,6, ...), oder?

Eine Frage zur Periodenlänge des MWC-RNG:

Wenn ich für den MWC-RNG nun die Werte a=7 und b=10 setze, müßte er eine Periode von 22 haben, wie auf der englischen Webseite erklärt wird. Denn (ord(b) in MG(a*b-1)) = (ord(10) in MG(69)) = #(01,10,31,34,64,19,52,37,25,43,16,22,13,61,58,28,04,40,55,67,49,07) = 22. Ich nehme also an, dass sich die vom MWC-RNG generierten Zahlen stets erst ab der Stelle 22 wiederholen sollten, wenn man den RNG korrekt initialisiert. Für die Startwerte c0 = 4 und x0 = 6, was meines Erachtens erlaubte Startwerte sind, erhalte ich aber im nächsten Schritt mit a * x0 + c = 7 * 6 + 4 = 46 also wieder c1 = 4 und x1 = 6. Mit anderen Worten, c und x sind in jeden Schritt dieselben, bleiben also unverändert, weshalb die Ausgabesequenz dieses RNG dann logischerweise output_sequence = (6,6,6,6,6,6,6, ...) wäre und somit nur eine Periodenlänge von (L = 1) aufweisen würde. Da nach meiner Arithmetik aber (1 # 22) gilt, habe ich also ein kleines Problem. Was habe ich da nicht richtig verstanden an dem Begriff "garantierte Periodenlänge eines RNG", oder wo ist in meinem Beispiel der Fehler, den ich gemacht habe? Dieses Problem hat folgendes einfaches Muster - es ist also kein Einzelfall. Man nehme einen Bruch mit unendlicher Periode, wo stets nur die gleiche Zahl wiederholt wird z.B. (2/3 = 0,66666666 ...). Dann erweitere man diesen Bruch mit einem geeigneten Faktor, so dass sich im Nenner des Bruches der Modul des verwendeten MWC-RNG ergibt, also z.B. ((2 * 23)/(3 * 23) = 46/69). Nun liest man im Zähler des erweiterten Bruches einfach die Initialwerte c0 und x0 für den MWC-RNG der Reihe nach ab und hat somit eine garantierte Periodenlange von (L = 1), was eigentlich laut Beschreibung des MWC-RNG nicht vorkommen dürfte, oder? Ja, ich weiß, mit einer Primzahl als Modul des MWC-RNG wäre mir das nicht passiert, aber die wird nicht zwingend vorausgesetzt, sondern nur wegen der wesentlich leichteren Berechnung der Periode des MWC-RNG empfohlen.

--Aragorn321 (Diskussion) 11:44, 3. Dez. 2012 (CET)

So, sorry, für den Delay... es gab noch eine andere Baustelle.

Zu 1) Danke, da hast du recht. Das war wohl ein Typo oder die Annahme, dass t ein Vorzeichen hätte.

Zu 6 & 9) Wenn ich das richtig verstehe, dann ist das ein Trick, um nicht die Null zu erwischen. Dann liegt die Zahl nämlich auf dem Intervall [1 ... 2³²-1]. (Und da kommt anscheinend auch das "complementary" her.)

Zu den anderen Punkten kann ich nur sagen, dass das richtig klingt bzw. ich dir z. B. bei der mangelnden Ausführlichkeit des Beispiels zustimme (ja, man könnte als Verbesserung mal die komplette Periode hinschreiben).

Zu der Periodenlänge: Ja, das ist AFAIK der Grund, warum nicht der MWC sondern der CMWC besser ist. Beim MWC können solche "nicht maximal langen" Perioden auftreten. Irgendwo steht (oder sollte stehen), dass beim CMWC b eine Primitivwurzel von p sein muss. Dann sind solche Fälle auch nicht möglich. -- Plankton314 (Diskussion) 21:58, 6. Dez. 2012 (CET)

x_n/b

hier wird an zwei Stellen gesagt, dass c_n=|x_n/b| wäre was definitiv falsch ist (nicht signierter Beitrag von 128.176.200.42 (Diskussion) 08:25, 24. Mai 2013 (CEST))

Okay. --Plankton314 (Diskussion) 10:31, 24. Mai 2013 (CEST)

Dieser Abschnitt kann archiviert werden. --Plankton314 (Diskussion) 19:27, 1. Okt. 2013 (CEST)