Random - Il paradosso

[SilverF0x]

Allora raga, questo è un dubbio serio.

Prendiamo un qualsiasi linguaggio di programmazione e pensiamo alla funzione random.

LA funzione random (n) sceglie un numero (mettiamo intero per semplificare) da 0 a n.

Ora mettiamo che voglio costruirmi una funzione random, senza usare il comando random....

|NON POSSO|

Perche qualunque serie di operazioni faccia per generare un numero casuale, genrerà sempre quel numero, o una serie di numeri sempre uguale.

Quindi non posso creare un numero random senza la funzione random.
MA COME FA ALLORA AD ESISTERE STO BENEDETTO ALGORITMO DEL RANDOM?! é insito nel processore?HA un sistema di biglie che ne sceglie una a caso e nessuno celo ha mai detto?!

Risolvetemi sto dubbio che da solo non ci sono riuscito Grazie a tutti quelli che vorranno partecipare a questa iniziativa culturale

[Lucio Virzì]

Originariamente inviato da SilverF0x
Allora raga, questo è un dubbio serio.

Prendiamo un qualsiasi linguaggio di programmazione e pensiamo alla funzione random.

LA funzione random (n) sceglie un numero (mettiamo intero per semplificare) da 0 a n.

Ora mettiamo che voglio costruirmi una funzione random, senza usare il comando random....

|NON POSSO|

Perche qualunque serie di operazioni faccia per generare un numero casuale, genrerà sempre quel numero, o una serie di numeri sempre uguale.

Quindi non posso creare un numero random senza la funzione random.
MA COME FA ALLORA AD ESISTERE STO BENEDETTO ALGORITMO DEL RANDOM?! é insito nel processore?HA un sistema di biglie che ne sceglie una a caso e nessuno celo ha mai detto?!

Risolvetemi sto dubbio che da solo non ci sono riuscito Grazie a tutti quelli che vorranno partecipare a questa iniziativa culturale

Mi sembra di ricordare che sia un sistema basato sul conteggio di cicli di clock, più è elevata la frequenza di lavoro della cpu e più è facile che un contatore che va con il ciclo di clock e si riazzera ogni tanto presenti un valore diverso. Il tutto viene modificato dal "seed" che imposti per il numero random.
Insomma, credo che ci sia un contatore che fa, mettiamo 1-1000 andando avanti di uno ogni ciclo di clock; quando tu chiedi RAND lui ti restituisce il valore attuale.

LuVi

[jumpermax]

sposto nella sezione scienza e aggiungo un piccolo contributo
http://www.dis.uniroma1.it/~alberto/...ri_casuali.pdf

[shinji_85]

Credo di aver letto che ci sono delle fomule per generare numeri definiti pseudo-casuali...
Non ho idea di come queste formule possano apparire, ma se non si cambia il numero di partenza (ovvero il "seed" di cui parla Lucio, il seme ) verranno generate sempre le stesse sequenze...

Come sono andati gli esami???

[Scoperchiatore]

Codice PHP:

interface

uses
  Windows, Messages, SysUtils, Classes;

function MakeRND(Len: integer): string;
procedure FillRND(Buff: Pointer; Len: integer);

function GetRNDByte: Byte;
// create random integer in range 0 <= X < Range
// like standart delphi random
function GetRNDInt(Range: integer = 0): integer;
function GetRNDDWORD: DWORD;

implementation

var rotor,                            { Rotor and ratchet are used to help }
    ratchet,                          { Continually shuffle the "cards."   }
    avalanche,                        { Data dependent index. }
    last_plain,                       { Previous plain text byte. }
    last_cipher: byte;                { Previous cipher text byte. }
    cards: array[0..255] of byte;     { Array to hold a permutation of all }
    CS: TRTLCriticalSection;
    TimeThread: TThread;

procedure PoolByte(b: Byte);
var swaptemp: byte;
begin
  EnterCriticalSection(CS);
  try
    ratchet := (ratchet + cards[rotor]) and $FF;
    inc(rotor);
    swaptemp := cards[last_cipher];      { Round-robin swap. }
    cards[last_cipher] := cards[ratchet];
    cards[ratchet] := cards[last_plain];
    cards[last_plain] := cards[rotor];
    cards[rotor] := swaptemp;
    avalanche := (avalanche + cards[swaptemp]) and $FF;
    last_cipher := b xor
      cards[(cards[ratchet] + cards[rotor]) and $FF] xor
      cards[cards[(cards[last_plain] + cards[last_cipher] +
      cards[avalanche]) and $FF]];
    last_plain := b;
  finally
    LeaveCriticalSection(CS);
  end;
end;

procedure PoolHiTime;
var hLast: TLargeInteger;
begin
  QueryPerformanceCounter(hLast);
  PoolByte(hLast and $FF);
end;

procedure PoolInt(Value: integer);
var j: integer;
begin
  for j:=1 to 4 do begin
    PoolByte(Value and $FF);
    Value:=Value shr 8;
  end;
