L'importanza degli estremi

La settimana scorsa ho saltato ma avevo la scusa: ero in Italia. Comunque mi sembra doveroso fare qualche appunto.

  • Il Malpensa Express è un treno regionale che qualche volta fa quattro fermate e qualche volta ne fa mille, in ogni caso percorre 54 km, costa 10 euro ed è operato da TreNord. Durante il mio primo viaggio su codesto treno mi sono beccato il questionario sulla qualità del servizio. Coda di paglia?
  • Le Frecce hanno invaso i binari italiani, praticamente gli altri treni non esistono più, se vai sul sito di Trenitalia e vuoi andare da Vicenza a Grisignano di Zocco scopri che fai prima ad andarci a piedi, i pendolari avvertono un ineluttabile senso di sconforto: dev’essere più o meno quello che provavano i Neanderthal quando hanno incontrato il primo Sapiens, e quello non aveva neanche il wifi a bordo… oh, wait.
  • Ho dovuto pagare un riscatto di ben £ 86,40 per poter uscire dal parcheggio di lunga permanenza all’aeroporto di Luton che avevo prenotato in anticipo pagando circa 40 sterline. Perché? Perché all’ingresso il sistema di riconoscimento della targa ha letto male la mia e ha ben pensato di farmela pagare cara, facendo pure finta di niente e pensando di essere al parcheggio di breve permanenza. Il giorno dopo mi hanno sentito, mi hanno chiamato “Ms”, e mi hanno restituito i soldi al volo.
  • I bambini sotto i 5 anni sono i nuovi corrieri della droga. I tamarroni pieni di piercing invece possono passare facendo suonare il metal detector e non essere nemmeno perquisiti perché l’addetta dall’altra parte li conosceva. E no, non è successo a Malpensa.
  • Le hostess di EasyJet ti vedono in difficoltà con le ginocchia e ti fanno sedere nei più larghi posti accanto alle uscite di emergenza, a patto che tu voglia prenderti la responsabilità di aprirle nell’improbabile eventualità di un atterraggio di emergenza. Con Ryanair se vuoi prenderti questa responsabilità devi pagare. I piloti di EasyJet sanno atterrare controvento, quelli di Ryanair non riescono nemmeno ad evitare che l’aereo rimbalzi quando tocca terra.
  • Se nel Regno Unito vedi scritto “deviazione” comincia pure a piangere: tu pensi di dover andare da una parte e la deviazione ti porta dalla parte opposta, senza specificare altro.

Comunque sono stati sei bei giorni, ho rivisto gente, ho preso un po’ di sole e l’ho riportato su a scaldare l’algida Albione. Così tanto che in questo momento sto con le finestre aperte mentre due settimane fa in casa mettevo canottiera, maglietta, felpa e maglione.

C’è un’altra cosa di cui avevo accennato e che non ho mai approfondito. Non è che ora… però almeno qualche passo avanti l’ho fatto. Uno dei problemi dei generatori di numeri casuali è che molto spesso sono pseudocasuali, cioè c’è un algoritmo che, a partire da un numero chiamato seme genera una sequenza di numeri con un periodo estremamente lungo, nell’ordine anche di 20 cifre, che sono tante. Purtroppo sono pochissime quando si deve generare quantità vergognosamente grandi di numeri casuali, e quindi la soluzione tipica è ricorrere alle sorgenti fisiche. Gli esempi classici sono piazzare un’antenna, scorrere un po’ di frequenze, e catturare il rumore, oppure sondare le temperature o le oscillazioni di carica nei circuiti integrati… soluzioni di alta qualità ma spesso tragicamente lente, in grado di generare non più di qualche centinaio di migliaio di numeri al secondo. E quando te ne servono alcune centinaia di miliardi, l’attesa può diventare un problema.

Ora, i moderni cellofoni hanno in genere questi giocattolini chiamati accelerometri e magnetometri, al loro interno, che altro non sono che degli integrati che sputano fuori dei numeri. Questi numeri ovviamente non sono casuali, dipendono dall’orientamento del dispositivo, dai campi elettromagnetici da cui è investito, e da alcuni altri fattori più o meno trascurabili. Peggio ancora, tipicamente sono molto lenti. Per fare un esempio, l’accelerometro dell’iPhone è in grado di fornire circa 300 numeri al secondo, avendo tre assi e campionandolo 100 volte al secondo.

Con l’avanzare di crittografie sempre più sofisticate, con chiavi sempre più lunghe, la necessità di avere velocemente numeri (pseudo)casuali di alta qualità è evidente [1]. La soluzione standard è costruire un pool di entropia da cui attingere a piene mani quando servono numeri nuovi. Questi pool vengono riempiti e rinfrescati costantemente dal sistema operativo usando ogni cosa a sua disposizione: i tasti battuti dall’utente, i movimenti del mouse, campionamenti pseudocasuali dalla memoria, letture dai vari sensori di cui il computer dispone…

