Generator Fibonacciego z przeniesieniem

Generator Fibonacciego z przeniesieniem – rozwinięcie opóźnionego (lagged) generatora Fibonacciego. Generatory te charakteryzują się bardzo długimi cyklami: podczas gdy zwykłe opóźnione generatory Fibonacciego (LFG) mają dla 32-bitowego czynnika modulo cykle długości rzędu $2^{32+r},$ generatory z przeniesieniem osiągają cykle długości $2^{32r}.$

Rozważmy standardowy ciąg Fibonacciego zapoczątkowany liczb ami 0 i 1:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...

Weźmy teraz ciąg reszt modulo baza $b=10$ (operacja $u\diamondsuit w$ = u + w mod 10):

0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6,...

Ciąg taki wpada w cykl długości 60, składający się z czterech cykli długości 15, gdzie w kolejnym cyklu liczby mnożone są przez 7 modulo 10:

 0 1 1 2 3 5 8 3 1 4 5 9 4 3 7
 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9
 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3
 0 3 3 6 9 5 4 9 3 2 5 7 2 9 1

Z bitem przeniesienia dla dodawania sytuacja będzie wyglądała tak, że początkowo bit c ustawiamy na zero, następnie jeśli $x_{n-r}+x_{n-s}+c>=b,$ wtedy odejmujemy $b$ i ustawiamy $c$ na 1; w przeciwnym przypadku zerujemy $c.$

Dla poprzedniego przykładu gdzie $b=10,$ $r=2,$ $s=1,$ bit przeniesienia spowoduje cykl długości 108:

$b^{r}+b^{s}-2=10^{2}+10^{1}-2=108.$

Generator nosi nazwę generatora add-with-carry.

Podobnie możemy zdefiniować generator subtract-with-borrow: jeśli $x_{n-r}-x_{n-s}-c<0,$ wtedy dodajemy $b$ i ustawiamy $c$ na 1; w przeciwnym przypadku zerujemy $c.$ Dla $b=10,$ $r=2,$ $s=1,$ cykl będzie miał długość 44.

Projekt generatora

Zajmijmy się teraz zaprojektowaniem generatora. Wybieramy $b$ bliskie 2³², $r$ i $s,$ takie że $m=b^{r}-b^{s}+1$ jest liczbą pierwszą z $b$ jako pierwiastkiem pierwotnym, $r$ nie jest za małe i $s$ nie tak bliskie $r.$

Dla $b$ bliskiego 2³² i $r$ o wartości 20 i więcej, $m$ może być z zakresu 2⁶⁰⁰ do 2¹⁸⁰⁰. Testowanie na pierwszość liczby $m$ jest wykonalne, używając testów Monte Carlo, ale ustalenie, czy $b$ jest pierwiastkiem pierwotnym, jest dużo trudniejsze, bo wymaga rozłożenia liczby $m-1.$ Po długich obliczeniach otrzymujemy generator substract-wih-borrow:

$x_{n}=(x_{n-22}-x_{n-43}-c){\bmod {b}},\;b=2^{32}-5=4\ 294\ 967\ 291.$

RCARRY

Dla generatora RCARRY zaproponowanego przez F. Jamesa $b=2^{24},$ $r=24,$ $s=10,$ co daje cykl jedynie 48 razy mniejszy niż możliwy do reprezentacji przez 24 liczby 24-bitowe, czyli (2²⁴)²⁴. Czyli okres wynosi w przybliżeniu 2⁵⁷⁰, czyli 10¹⁷¹.

static const unsigned long int two24 = 16777216;        /* 2^24 */
void RCARRY(int rvec[], int lenv, int seeds[])
{
        for (int i = 0; i < lenv; i++)
        {
                int unew = seeds[jptr] - seeds[iptr] - carry;
                if (unew < 0)
                {
                        unew += two24;
                        carry = 1;
                }
                else
                        carry = 0;
                seeds[iptr] = unew;
                iptr--;
                if (iptr < 0) iptr = 23;
                jptr--;
                if (jptr < 0) jptr = 23;
                rvec[i] = unew;
        }
}

gdzie inicjalizacja wygląda :

void seet_seeds(long int seed, int u[])
{
        int i;

        /* This is the initialization algorithm of F. James, widely in use
        for RANLUX. */

        for (i = 0; i < 24; i++)
        {
                unsigned long int k = seed / 53668;
                seed = 40014 * (seed - k * 53668) - k * 12211;
                if (seed < 0)
                {
                        seed += 2147483563;
                }
                u[i] = seed % two24;
        }
        iptr = 23;
        jptr = 9;
        carry = 0;
}

wołanie :

void rcarry_test()
{
        const int SIZE = 5;
        int rvec[SIZE];
        int seeds[24];
        seet_seeds(314159265, seeds);//dla 314159265 daje 9056646 12776696 1011656 13354708 5139066
        RCARRY(rvec, SIZE, seeds);
        for (int i = 0; i < SIZE; i++)
                printf("%d ", rvec[i]);
}

Własności

Algorytm jest szybki (pomiary w Visual C++ na Intel i3 3.6 GHz: 15.7 takta), jednak nie przechodzi testu urodzinowego (diehard_birthdays w pakiecie DieHarder). Stał się on podstawą algorytmu RANLUX.