end;

type
  TTimeThread = class(TThread)
  protected
    procedure Execute; override;
  end;

procedure TTimeThread.Execute;
begin
  FreeOnTerminate:=True;
  while not Terminated do begin
    Sleep(20);
    PoolHiTime;
  end;
  DeleteCriticalSection(CS);
end;

function GetRNDByte: Byte;
begin
  EnterCriticalSection(CS);
  try
    PoolHiTime;
    Result:=last_cipher;
  finally
    LeaveCriticalSection(CS);
  end;
end;

function GetRNDDWORD: DWORD;
begin
  FillRND(@Result,SizeOf(Result));
end;

function GetRNDInt(Range: integer): integer;
begin
  FillRND(@Result,SizeOf(Result));
  Result:=Result and $7FFFFFFF; // >= 0
  if Range > 0 then
    Result:=Result mod Range;
end;

function MakeRND(Len: integer): string;
var i: integer;
begin
  EnterCriticalSection(CS);
  try
    SetLength(Result,Len);
    for i := 1 to Len do begin
      PoolHiTime;
      Result[i]:=Chr(last_cipher);
    end;
  finally
    LeaveCriticalSection(CS);
  end;
end;

procedure FillRND(Buff: Pointer; Len: integer);
var i: integer;
    p: PByte;
begin
  p:=PByte(Buff);
  EnterCriticalSection(CS);
  try
    for i := 1 to Len do begin
      PoolHiTime;
      p^:=last_cipher;
      Inc(p);
    end;
  finally
    LeaveCriticalSection(CS);
  end;
end;

procedure HashInit;
var i,j: integer;
    MemStat : TMemoryStatus;
begin
  rotor := 1;           { Make sure we start key in a known place. }
  ratchet := 3;
  avalanche := 5;
  last_plain := 7;
  last_cipher := 11;
  j := 255;
  for i := 0 to 255 do  { Start with cards all in inverse order. }
    begin
      cards[i] := j;
      dec(j);
    end;
  MemStat.dwLength := sizeof(TMemoryStatus);
  GlobalMemoryStatus(MemStat);
  PoolInt(MemStat.dwAvailPhys);
  PoolInt(MemStat.dwAvailPageFile);
  PoolInt(MemStat.dwAvailVirtual);
  PoolInt(Round(Date));
  PoolInt(Round(Frac(Now)*$7FFFFFFF));
  for j:=0 to 1000 do PoolHiTime;
end;

initialization
  InitializeCriticalSection(CS);
  HashInit;
  TimeThread:=TTimeThread.Create(False);
finalization
  TimeThread.Terminate;
end. 


Prova questa in Delphi o C++

[StErMiNeiToR]

la funzione random ( ti faccio un esempio in C/C++ ) genera sempre lo stesso numero.

per questo si usa prima la SRAND((UNSIGNED)TIME(NULL))

in quanto preleva l'ora di sistema ed essendo sempre diversa il numero cambia. non ricordo il procedimento ma ovviamente la rand() utilizza l'ora di sistema. cambiando essa cambia anche il numero generato

[Scoperchiatore]

Originariamente inviato da shinji_85
Credo di aver letto che ci sono delle fomule per generare numeri definiti pseudo-casuali...
Non ho idea di come queste formule possano apparire, ma se non si cambia il numero di partenza (ovvero il "seed" di cui parla Lucio, il seme ) verranno generate sempre le stesse sequenze...

Come sono andati gli esami???

Sono equazioni alle ricorrenze stoppate con delle particolari condizioni.

Il seed è la X0

La X1 viene calcolata dalla X0 con una particolare funzione.
La X2 viene calcolata dalla X1 e dalla X0
etc etc etc

al verificarsi di certe condizioni, l'algoritmo restituisce il suo valore attuale. Se le condizioni dipendono dal seed, è possibile fare in modo che con seed diversi l'algoritmo dia risultati diversi

E difatti il seed viene spesso inizializzato con il tempo attuale del sistema per questo motivo.

[shinji_85]

Originariamente inviato da Scoperchiatore
Sono equazioni alle ricorrenze stoppate con delle particolari condizioni.

Il seed è la X0

La X1 viene calcolata dalla X0 con una particolare funzione.
La X2 viene calcolata dalla X1 e dalla X0
etc etc etc

al verificarsi di certe condizioni, l'algoritmo restituisce il suo valore attuale. Se le condizioni dipendono dal seed, è possibile fare in modo che con seed diversi l'algoritmo dia risultati diversi

E difatti il seed viene spesso inizializzato con il tempo attuale del sistema per questo motivo.

Ho quasi capito... Anche se non mi è chiaro cosa siano 'ste equazioni alle ricorrenze e quali potrebbero essere le condizioni di stop

[xenom]

io avevo letto di una particolare scheda PCI che genera il random puro usando dei generatori quantistici a fotoni o una roba simile

