Migliorare la generazione di numeri casuali senza librerie

Claudio_FF · May 11, 2019, 9:15am

Quello che temo è che si finisca comunque sempre per generare valori con una distribuzione gaussiana... o con molte gaussiane.

Ad esempio se i bit arrivassero casualmente 0 o 1, in un gruppo di 8 mediamente ne avremmo quattro a 1, e quindi tutti i valori con quattro bit a 1 risulteranno molto più frequenti.

Standardoil · May 11, 2019, 9:49am

mi sembra strano
qualcosa in questo ragionamento non mi torna
se 0 o 1 sono equiprobabili, all'ora sono equiprobabili anche tutte le loro combinazioni
vero è che mediamente sono 4 bit a 1, e questo significa che spesso si trova UNA delle combinazioni con 4 bit a uno, ma essendo queste un numero maggiore di quelle con tre bit a uno ...
poi mi sono perso
ci si sente dopo..........

Claudio_FF · May 11, 2019, 10:41am

Standardoil:
se 0 o 1 sono equiprobabili, all'ora sono equiprobabili anche tutte le loro combinazioni

None... se lanci due dadi i numeri da 2 a 12 non hanno la stessa probabilità, se lanci otto monete le teste da 0 a 8 non hanno la stessa probabilità.

Standardoil · May 11, 2019, 10:49am

Il numero di teste

Ma le singole combinazioni di 8 bit a caso?
Pomeriggio ci penso... Perché non sono convinto
Esercizio propedeutico
Numero di possibili combinazioni con 0 bit a 1
1
numero di possibili combinazioni con 1 bit a 1
8
Numero di possibili combinazioni con 2 bit a 1
8 per 7 a fare 56 (edit 56 56 56 non 256, maledetto furbofono)
Ma è ovviamente imposibile che continui così
Anche perché
Numero di possibili combinazioni con 8 bit a 1 non è
8 per 7 per 6 per 5....

Claudio_FF · May 11, 2019, 11:15am

Standardoil:
Ma le singole combinazioni di 8 bit a caso?

Se in 8 bit a caso (in cui ciascun bit ha esattamente il 50% di probabilità di risultare alto) la probabilità di vedere 4 bit alti è maggiore di quella di vederli tutti bassi o tutti alti, allora tutti i valori rappresentati con 4 bit alti (in qualunque posizione) appariranno più spesso, mentre lo 0 o il 255 raramente.

Standardoil · May 11, 2019, 12:11pm

No, è una cosa risaputa
Quello che non ricordo è perché no
Comunque se i singoli bit fossero a pari probabilità allora anche i byte saranno equiprobabili
Non vale nemmeno la pena scommetterci, non è che ne sono sicuro: È una certezza matematica!
Come ho già detto: è più probabile l'insieme della sequenze di 4 bit a 1, non lo sono le singole sequenze
Il paragone coi dadi è fallace, nei byte i bit non si sommano, coi dadi i numeri sì

Claudio_FF · May 11, 2019, 1:48pm