Qualche tempo fa mi è venuta voglia di scrivere un’applicazione per iOS che, sfruttando proprio l’accelerometro, generasse numeri casuali di alta qualità e in grande quantità. L’idea era di fare una specie di coltellino svizzero della casualità, in grado sia di generare enormi quantità di numeri in poco tempo e metterli a disposizione in tempo ragionevole, sia di generare le classiche scemenze tipo i d20 o le password. Sto ancora lavorando sulle applicazioni, ma prima di tutto volevo assicurarmi che il giochino fosse fattibile. La chiave di tutto è avere un buon generatore con distribuzione uniforme, il che vuol dire che ogni numero compreso in un certo intervallo ha la stessa probabilità di essere estratto rispetto agli altri, un po’ come quando si tira un dado non truccato.

Ci sono innumerevoli funzioni (almeno tre) per generare numeri pseudocasuali. Quella che va più di moda è arc4random() che può essere chiamata in qualsiasi momento, non necessità di essere inizializzata, produce sequenze esageratamente lunghe prima di cominciare a ripetersi, ed è di una lentezza disarmante. Un po’ più veloce è rand() che però deve essere inizializzata, produce sequenze ridicolmente brevi, e chi programma in C da lungo tempo sa bene quanto temere la chiamata “srand(time(NULL))”. Tra le due c’è random() che produce sequenze decenti e sarebbe meglio reinizializzarla ogni tanto.

Così mi sono detto: perché non richiedere una manciata di numeri a random() e poi reinizializzarla usando un seme basato su una sorgente fisica… tipo l’accelerometro? Così il rischio di ripetizioni della sequenza praticamente dovrebbe annullarsi. Detto fatto, il codice è così banale che non ve lo scrivo nemmeno, ho generato una certa quantità di numeri (65536, per i più curiosi) compresi tra 0 e 1, l’ho fatto più volte tanto per avere una quantità di dati da esaminare, e poi li ho importati in Octave per darci un’occhiata.

La linea blu è il dataset che ho generato con l’iPod, la linea rossa è un dataset che ho generato con l’apposita funzione di Octave, tanto per avere un termine di paragone. Il grafico mostra l’istogramma con 50 cestini, che poi vuol dire che ho diviso l’intervallo [0,1] in cinquanta intervallini e per ciascuno di questi ho contato quanti dei numeri generati ci finivano dentro. Idealmente ciascun intervallo dovrebbe contenere la stessa quantità di numeri degli altri. Poi in pratica non è proprio così, ma non siamo mica nell’iperuranio. Due cose comunque si notano:

  1. per la maggior parte, la distribuzione è effettivamente uniforme: potrebbe essere meglio ma non fa neanche schifo;
  2. a ben guardare, né il dataset generato con l’iPod né quello generato da Octave contengono né 0 né 1.

Questa cosa degli estremi mi ha fatto molto pensare, soprattutto al fatto che potrebbe esserci stato un problema di approssimazione nella divisione in virgola mobile. La verità è che random() genera numeri casuali tra 0 e (2^31)-1 e quindi ciascun numero andava normalizzato per risultare nell’intervallo [0,1] che serviva a me, e questo è un problema classico nel calcolo numerico ad alta precisione. Così ho saltato la divisione e ho analizzato direttamente gli interi. Stesso risultato: degli estremi nessuna traccia.

A questo punto il problema è chiaro: con i numeri casuali non si può mai sapere quello che succede. Potrebbe essere che ci aspettiamo di vedere uscire il numero 4 e in un miliardo di estrazioni non esca mai [2]. Questo però non vuol dire che possiamo assumere che un bel giorno uscirà anche lo zero e andare avanti.

Se a qualcuno venisse qualche idea, io sono in ascolto.

  1. A chiunque si intenda un minimo di crittografia :)
  2. A meno che non usiamo Debian, allora è garantito.

Commenti

Cico » 

Sicuro che sia una questione di estremi?

Hai controllato se gli estremi dei bucket vengono mai generati?
(esempio quante volte compare il 0.02 o il 0.04 …. )

Pensa un numero da 0 a 1 quante volte compare quel numero esatto?

Che precisione hanno i numeri generati?

Se prendi un dataset di 400 persone sicuramente due di loro sono nate lo stesso giorno ma se andiamo a vedere ore-minuti-secondi…

Nessuna freccia potrà mai colpirmi, io sono Zenone!
Buhahahaha!!!