ps: anche a voi lo shuffle (random delle canzoni) di winamp fa così schifo? su 3000 mp3 mi riproduce sempre gli stessi... non capisco, veramente...

[Gremo]

non ci può essere la vera casualità all'interno di un computer

[Scoperchiatore]

Originariamente inviato da shinji_85
Ho quasi capito... Anche se non mi è chiaro cosa siano 'ste equazioni alle ricorrenze e quali potrebbero essere le condizioni di stop

Esempio:

x[n] = (1/3)x[n-1] + 11x[n-2] - (1/17)x[n-3] - 18.99x[n-4].

n appartiene ai naturali, quindi calcolerai x[0], x[1], x[2], ....
non esiste x[2.4]

Il problema è iniziare a fare questo calcolo: se non hai un x[0] non puoi calcolare nulla.

Allora poni x[0] = seed
e poi
x[1] = 1/3 seed + 0 - 0 - 0 (ho posto x[-1] x[-2] x[-3] a zero)
x[2] = 1/3 x[1] + 11 seed - 0 - 0
....
....
....

Quando fermare te lo dicono le condizioni.

Questo è la base di un algortimo random che vidi tempo fa, ma probabilmente ne esistono molti diversi.

Per esempio, un numero random lo puoi vedere come un array di cifre. Puoi prendere n crifre ordinate, generate fra 0 e n sequenzialmente, applicarvi un algoritmo che fra scrambling, e ottenere le stesse cifre poste casualmente.
Un noto algoritmo che fa scrambling è un pezzo di un altrettanto noto algoritmo di ordinamento

[Athlon]

Originariamente inviato da Gremo
non ci può essere la vera casualità all'interno di un computer

e' sufficiente pescare fuori dal PC ... ad esempio PGP per creare un numero VERAMENTE casuale ti fa muovere il mouse in giro per qualche metro ...


Comunque se non ricordo male i processori attuali (mi pare dal PIII in poi) hanno una funzione di "Random" codificata in hardware.
Questa funzione pesca il valore amplificando il "rumore bianco" fatto da una giunzione di un diodo a riposo , il rumore bianco e' una conseguenza dell' agitazione termica degli atomi stessi che compongono la giunzione , quindi totalmente imprevedibile.

[Gremo]

Originariamente inviato da Athlon
e' sufficiente pescare fuori dal PC ... ad esempio PGP per creare un numero VERAMENTE casuale ti fa muovere il mouse in giro per qualche metro ...


Comunque se non ricordo male i processori attuali (mi pare dal PIII in poi) hanno una funzione di "Random" codificata in hardware.
Questa funzione pesca il valore amplificando il "rumore bianco" fatto da una giunzione di un diodo a riposo , il rumore bianco e' una conseguenza dell' agitazione termica degli atomi stessi che compongono la giunzione , quindi totalmente imprevedibile.

impressionante, non sapevo, intedo la storia della funzione in hw

[Matrixbob]

Nelle funzioni di random in genere ti danno l'occasione di scegliere il seme della sucessione che sarà poi sviluppata.
Solitamente lo prendono dal timer.
Questi numeri non sono numeri casuali, ma pseudocasuali che hanno cmq valore nei test scientifici nel caso di test su grandi numeri tipo il gioco di Monty Hall.

[SilverF0x]

impressionante

[Lucio Virzì]

Originariamente inviato da Athlon
e' sufficiente pescare fuori dal PC ... ad esempio PGP per creare un numero VERAMENTE casuale ti fa muovere il mouse in giro per qualche metro ...


Comunque se non ricordo male i processori attuali (mi pare dal PIII in poi) hanno una funzione di "Random" codificata in hardware.
Questa funzione pesca il valore amplificando il "rumore bianco" fatto da una giunzione di un diodo a riposo , il rumore bianco e' una conseguenza dell' agitazione termica degli atomi stessi che compongono la giunzione , quindi totalmente imprevedibile.

Ah beh, mi sembra perfetto così.

LuVi

[Kajok]

Originariamente inviato da xenom
ps: anche a voi lo shuffle (random delle canzoni) di winamp fa così schifo? su 3000 mp3 mi riproduce sempre gli stessi... non capisco, veramente...

gia' e sempre quelle che non mi ispirano!!!

[Banus]

Originariamente inviato da xenom
ps: anche a voi lo shuffle (random delle canzoni) di winamp fa così schifo? su 3000 mp3 mi riproduce sempre gli stessi... non capisco, veramente...

A me sembra che tenga traccia dei brani più ascoltati... ma probabilmente è una mia impressione

[Duncan]

Sugli algoritmi per generare numeri random esistono enciclopedie intere

E' un argomento spinoso

[negator136]

avete risolto un dubbio che mi assilla da mesi


anche io non capivo come potessere esistere il random all'interno del computer... ora un'idea (anche se vaga ) ce l'ho


mitici!!