hur funkar en slumpgenerator?

tekniskt! hur gör den? är det riktigt slump? är alltid tiden med?

http://www.agner.org/random/

Savitt jag forstar sa funkar de flesta inbyggda slumpgeneratorer i C genom att man forst "seedar" generatorn med ett visst nummer (forslagsvis tiden), och sen sa fifflar generatorn till en viss sekvens av pseudo-slumpmassiga nummer med hjalp av seedet (jag formodar att statiska variabler ar inblandade). Alltsa, addera 2 till seedet, dela med 6, osv osv ;)

Sekvensen blir ju annorlunda med olika seeds, och har man en hogupplost tidfunktion ar ju det ganska otroligt att man skulle seeda generatorn med exakt samma tid tva (eller fler) ganger, och darfor ar sannolikheten att man far tva likadana sekvenser valdigt liten (Ratta mig om jag har fel, ar inte sa varst insatt).

Hursomhelst ar det iaf inte "riktig" slump.

Vissa slumpgeneratorer funkar dock genom att de har en yttre kalla av "slumpmassighet". Silicon Graphics har nan spexgrej som anvander lavalampor, gamla Sun-maskiner anvande bruset fran hogtalarinputen... Har aven hort nat om att man kan anvanda varmesensorer placerade i datorn... Aja, dessa nummer borde bli "battre" an de som produceras av en san generator som jag beskrev lite langre upp i inlagget, men kraver i sin tur mer hardvara.

I Linux använder kärnan entropi för att erbjuda äkta slump (i viss mån beroende på hur man definierar "äkta" och "slump"). Kort beskrivning finns på http://egd.sourceforge.net/

Jag skrev ett snabbt program. Verkar slumpa ganska jämnt men det blir alltid dubbelt så många 0or som andra siffror....

#include <iostream>
#include <windows.h>
using namespace std;

unsigned int g_Seed;
int numcontrol[25];

int Random()
{
	g_Seed += 12355645647539868;
	g_Seed *= 25.1257235;
	return g_Seed;
}

int main(int argc, char **argv)
{

	g_Seed = GetTickCount();

	for(int i=0;i<100000;i++)
	{
		numcontrol[Random()%20]++;
	}

	for(i=0;i<20;i++)
	{
		cout << "#" << i << ": " << numcontrol[i] << endl;
	}

}

Mitt krypteringsprogram använder sig av brus från datormikrofonen för att generera mycket stora (flera megabit) kryptonycklar.
Länk

Många gånger är det en jättetabell med tal, uträknade en gång från någon viss formel och "seedet" avgör var man startar i tabellen. I vissa fall räknas talen fram när de behövs.

Vanligtvis är formlerna för beräkning mycket komplexa och bygger till viss del på att man tar fram modulo på något stort primtal efter en avancerad beräkning av något slag.

Att plocka fram slumptal är inte ett enkelt problem att lösa eftersom många gånger är det viktigt att de tal man får fram verkligen är likformigt fördelade. Så om du vill skriva en sådan funktion, rådfråga någon litteratur i ämnet. Två saker är framförallt viktiga:
* Att det verkligen blir (tillräckligt bra) likformig fördelning.
* Att man vet hur lång tid det tar för funktionen att komma "runt", dvs när funktionens nästa värde är samma som det första.

Om man behöver någon annan fördelning, tex Normalfördelade slumptal, så startar man med att ta fram likformigt fördelade och sedan gör man en matematisk transformation på dessa. På så sätt kan man få fram godtycklig fördelning på slumptalen.

AlphaII - Jag har bara slängt ett getöga på din funktion, men en sak är i alla fall ingen höjdare. Du delar med 20. Överhuvudtaget bör man inte dela med jämna tal, har för mig att man brukar använda primtal.

aasah skrev:

Vanligtvis är formlerna för beräkning mycket komplexa och bygger till viss del på att man tar fram modulo på något stort primtal efter en avancerad beräkning av något slag.

Nej, vanligtvis är formlerna inte alls avancerade, de ser ut precis som AlphaIIs funktion. Det luriga är att välja bra konstanter. AlphaII har valt en konstant som inte fungerar speciellt bra på de flesta kompilatorer där int är 32 bitar eller mindre.
Det låter som om du tänker på krypteringsalgoritmer.

aasah skrev:

AlphaII - Jag har bara slängt ett getöga på din funktion, men en sak är i alla fall ingen höjdare. Du delar med 20. Överhuvudtaget bör man inte dela med jämna tal, har för mig att man brukar använda primtal.

Den divisionen har inget att göra med algoritmen för att ta fram slumptal, utan för att specificera ett intervall.
Om man vill ha slumptal i intervallet 0-19 så måste man ta modulo på 20. Skulle man välja ett primtal så skulle man få tal i ett annat intervall.

Så här ser generatorn ut i Visual C++ .NET 2003:

int rand()
{
    return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
}

Ingen avancerad formel, men konstanterna är inte godtyckligt valda.