Queste sono le occorrenze di 100 megabyte estratti componendo ogni byte con singoli bit equiprobabili... se qualcuno ha voglia di graficarli... (naturalmente il primo valore sono le sortite dello zero e l'ultimo del 255).

Magari sottraendo una costante, ad esempio 380000, si evidenzia meglio la parte variabile:

...a dire il vero mi aspettavo scostamenti maggiori

Questo il codice Py3 usato per ottenere i valori:

from random    import randrange
from functools import reduce

def genbyte():
    n = [randrange(2) for _ in range(8)]
    return reduce((lambda x, y: x<<1 | y), n, 0)

storico = [0] * 256
for _ in range(100000000): storico[genbyte()] += 1

for n in storico: print(n)
storico2 = [storico[n]-380000 for n in range(256)]
for n in storico2: print(n)

Standardoil · May 11, 2019, 2:16pm

Che spreco di lavoro
Non c'è differenza nelle previsione
I singoli bit sono ugualmente probabili
Ugualmente probabili le loro combinazioni
È una vergogna che hai dovuto provare
Ancora peggio che ti stai arrampicando sugli specchi per una causa sbagliata...

Standardoil · May 11, 2019, 3:23pm

A parziale "rettifica" di quello che ho scritto prima:
lo ho scritto, poi ripensandoci, è andata via la corrente
ora, delle due l'una
o abbiamo qui un temporale
oppure io non devo ripensare: fa male agli impianti elettrici
sono uscito in cortile e mi sono bagnato
Ergo ripensare è concesso.......
ripenso quindi:
Non volevo essere offensivo
se lo sono stato me ne dispiace
dopo tutto il tempo passato prima che tornasse energia non sarebbe giusto che io editassi adesso il mio post precedente

Standardoil · May 11, 2019, 3:29pm

invece per la generazione del numero casuale con poco HW aggiuntivo..
stavo pensando che in buona sostanza a noi serve un buon seme, con un'alta entropia
OK, trovato ce lo teniamo stretto
se, ad ogni accensione, noi leggessimo da EEPROM il seme "vecchio", lo "mescolassimo" con una new-entry, lo usassimo come seme e poi ne facessimo generare uno nuovo da salvare in eeprom....
con una semplice lettura di un pin analogico libero ce la caviamo, dato che è pur vero che l'entropia di una sola lettura è bassa, ma così facendo aumenteremmo progressivamente l'entropia generale, senza condividere con l'esterno, si tratterebbe sempre e solo di letture casuali di un device "locale", ma nel tempo, spero con poche accensioni, ci troveremmo ad avere un seme in EEPROM semplicemnte imprevedibile, dato che facilmente nemmeno ci ricordiamo con esattezza quante volte abbiamo resettato o riacceso arduino

paulus1969 · May 11, 2019, 3:58pm

Sarebbe bene mettersi d'accordo su alcuni punti di base.

Cosa si intende per "hardware esterno"? Qual è il limite che ci poniamo? Anche il pezzo di filo è un hardware esterno, lo accettiamo? Se aggiungiamo un diodo? Se aggiungiamo un condensatore? E così via.
Principalmente: cosa intendiamo per "casuale" e - quindi - per "sequenza casuale"?
Ci accontentiamo di generare un seme e poi andare avanti con la sequenza pseudo-casuale che ne deriva? Oppure vogliamo ottenere un metodo per generare una sequenza che non sia pseudo-casuale ma casuale?

Standardoil · May 11, 2019, 4:02pm

io per l'hardware non ho una risposta, andrei di estemporaneo, quello che c'è sul momento si usa, altrimenti un tocco di filo penzolante
invece non re-inventerei nuovi generatori pseudo-casuali
mi accontenterei di avere un buon seme, utilizzando generatori esistenti
magari "trucco" un pochino, genero due numeri, il secondo mi dice quante cifre del primo sostituire con le corrispondenti di una nuova lettura "dell'inseminatore"

Claudio_FF · May 11, 2019, 4:16pm

Standardoil:
Non volevo essere offensivo

Beh nelle discussioni strettamente tecniche si è ormai asettici
In realtà sono solo perplesso, perché (forse) crolla un pilastro portante che è un filmato visto nell'aula di fisica dell'ITIS ben 39 anni fa. Se lancio 10mila monete mi aspetto in media di vedere sempre metà teste (comunque siano disposte) salvo le fluttuazioni statistiche del singolo lancio. E assumo anche che lanciare 10k monete una volta sola, o lanciare una moneta sola 10k volte è la stessa cosa. E per dare enfasi al concetto usavano un fotometro per misurare la luce riflessa da innumerevoli cartellini bianchi e neri che ruotavano casualmente 50%. Ora non so se lavorare con solo 8 bit è del tutto insufficiente per manifestare il fenomeno, ma il concetto era che benché nulla impedisse a tutti i cartellini di posizionarsi contemporaneamente su nero o su bianco, di fatto questo non avveniva mai (in tempi umanamente osservabili). Quindi perché in 10kbit, con i bit singolarmente casuali al 50%, che corrispondono alle 10kmonete e ai 10kcartellini, le combinazioni tutti zeri o tutti uni dovrebbero invece avere la stessa probabilità di quelle metà zeri e metà uni?

Standardoil · May 11, 2019, 4:40pm

no, ti sfugge un concetto
è verissimo che mediamente ci saranno 4 bit ad 1
e che quindi le combinazioni con 4 bit a 1 saranno mediamnete più frequenti delle altre
per l'esattezza
nessun bit a uno o tutti i bit a 1 sono frequenti uno su 256
1 bit a uno oppure 7 bit a 1 sono frequenti 8 su 256
2 bit a uno sono frequenti 28 su 256, e anche 6 bit a uno
3 bit a uno fa 56 su 256
come anche 5 bit a uno
mentre 4 bit a uno è frequente 70 su 256
MA
SICCOME
le combinazioni con 4 bit a uno SONO esattamente 70
la frequenza della "singola" combinazione è 1 su 256
arriviamoci in altra maniera
primo bit, 50 percento di probabilità alto 50 basso
delle possibili 256 possibilità complessive 128 avranno il bit alto e 128 avranno il bit basso, a pari merito come frequenza
secondo bit, stesso discorso, qualunque sia stato il primo bit le 128 possibilità rimaste saranno 64 col secondo bit alto e 64 col secondi bit basso, anche qui a pari merito
terzo bit, fanno 32 a pari merito
quarto bit fanno 16
5° 8
6° 4
7° 2
ottavo bit rimangono 2 possibilità, una col bit alto e una col bit basso
siamo arrivatoi all'ottavo bit e tutte e due le rimaste sono pari merito
adesso scegli di navigare l'albero delle possibilità come vuoi, ad ogni bivio ti ritroverai SEMPRE con le possibilità uguali sia a destra che a sinistra
ogni singola possibilità ha la stessa frequenza di tutte le altre

anche coi dadi è così, se NON fai la somma
la probabilità che esca 6-2 (per esempio, che significa 6 sul primo e 2 sul secondo) è la stessa che esca 1-1
anche se la "somma" delle cifre di "due" dadi è più frequente che sia 7 (mi sembra)

Standardoil · May 11, 2019, 4:54pm

Claudio_FF:
In realtà sono solo perplesso, perché (forse) crolla un pilastro portante che è un filmato visto nell'aula di fisica dell'ITIS ben 39 anni fa.

erano i filmati della Esso Italia?
filmati americani in B/N con dei laboratori piuttosto vuoti, uno o giusto due sperimentatori?
in realtà non li aveva fatti la Esso Italia, e nemmeno la mia azienda in America
non ho mai capito come sia che la Esso Italia li avesse distribuiti......
mi ricordo Millikan, mi ricordo la legge di gravitazione universale, la relatività Galileiana, il radiometro solare, miiii quanti ricordi.... è stato allora che ho deciso il mio soprannome (a dir la verità sono stati i miei compagni di classe, che me lo "hanno deciso addosso" proprio in assonanza con la casa madre di quella del filamto)

Claudio_FF · May 11, 2019, 6:59pm

Standardoil:
erano i filmati della Esso Italia?

Fantastico! Eccolo kva https://www.youtube.com/watch?v=gryr_MPPTMU

Standardoil · May 11, 2019, 7:48pm

non mi ricordavo che ci fossero tutti questi mostri sacri dell'automobilismo
ma dimmi una cosa, lo hai trovato oggi?

paulus1969 · May 12, 2019, 7:13am

La frequenza tende alla probabilità quando provi INFINITE volte.

Se fai un SINGOLO lancio di otto monetine, la probabilità di ottenere la combinazione (1=testa 0=croce)

0 0 0 0 0 0 0 0

è la stessa di quella di ottenere la combinazione

0 1 0 1 1 0 0 1

(indipendentemente dal fatto di lanciare insieme otto monete o lanciare la stessa moneta otto volte, in quanto ogni lancio ha il 50% di dare testa ed il 50% di dare croce indipendentemente da eventuali lanci precedenti)

Quindi dirai: "ma come mai allora ottengo più volte le combinazioni con quattro 1 quasi mai quella con otto 0?"

Proprio per il fatto che la frequenza tende alla probabilità, ma se tu ACCORPI tutte le possibili sequenze con quattro 1 e ne vedi ogni occorrenza come evento "sono usciti quattro 1" allora l'evento "sono usciti quattro 1" si verificherà più volte dell'evento "sono usciti otto 0", ma solo in quanto in realtà l'evento "otto 0" è UNO mentre GLI eventi "quattro 1" sono molti di più e tu li accorpi in un unico evento da contrapporre all'evento "otto 0".
Se invece guardi le singole sequenze, la prima (00000000) ha la stessa probabilità della seconda (01011001) e se lanci tante volte tenderà ad avere la stessa frequenza.

E' come al poker, riceverai la sequenza di carte "Ac, Af, Aq, Ap, 9c" con la stessa probabilità di ricevere "10c, 9f, Kf, 10p, Qq", il fatto che la prima valga più della seconda deriva dalla nostra convenzione che ci serve per selezionare facilmente le combinazioni vincenti, infatti è facilissimo riconoscere un poker d'assi mentre vattela a ricordare la seconda sequenza... a quel punto si sceglie di rendere vincente il poker e se ne calcola la probabilità e quindo la posizione rispetto al tris, al full....

Standardoil · May 12, 2019, 9:19am

no, non concordo
al poker le cose sono differenti ancora, non mischiamo gli esempi giusti (lancio delle monetine) con quelli sbagliati (poker d'assi)
il poker non è un gioco che rappresenta la statistica in "pieno"
il tuo ragionamento vale se confrontimla probabilità di riceve un poker d'assi con quella di ricevere un poker di 9 con quella di ricevere una qualunque sequenza
ma le regole del poker non equiparano il poker ad una qualunque sequenza
tu hai un'infinita di sequenze qualunque, e solo UN poker d'assi, che è un tocco più probabile di quello che credi, dato che nell'insieme della carte ne definisce solo 4, lasciando libera la 5 (con l'unica regola che non sia un'altro asso, che sarebbe impossibile)
quindi, una volta definito il mazzo (completo o all'italiana?) le probabilità relative di un poker (4 carte uguali e una indifferente) è molto minore di un .... qui bisogna fare dei distinguo
ci sono casi, nel poker all'italiana, vado a memoria non gioco dalle superiori, che "almeno" una coppia (non vestita) sia "certa", non probabile
a scombinare il tutto nel poker si aggiunge il "cambio",
usare il poker come esempio non vale...............

maubarzi · May 12, 2019, 10:53am

paulus1969:
Sarebbe bene mettersi d'accordo su alcuni punti di base....

Secondo me, lo scopo dovrebbe essere quello di fornire una gamma di possibili soluzioni per massimizzare l'entropia nell'identificazione di un seme per inizializzare il generatore di numeri casuali standard.

Perchè dico un insieme e non una soluzione?
Perchè non possiamo contare su nulla di assolutamente disponibile e quindi a seconda dei casi potremmo dover usare cose diverse.
Con un esempio, usare un pin analogico volante per fare una lettura casuale potrebbe essere impossibile se ho tutti i pin occupati.

Quindi:

Utilizziamo la funzione random
Inizializziamo con un seme
Usiamo tutti i bit dell'unsigned long del seme
Non usiamo alcun elemento esterno, se possibile, o dichiariamolo bene se facilmente implementabile e utile al risultato.

Ora, dovessimo fare crittografia potremmo interrompere qui la discussione perchè con gli strumenti a disposizione, con molta probabilità, non potremmo mai generare qualcosa di veramente sicuro e casuale.
Limitiamoci quindi ad una soluzione che può essere accettabile sulla base dei primi 3 punti.

Quindi lo scopo principale è generare un unsigned long con la massima irregolarità possibile.

Riguardo la probabilità di ottenere 8 zeri o 4 bit a 1, è già stato detto che sono due cose differenti, come per ottenere due 1 ai dati o un 7, perchè da un lato si confronta una singola combinazione e dall'altro un risultato ottenibile da N combinazioni. Quindi non aggiungo altro, se non il fatto che proprio per questo motivo ho barrato quasi tutto un mio precedente post perchè causa i fumi dell'alcool ero caduto proprio in questo errore, ma mi sono ravveduto prima di eventuali stimoli esterni

Direi che possiamo procedere dichiarando bene gli elementi esterni necessari in modo da poter valutarne la disponibilità e la facilità di implementazione così da dare maggior scelta implementativa direttamente legata alla variabilità ottenibile.
Es. filo penzolante, RTC, condensatore oscillante...

Topic		Replies	Views
Random number generator for Arduino? General Guidance	73	1466	September 27, 2025
Random input for randomseed Programming	42	1611	November 14, 2024
Random() is much too slow UNO R4 WiFi	22	366	August 8, 2025
Mesure analogique et signal aléatoire Français	34	295	February 12, 2025
Aiuto!! cerco aiuto per scrivere il codice!! Generale	65	3416	May 7, 2021

Migliorare la generazione di numeri casuali senza librerie

Related topics