Keskustelu: Koodit: C++: random-testi

Metabolix, osoitit taannoin, että tekemäni random-funktio rupeaa toistamaan itseään verrattain nopeasti. Mutta kun tein uuden testi-alustan, niin random-funktio ei ihan heti rupea toistamaan itseään. Huomasin tämän vähän monimutkaisemmassa random-testikoodissani.

Oliko testikoodissasi sitten bugi, vai miksi se rupesi toistamaan itseään niin nopeasti? Itse tekemässäni random-testikoodissa en enää löytänyt toistoa?

Ohessa testikoodini, joka kommentoikoon itse itsensä – en jaksa ruveta kirjoittamaan triviaaleja kommentteja, kun testikoodi on näin yksinkertainen.

Hox: jos joku kaipaa kommentteja tai testikoodissa on ylitsepääsemättömän vaikea kohta, niin kommentoin testi-koodia parhaani mukaan, kun on ensin kysymys, mitä kohtaa pitää kommentoida.

#include <stdio.h>
#include <conio.h>

class random
{
    public:

    random(void);
    ~random(void);

    unsigned rnd32(void);

    private:

    unsigned r1, r2;
};

random::random(void)
{
    r1=1;
    r2=2;
}

random::~random(void)
{
}

unsigned random::rnd32(void)
{
    r1 -= 0x012357bfL;
    r2 += 0xfedca201L;
    r1 += (r1>>16)^(r2<<16);
    r2 -= (r1<<16)^(r2>>16);
    return r1^r2;
}

int toistaa(void *a, void *b)
{
    char *A=(char*)a;
    char *B=(char*)b;
    int size=sizeof(random);
    for (int i=0; i<size; i++)
    {
        if (A[i]!=B[i]) return 0;
    }
    return 1;
}

int main(void)
{
    random a;
    random b;

    for (int i=0; i<100000000; i++)
    {
        a.rnd32();
        b.rnd32();
    }

    printf("aloitetaan...\n");

    for (unsigned x=0, y=0;;)
    {
        ++x;
        b.rnd32();

        if (toistaa(&a, &b))
        {
            printf("toistaa... %u %u\n", x, y);
            for (int u=1; u<1000; u++) getch();
        }

        if ((!x) || (x%100000000==0))
        {
            if (!x) ++y;
            printf("%u %u\n", x, y);
        }
    }
}

Asia selviää helposti siitä viestistä, jossa esittelin tuloksen: "44202814360 kierroksen jälkeen jakso, joka käsittää 183902521870 lukua". Virhe omassa testissäsi on siis se, että ajat ensimmäistä randomia vain 100000000 kierrosta eli se ei tule silmukan sisään. Jos ajat molempia ensin 44202814361 kierrosta, pääset silmukan sisään.

Usein silmukoiden etsintään käytetään algoritmia, joka siirtää A:ta yhden ja B:tä kaksi askelta. Jos silmukka on olemassa, nämä lopulta kohtaavat toisensa. Tämä tapa toimii riippumatta siitä, miten pitkä alkuosa on ennen silmukkaa.

Hmmm... jokaisella random-funktiolla on tietyn pituinen sykli - alku ja loppu ja ympäri pyörähtäminen. Tässä tapauksessa se on ainakin suurempi kuin 1000*2^32.

Keskustelu koskee tätä random-funktiota jossa sykli on pidempi kuin 1000*2^32:

unsigned rnd32(void)
{
	static unsigned r1=1;
    static unsigned r2=2;
    r1 -= 0x012357bfL;
    r2 += 0xfedca201L;
    r1 += (r1>>16)^(r2<<16);
    r2 -= (r1<<16)^(r2>>16);
    return r1^r2;
}

jone2712 kirjoitti:

Keskustelu koskee tätä random-funktiota jossa sykli on pidempi kuin 1000*2^32

Syklin pituus 183902521870 on vähemmän kuin 43 * 2^32 ja vähemmän kuin 2 * 10^11.

Vaikka tämäkin sykli on moneen käyttöön ihan tarpeeksi, tärkein kritiikki koskee sitä alkuperäistä väitettä, että "teho-random poukkoilee kaoottisesti likimain 10 potenssiin 19 eri attraktorilla”.

Tämmöinen usean kertaluokan virhe yksinkertaisessa asiassa ei anna kovin vakuuttavaa kuvaa siitä, että aiheen teoriaa olisi oikeasti tutkittu kymmeniä vuosia ja funktio olisi muillakaan tavoilla luotettava.