imported>Bithisarea: /* growthexperiments-addlink-summary-summary:2|1|0 */

2025-01-12T20:20:20Z

growthexperiments-addlink-summary-summary:2|1|0

Neue Seite

{{Überarbeiten}}

Der '''Multiply-with-Carry''' (kurz: '''MWC''') und dessen modifizierte Variante '''Complimentary-Multiply-with-Carry''' (kurz: '''CMWC''') sind [[Pseudozufallszahlengenerator]]en, die 2003 von [[George Marsaglia]] vorgestellt wurden.

== Eigenschaften ==

# Extrem lange Periode (2<sup>131086</sup> für den CMWC mit 16 kB Zustandsregister).
# Liefert gleich verteilte Bit-Sequenz.

=== Algorithmus ===

Der [[Algorithmus]] für den MWC kann durch zwei Rekurrenzgleichungen beschrieben werden:

:<math>x_n = ( a x_{n-1} + c_{n-1} ) \mod b</math>

:<math>c_n = \lfloor ( a x_{n-1} + c_{n-1} ) / b \rfloor </math>

Das Ergebnis der Multiplikation ist aufgeteilt in <code>x</code> (die unteren 32 Bits) und den Übertrag <code>c</code> (die oberen 31 Bits).

Hier steht <math>x_i</math> für die ''i''-te generierte Zahl, ''a'' für einen konstanten Faktor und ''b'' für die Zahlenbasis.

Die Konstanten ''a'' und ''b'' sollten so gewählt werden, dass <math>m = ab-1</math> eine [[Primzahl]] ist. Dann gibt der Generator für alle nicht-trivialen Startwerte <math>x_1</math> und <math>c_1</math> eine Sequenz mit der Periodenlänge <math>l = m-1</math> aus.

=== Beispiel ===

Sei <math>a = 6</math>, <math>b = 10</math> und als Startwerte <math>c_1 = 3</math>, <math>x_1 = 5</math>:

Sequenzlänge: <math>l = m-1 = ab-2 = 6 \cdot 10 - 2 = 58</math>

:<math>x_n = ( 6 x_{n-1} + c_{n-1} ) \mod 10</math>

:<math>c_n = \lfloor ( 6 x_{n-1} + c_{n-1} ) / 10 \rfloor</math>

{| class="wikitable" style="text-align:center"
|-
| n || <math>( 6 x_{n-1} + c_{n-1} )</math> || <math>c_n</math> || <math>x_n</math>
|-
| 1 || – || 3 || 5
|-
| 2 || 33 || 3 || '''3'''
|-
| 3 || 21 || 2 || '''1'''
|-
| 4 || 8 || 0 || '''8'''
|-
| 5 || 48 || 4 || '''8'''
|-
| 6 || 52 || 5 || '''2'''
|-
|}

Der MWC gibt in umgekehrter Reihenfolge die Dezimalbruchentwicklung von <math>33 \over 59</math> aus.

== Complimentary Multiply-with-carry ==

Für die Erzielung einer maximalen Periodenlänge wird beispielsweise bei Verwendung von 32-Bit-Integern für <math>b = 2^{32}</math> gewählt. Dies ermöglicht die optimale Nutzung des Wertebereichs und eine gleichzeitig schnelle Berechnung.
Bei MWC-Generatoren verkürzt sich hier aber die Periode um die Hälfte und es wird schwieriger, passende Primzahlen zu finden.

Diese Probleme können durch eine kleine Modifikation des ursprünglichen Algorithmus behoben werden, indem man als Rekurrenzgleichung

:<math>x_n = (b-1) - [( a x_{n-1} + c_{n-1})\mod b ]</math>

verwendet.

== Initialisierung ==

Die Initialisierung des Zustandsregisters sollte mit möglichst zufälligen und gleich verteilten Bits erfolgen, sprich etwa so viele 1- wie 0-Bits. Anderenfalls braucht der Generator eine „Warmlauf-Phase“, d. h. es muss eine gewisse Menge an Zufallszahlen generiert werden bis der Generator gleich verteilte Zufallszahlen liefert.

== Implementierung ==

=== MWC ===
<syntaxhighlight lang="C">
#include <stdint.h>

static uint32_t Q[1038];
static uint32_t c = 123;

uint32_t MWC1038() {
static uint32_t i = 1037;
uint64_t t;

t = (611376378ULL * Q[i]) + c;
c = t >> 32;

if (--i != 0)
return (Q[i] = t);

i = 1037;
return (Q[0] = t);
}
</syntaxhighlight>

=== CMWC ===
<syntaxhighlight lang="C">
#include <stdint.h>

static uint32_t Q[4096];
static uint32_t c = 123; /* 0 <= c < 18782 */

uint32_t CMWC() {
static uint32_t i = 4095;
uint64_t t;
uint32_t x;

i = (i + 1) & 4095;
t = (18782ULL * Q[i]) + c;
c = t >> 32;
x = t + c;

if (x < c) { ++x; ++c; }

Q[i] = 0xfffffffe - x;

return Q[i];
}
</syntaxhighlight>

== Siehe auch ==

* [[Liste von Zufallszahlengeneratoren]]

== Literatur ==
* {{Literatur |Autor=George Marsaglia |Titel=Random number generators |Sammelwerk=Journal of Modern Applied Statistical Methods |Band=2 |Nummer=1 |Datum=2003-05 |Sprache=en |DOI=10.22237/jmasm/1051747320 |Seiten=2–13 |Online=https://web.archive.org/web/20131004223940/http://www.jmasm.com/journal/2003_vol2_no1.pdf |Format=PDF |Abruf=2022-10-29}}
* {{Literatur |Autor=George Marsaglia |Titel=On the Randomness of Pi and Other Decimal Expansions |Datum=2005-10 |Online=http://www.yaroslavvb.com/papers/marsaglia-on.pdf |Format=PDF |Abruf=2022-11-25}}

== Weblinks ==

* Bibliothek mit statistischen Tests: [http://www.iro.umontreal.ca/~simardr/testu01/tu01.html TestU01]
* F. Panneton, P. L’Ecuyer: [http://www.iro.umontreal.ca/~lecuyer/myftp/papers/lfsr04.pdf ''Improved Long-Period Generators Base on Linear Recurrences Modulo 2''.] (PDF; 301 kB).
* [http://groups.google.com/group/comp.lang.c/msg/e3c4ea1169e463ae groups.google.com]
* [http://groups.google.com/group/sci.crypt/browse_thread/thread/305c507efbe85be4?pli=1 groups.google.com]

[[Kategorie:Pseudozufallszahlengenerator]]

Multiply-with-carry - Versionsgeschichte

imported>Bithisarea: /* growthexperiments-addlink-summary-summary:2|1|0 */