Congruentiegenerator

Een congruentiegenerator is een algoritme dat pseudotoevalsgetallen genereert, dat wil zeggen getallenrijen die deterministisch worden gegenereerd en dus niet echt willekeurig zijn, maar veel kenmerken van toevalsgetallen hebben. Congruentiegeneratoren zijn de bekendste en meestgebruikte pseudotoevalsgeneratoren.

Een congruentiegenerator wordt bepaald door de volgende parameters:

• het aantal toestandswaarden $n$
• de modulus $m\in \{2,3,4,\ldots \}$
• de multipliers $a_{1},\ldots ,a_{n}\in \left\{0,\ldots ,m-1\right\}$
• de toename $b\in \left\{0,\ldots ,m-1\right\}$

en het algoritme waarmee een nieuw gegenereerd getal gegenereerd wordt voor $i>n$ door de recurrente betrekking:

$y_{i}=\sum _{k=1}^{n}a_{k}y_{i-k}+b{\pmod {m}}$.

Daarin zijn $y_{1},\ldots ,y_{n}\in \left\{0,\ldots ,m-1\right\}$ de startwaarden.

Reële toevalsgetallen in het interval [0, 1] kunnen verkregen worden als $u_{i}=y_{i}/m$, mits $m$ groot genoeg is om een voldoende nauwkeurige onderverdeling te geven.

De toestand van de generator voor de productie van $y_{i}$ wordt gegeven door de startwaarden. Deze toestand legt (voor gegeven $n$, $m$, $k$, $b$) alle volgende toevalsgetallen vast, omdat het volgende toevalsgetal en de volgende toestand door de huidige toestand bepaald worden. Er zijn $m^{n}$ mogelijke toestanden, en daarom moet er na maximaal $m^{n}$ stappen een eerdere toestand herhaald worden. De congruentiegenerator produceert dus een periodieke rij getallen, waarbij de lengte van de periode veel kleiner dan $m^{n}$ kan zijn. In extreme gevallen is de lengte 1, en zal de generator altijd hetzelfde "toevalsgetal" geven. Bij het kiezen van de parameters is het dus onder andere van belang om te zorgen voor een periode die lang genoeg is.

Lineaire congruentie

Als $n=1$, spreekt men van een lineaire-congruentiegenerator. Het algoritme is:

$y_{i}=a\,y_{i-1}+b{\pmod {m}}$.

Is ook nog $b=0$, dus

$y_{i}=a\,y_{i-1}{\pmod {m}}$,

dan is er sprake van een multiplicatieve-congruentiegenerator. De multiplicatieve congruentie heet ook Lehmer-congruentie, naar D. H. Lehmer die dit algoritme in 1949 introduceerde.

Fibonacci-generator

Een Fibonacci-generator is een congruentiegenerator met $n=2$, $b=0$ en $a_{1}=a_{2}=1$, en bestaat uit de volgende componenten:

• Modulus $m\in \{2,3,4,\ldots \}$
• Startwaarden $y_{1},y_{2}\in \left\{0,\ldots ,m-1\right\}$

Met de volgende functie worden de pseudowillekeurige getallen gegenereerd:

$y_{i}\equiv y_{i-1}+y_{i-2}{\pmod {m}}\quad ({\mbox{met }}i\geq 3)$.

Een kenmerk is dat de gevallen $y_{i-1}<y_{i+1}<y_{i}$ respectievelijk $y_{i}<y_{i+1}<y_{i-1}$ nooit voorkomen. Fibonacci-generatoren zijn dus niet geschikt als pseudotoevalsgenerator. Dit geldt met name voor wiskundige objecten waarvoor de productie van meer dan twee toevalsgetallen nodig is. Als men bijvoorbeeld probeert om een willekeurige wolk van punten in een kubus te genereren, dan zouden alle punten op twee vlakken liggen.

Vertraagde Fibonacci-generator

Het principe van de Fibonacci-generator kan worden gegeneraliseerd door niet de laatste twee, maar verder terug liggende waarden $y_{i}$ te gebruiken om een nieuw toevalsgetal te genereren. Dit resulteert in een vertraagde (Eng. 'lagged') Fibonacci-generator:

$y_{i}\equiv y_{i-B}+y_{i-A}{\pmod {m}}\quad {\mbox{met}}\;A,B\in \mathbb {N} ^{+},\ A>B;\quad i>A$

met de startwaarden $y_{1},\ldots ,y_{A}\in \left\{0,\ldots ,m-1\right\}$.

Dan is $n=A$ en $a_{A}=a_{B}=1$ en de andere $a_{k}$ zijn nul. Hierbij wordt $m$ in het algemeen even gekozen en $A$ en $B$ worden gekozen, zodat de polynoom in $x$: $x^{A}+x^{B}+1$ een primitieve polynoom modulo 2 is. De periode van de generator is dan minimaal $2^{A}-1$.

