View Full Version : Random - Il paradosso
SilverF0x
02-03-2005, 21:45
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 :D
Lucio Virzì
02-03-2005, 21:52
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 :D
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
02-03-2005, 22:00
sposto nella sezione scienza e aggiungo un piccolo contributo
http://www.dis.uniroma1.it/~alberto/didattica/Genratore_numeri_casuali.pdf
shinji_85
02-03-2005, 22:00
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 :D ) verranno generate sempre le stesse sequenze...
Come sono andati gli esami???
Scoperchiatore
02-03-2005, 22:02
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++ :D
StErMiNeiToR
02-03-2005, 22:03
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
02-03-2005, 22:04
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 :D ) 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
02-03-2005, 22:08
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
io avevo letto di una particolare scheda PCI che genera il random puro usando dei generatori quantistici a fotoni o una roba simile :asd:
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... :asd:
non ci può essere la vera casualità all'interno di un computer :O
Scoperchiatore
02-03-2005, 22:59
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] :D
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 :D
Originariamente inviato da Gremo
non ci può essere la vera casualità all'interno di un computer :O
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.
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.
:eek: impressionante, non sapevo, intedo la storia della funzione in hw
Matrixbob
03-03-2005, 00:29
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
03-03-2005, 07:10
impressionante:D :eek:
Lucio Virzì
03-03-2005, 11:14
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
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... :asd:
gia' :muro: :muro: e sempre quelle che non mi ispirano!!!
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... :asd:
A me sembra che tenga traccia dei brani più ascoltati... ma probabilmente è una mia impressione :p
Sugli algoritmi per generare numeri random esistono enciclopedie intere :)
E' un argomento spinoso
negator136
03-03-2005, 14:17
avete risolto un dubbio che mi assilla da mesi :D
anche io non capivo come potessere esistere il random all'interno del computer... ora un'idea (anche se vaga :p) ce l'ho :D
mitici!! :)
Originariamente inviato da Banus
A me sembra che tenga traccia dei brani più ascoltati... ma probabilmente è una mia impressione :p
infatti! l'ho notato anch'io! sempre quelli escono...
i più ascoltati... ma che stronzata è? l'hanno fatto apposta? io metto lo shuffle proprio perchè mi sono rotto di ascoltare sempre i soliti brani, e quel cazzo di programma li tiene in memoria e pesca quelli? :asd:
SilverF0x
07-03-2005, 19:28
sapete un libro o qlc che ne parla visto che mi dite che ci sono enciclopedie intere?
Ziosilvio
07-03-2005, 22:17
Originariamente inviato da SilverF0x
un libro o qlc che ne parla
Donald E. Knuth, "The Art of Computer Programming", Volume 2: Seminumerical Algorithms, Addison-Wesley.
Matrixbob
08-03-2005, 00:13
Originariamente inviato da SilverF0x
sapete un libro o qlc che ne parla visto che mi dite che ci sono enciclopedie intere?
Infatti io non ne ho mai vista enciclopedie intere ma qualche capitoletto.
non capisco perchè bisogna sempre esagerare nel descrivere le cose.:sofico:
hakermatik
09-03-2005, 11:53
una volta alle superiori, il mitico prof, di informatica ci fece scrivere l'algoritmo random (o meglio, ci fece vedere come fare...) utilizzando l'ora di sistema.
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.