Véletlen volt

véletlenszámok készítése gyorsan és alacsony hőfokon

Az alábbiakban néhány ismert és könnyen implementálható módszert mutatok (pszeudo)véletlen egészek előállítására. A témának egyébként kiterjedt szakirodalma van (pl. egy teljes fejezet a Knuth 2. kötetében), melyhez képest ez a reprodukció még porszemnyit sem ér. De hátha mégis...

Ha nincs különleges igény, használd a Pascal-ét. Ezzel csak egy baj van: Nem tud véletlen word-öt generálni [0..65535], mivel 65534-nél nagyobb számokat sohasem ad vissza. Így például nem lehet bele egy fájlon belül véletlen helyre ugrani. Mivel nekem éppen erre volt szükségem, belevetettem magam a szakirodalomba.

A módszer (Knuth 3.2.2.A)

Dobj ki kockával 55 db értéket (x[0..54]), majd használd a következő képletet: x[n]:=x[n-24]+x[n-55]. Az a nagy előny, hogy az összeadást mod 2^i végezzük, azaz az esetleges átvitelt el lehet felejteni.

Ugyanez algoritmikusan:

Randomize():

  t[1..55] feltöltése pl. int 1Ah (pontos idő)-vel
  j:=24;
  k:=55;

X:=random():
  t[k]+=t[j];
  X:=t[k];
  j--;
  if j=0 then j:=55;
  k--;
  if k=0 then k:=55;

Előnyei:

1. gyors (1 összeadás, 2 csökkentés, 2 feltétel), semmi szorzás, semmi osztás;
2. könnyű lekódolni bármilyen nyelven
3. dinamikus: t lehet akár byte, word, dword vagy akármilyen típusú elemekből álló tömb, minden esetben működik.

Hátrányai:

1. 55 db memóriarekeszt foglal (de a kódja sokkal rövidebb, és ez behozza a hátrányt)
2. Helyessége formálisan nem bizonyított (de eddig minden szakszerű gyakorlati próbát kiállt).

Hiheted, ha látod.

Tetszőleges intervallum

Ha olyan X véletlenszámot akarunk, amire alt=XGeneráljunk egy nagyon sok, mondjuk 32 bites számot A-ban. Szorozzuk ezt meg c-vel (c jelentését ld az előző bekezdésben), majd az eredményt toljuk jobbra 32-vel (egész osztás 2^32-nel). Assemblyben:

k dw 55*4
j dw 24*4
t dd 55 dup (?)

pushf
push eax	;EDX:=random(c)
xchg bx, k
xchg si, j
mov eax, t[bx-4]
add eax, t[si-4]
mov t[bx-4], eax
sub bx, 4
if z mov bx, 55*4
sub si, 4
if z mov si, 55*4
xchg bx, k
xchg si, j
mul dword ptr c
pop eax
popf
ret

Kártyakeverés

Feladat: Véletlen sorrendbe kell rakni néhány tárgyat. A tárgyakat 0-tól (n-1)-ig számozzuk, és t[i]-vel hivatkozunk rájuk. Megoldás (n tárgyra): c:=random(n); csere(t[n-1],t[c]); Ezek után végezzük el ugyanezt rekurzívan (n-1) db tárgyra.

Pascalban:

var i,c: integer; temp: XXX; t: array[0..n-1] of XXX

for i:=n downto 2 do begin
  c:=random(i);
  temp:=t[i-1];
  t[i-1]:=t[c];
  t[c]:=temp;
end;

Remélem, tudtam valami újat mondani/írni.

Ez a lap pts oldalai közül való.