$x^{A}+x^{B}+1$ is een primitieve polynoom modulo 2 dan en slechts dan als $x^{A}+x^{A-B}+1$ dat ook is. Zo kan men in plaats van $B$ ook altijd $A-B$ berekenen.

De volgende tabel geeft enkele waarden voor $A$ en $B$ die aan deze voorwaarde voldoen:

A	2	31	55	73	98	100	135	258	607	3217	23209
B	1	13	24	25	27	37	22	83	273	576	9739

Deze generator wordt ook gebruikt in de praktijk. Het geeft echter niet altijd volledig willekeurige getallen. Het probleem van de gewone Fibonacci-generator is slechts verschoven; nu komen $y_{i-A}<y_{i}<y_{i-B}$ of $y_{i-B}<y_{i}<y_{i-A}$ nooit voor. Er zijn zelfs nog meer tekortkomingen.

Als oplossing werd voorgesteld om altijd alleen gebruikmaken van $A$ opeenvolgende nummers, en dan de volgende $4A$ tot $10A$ getallen te verwerpen. Dit werkt goed, maar zorgt voor een 5 tot 11 keer hogere computatietijd. De door Donald Knuth voorgestelde generator ranarray werkt op deze manier. Hierbij is $A=100$ en $B=37$, en van 1009 opeenvolgende getallen wordt slechts een blok van 100 getallen gebruikt.

Om voor een periode van $2^{A}-1$ te zorgen, is alleen de minst significante bit in de toestandswaarde $y_{i}$ van belang, dat wil zeggen, dat het van belang is of de bit even of oneven is. Het is mogelijk om de hogere orde bits naar behoefte te veranderen, om de kwaliteit van de resulterende toevalsgetallen te verbeteren. Bijvoorbeeld:

$y_{i}\equiv y_{i-A}+y_{i-B}+f(y_{i-C}){\pmod {m}};\quad f:\{0,\ldots ,m-1\}\rightarrow \{0,2,4,6,\ldots \},\;C\in \{1,\ldots ,n\}$

Verdere veralgemening

Men kan de vertraagde Fibonacci-generator verder veralgemenen door meer dan twee toestandswaarden te verwerken:

$y_{i}\equiv \sum _{k\in M}y_{i-k}{\pmod {m}}\quad {\mbox{met}}\quad M\subset \mathbb {N} ^{+}$.

Hier is $n$ het grootste element in $M$. Om een periode van ten minste $2^{n}-1$ te garanderen, moet ook hier de bijbehorende polynoom $\sum _{k\in M}x^{k}+1$ of equivalent, de polynoom $x^{n}+\sum _{k\in M}x^{n-k}$ een primitieve polynoom modulo 2 zijn (met een even modulus $m$). Een generator die zo opgebouwd is met $|M|>2$ levert over het algemeen beter toevalsgetallen dan met $|M|=2$, maar ook dit gaat ten koste van de rekentijd.

Met een verdere generalisering kan voor een gegeven $n$ de lengte van de periode verhoogd worden en waarschijnlijk ook de kwaliteit van willekeurige getallen verbeterd worden. $p$ is een priemfactor van $m$. Voor de rekenregel

$y_{i}\equiv \sum _{k=1}^{n}a_{k}y_{i-k}{\pmod {m}}$

zullen de $a_{k}\in \{0,\ldots ,m-1\}$, met $a_{n}\not \equiv 0{\pmod {p}}$, zodanig worden geselecteerd dat de polynoom in $x$

$x^{n}-\sum _{k=1}^{n}a_{k}x^{n-k}{\pmod {p}}$

een primitieve polynoom modulo $p$ is. Dan is de periode ten minste $p^{n}-1$.

De vorige generator vloeit hieruit voort met $p=2$ en $a_{k}\in \{0,1\}$ als een bijzonder geval, en $n=1;\ p=m$ levert een multiplicatieve congruentiegenerator met periode $p-1$.

De polynoom $f(x)=x^{n}-\sum _{k=1}^{n}a_{k}x^{n-k}$ is een primitieve polynoom modulo p als

$r={\frac {p^{n}-1}{p-1}}$ en $a=(-1)^{n-1}a_{n}$

voldoen aan:

• $a$ is een primitief element modulo $p$
• de polynoom $x^{r}$ is congruent aan $a$ (modulo $f(x)$)
• voor alle priemfactoren $q$ van $r$ is de graad van de polynoom $x^{r/q}{\pmod {\ }}f(x)$ positief.

Hiervoor wordt polynoomrekening gebruikt en er wordt modulo $p$ gerekend met de coëfficiënten (het zijn elementen van de quotiëntring $\mathbb {Z} /p\mathbb {Z}$).