English

Slumptal

I en dator finns det ingenting som är slumpmässigt. Allt följer samma mönster varje gång och regler givna av programmen som datorn kör bestämmer entydigt vad som ska hända. Att skapa något helt slumpartat är därför inte så lätt i en dator. Äkta slumptal finns normalt inte att tillgå utan man brukar tala om pseudoslumptal (nästan slumptal eller låtsasslumptal).

Pseudoslumptal beräknas med en matematisk formel utifrån ett frö. För att skapa en följd av olika slumptal brukar dessa formler använda det senast genererade slumptalet som frö för nästa beräkning. Formeln är naturligtvis deterministisk och givet samma frö får man därför alltid samma slumptal. Den vanligaste metoden att skapa slumptal kallas linear congruent eller power residue. Multiplicera det föregående slumptalet med en konstant, a, addera sedan en annan konstant, c. Ta resultatet modulo M och behåll resten som ditt nästa slumptal. M är den övre gränsen för slumptalen. Metoden finns beskriven i Donald Knuths 'The Art of Computer Programming', Volym 2, Sektion 3.2.1.

    ri = (ri-1 * a + c) % M
  

Koden nedan är hämtad från C:s standardbibliotek och visar implementationen av en slumptalsfunktion i C. Funktionen har ett frö, next, som initieras till ett. Varje gång man anropar rand() får man ett nytt slumptal. Slumptalet sparas i next till nästa gång man vill ha ett slumptal och används då som frö. För att initiera slumpfröet till ett eget värde anropar man srand med ett frö.

    unsigned long int next = 1;

    int rand(void)
    {
        next = next * 1103515245 + 12345;
        return (unsigned int)(next/65536) % 32768;
    }

    void srand(unsigned int seed)
    {
        next = seed;
    }
  

Ett slumpmässigt frö

I vissa sammanhang är det önskvärt med slumptal som följer samma mönster gång på gång. Till exempel om man vill simulera eller testköra ett system med slumpmässiga parametrar flera gånger och vara säker på att de slumpmässiga parametrarna är de samma varje gång. I andra fall är det inte lika roligt med deterministiska slumpföljder. I spel och liknande applikationer brukar man inte vilja att samma slumpföljd upprepas varje gång man spelar. Då räcker det inte med en formel som givet ett frö räknar ut nästa slumptal, man måste även se till att ha ett tillräckligt slumpmässigt frö.

Det enklaste att ta till i en dator där sannolikheten är mycket liten att man får samma svar från gång till gång, är systemklockan. Det är därför mycket vanligt att datorns klocka används som frö vid slumptalsgenerering. Detta är fallet i till exempel Java. När ett nytt Random-objekt skapas hämtar systemet ett frö från klockan som används till framtida slumptal i objektet. I C finns ingen färdig konstruktion för att skapa en ny slumpföljd med ickedeterministiskt frö, men det är mycket enkelt att göra detta själv med hjälp av systemklockan: srand(time(NULL)); Exempel på hur detta kan användas finns på Kodsidan.

Äkta slumptal

Det finns många olika sätt att beräkna pseudoslumptal. Den vanligaste metoden, som finns inbyggd i många programmeringsspråk (till exempel de vanligaste implementationerna av C och Java), är beskriven här. Söker ni efter saker som 'pseudo random number generator' med någon lämplig sökmotor hittar ni fler. Är man i desperat behov av äkta slumptal måste man gå utanför datorn för att hämta inspiration. Exempel på detta finns hos random.org som använder sig av atmosfäriska störningar från radio för att skapa slumptal, eller HotBits som har en radioaktiv kärna för att skapa slumptal. En annan intressant metod används av LavaRand. Där är det lavalampor som står för slumpen. (Väl värt en titt!)

Som ni märker så är det inte alltid helt lätt att skapa sig en äkta slump i en deterministisk värld.