Andrea Franceschini » 

L’argomento della precisione (single float) viene facilmente smontato quando si torna ad analizzare gli interi tra 0 e $holyCrap (dove $holyCrap = (2^31)-1). L’occorrenza degli estremi dei bucket è implicitamente provata dal fatto che nei bucket di mezzo la distribuzione è abbastanza uniforme… è chiaro che con soli 2^16 campioni non si prova granché ma il saggio ci insegna che a sparare a caso ci si prende sempre, e quindi mi sento di affermare che gli estremi dei bucket dal secondo al quarantanovesimo vengono estratti whp e sol (sooner or later).

Un test empirico mi dice che 0L viene generato da random() (ho dovuto scomodare l’halting problem ma alla fine ce l’ho fatta) almeno su OS X e Linux, sull’iOS non l’ho provato, lo farò per completezza, ma sono quasi sicuro che venga generato anche in quel caso, il che mi porterebbe a tranquillizzarmi un po’ circa la mia applicazione particolare. Inoltre la specifica di random() dice che può addirittura generare sequenze di zeri lunghi quanto la lunghezza dello shifting register che usa internamente, quindi potenzialmente potremmo anche avere una sequenza di 32 zeri (31?) ma vabè, non è che sto cercando quella, e anche se fosse campa cavallo.

Comunque non volevo dirtelo ma Zenone è morto.

Cico » 

Avevo confutato con un commento bellissmo ma poi mi è sorto il dubbio che stessimo dicendo la stessa cosa e mi è passata la voglia di rileggerre.
Comunque Zenone è morto sì ma nessuna freccia lo ha mai colpito!

Andrea Franceschini » 

Nuoooooo!

Allora avrà mangiato troppi punti geometrici. Vedi a farsi i paradossi per togliersi i sensi di colpa.

oscar paolo » 

Non sono un esperto di generazione di numeri casuali o pseudocasuali, ma visto l’argomento interessante volevo porre alcune domande da profano: E’ possibile generare una serie numerica (variabile da 1 a 20 ad esempio) che rispetti dei “vincoli” da noi stabiliti e che permettano di condizionare la distribuzione? Ad esempio la serie non puo’ avere la presenza di 20 numeri diversi tra loro in sequenza, o un qualsiasi numero puo’ avere un ritardo massimo di apparizione uguale a 400 etc. Che software è meglio usare? grazie e scusate se sono un po fuori argomento..

Andrea Franceschini » 

Quello che chiedi è certamente possibile, in effetti imporre vincoli è una delle cose che riescono meglio non solo nel campo dell’informatica, ma all’umanità in quanto tale. Non saprei dirti che software particolare usare ma ho in mente numerose possibili soluzioni, dalle più semplici alle più raffinate, per risolvere il tuo problema, e per la maggior parte si tratta di veramente poche righe di codice. Se non sei pratico di programmazione ma la cosa ti interessa, mi sembra un buon momento per imparare qualche linguaggio, tipo Python o Ruby.

Nello specifico, il primo problema mi sembra di capire che tu voglia una sequenza di numeri casuali che però nell’arco di 20 estrazioni presenti almeno una ripetizione. In questo caso direi che la soluzione creare un insieme degli ultimi 20 numeri estratti e, ogni tanto, andarne a pescare uno a caso tra quelli invece di chiederli al generatore di numeri casuali. Ho in mente alcuni casi critici, per esempio quello in cui i primi 19 numeri sono tutti diversi, il ventesimo è uguale al primo e il ventunesimo è l’unico non estratto fino a quel momento. Se consideri la sequenza dal secondo al ventunesimo chiaramente il vincolo è violato. Sono sicuro che ci sia un modo facile per risolvere il problema (magari imponendo una certa frequenza con la quale i numeri dal set dei già estratti vengono usati nella sequenza che stiamo generando, per esempio uno ogni 9 dovrebbe risolvere il problema facilmente). Altri casi critici avranno sicuramente soluzioni analoghe.

Per quanto riguarda il vincolo sul ritardo, la soluzione è quasi analoga. Devi avere una tabella dei numeri estraibili e, ad ogni estrazione, incrementi di 1 il ritardo di ogni numero tranne di quello appena estratto che invece viene riportato a 0. In questo modo ti dovrebbe essere facile capire di volta in volta quali sono i numeri che si stanno approssimando al ritardo massimo e quindi estrarli forzosamente prima che sforino il massimo. Occhio che un approccio banale porta sicuramente a sequenze ripetute per cui potrebbe essere interessante istituire un margine di ritardo massimo in modo da avere un pool di numeri tra cui scegliere a caso, per esempio i 10 numeri con ritardo tra 391 e 400.

Rispondi