Migliorare la generazione di numeri casuali senza librerie

In altro thread ci era venuta la balzana idea di provare a migliorare la generazione di numeri casuali, senza usare particolari librerie. Ce ne sono già alcune, di cui una in particolare fa uso di registri a scorrimento lineari, una cosa abbastanza complessa anche se molto più efficiente ed affidabile).

Il problema principale è quale “seed” utilizzare per la reandomSeed() perché la generazione di numeri pseudocasuali dipende dal valore iniziale (stesso valore iniziale, stessa sequenza) che è un unsigned long.
Generalmente si fornisce come seed il valore di un pin analogico lasciato libero (“flottante”) il quale restituisce valori non costanti in quanto dipendono da disturbi elettromagnetici di varia natura. Il problema è che questo valore va da 0 a 1023, quindi di fatto facendo ad esempio:

randomSeed(analogRead(A0));

si possono avere al massimo 1024 diverse sequenze pseudocasuali, non di più. Qualcuno suggeriva anche di usare millis() ma anche questo valore sarebbe troppo limitato e limitante in quanto all’accensione il valore restituito sarà più o meno sempre lo stesso.

Sicuramente ci sono stati studi sull’argomento, ma ci piaceva cercare di trovare una proposta migliorativa senza scavare in rete. :wink:

A questo punto era sorta l’idea di combinare 3 diverse letture da 10 bit ciascuna (scartandone alcune nel mezzo, per dare il tempo al convertitore di “assestarsi” su un valore probabilmente differente) in un unsigned long, e questo era un esempio di possibile codifica:

void randomize(int pin)
{
  unsigned long seed = 0;
  for (int i=0; i<=2; ++i)
  {  
    seed += analogRead(pin)>>(i*8);
    for (int j=0; j<=4; ++j)
    {
      delay(2);
      analogRead(pin);
    }
  }
  randomSeed(seed);
}

Il dubbio però è quanto l’analogRead() sia realmente “fluttuante” ossia non credo che il range sia proprio l’intero 0-1023, e da questo quindi se i seed così generati possano essere distribuiti in maniera sufficientemente uniforme all’interno del range previsto, o se invece la lettura analogRead() restituisca valori relativamente limitati come estensione.

Seguirà sperimentazione pratica, ma sono ben accette idee ed argomentazioni statistico-matematiche utili a migliorare quella funzione randomize() :wink:

Preso un Arduino NANO da una scatla, fatto girare una sola volta uno sketch di test che per ogni pin analogico fa 10 letture e stampa il risultato.
Ottenuto:

A0: 406 406 406 406 405 405 405 405 405 404 
A1: 352 352 351 351 351 351 351 351 350 349 
A2: 313 312 311 310 310 311 310 309 308 309 
A3: 315 314 314 314 314 313 312 313 313 313 
A4: 300 300 301 300 299 299 299 299 299 298 
A5: 285 285 284 283 284 284 284 283 282 283 
A6: 288 287 287 287 288 287 286 286 286 287 
A7: 282 283 283 283 282 281 282 282 281 280

Preso un secondo NANO e ottenuto:

A0: 443 443 443 442 442 442 442 442 442 441 
A1: 455 455 455 455 455 455 456 457 455 454 
A2: 448 448 446 445 446 447 447 445 444 445 
A3: 459 457 458 459 459 458 456 457 458 458 
A4: 482 484 485 484 482 482 483 484 482 481 
A5: 454 453 452 451 452 453 452 450 450 451 
A6: 486 485 487 488 488 485 485 486 488 487 
A7: 463 464 464 463 461 461 463 463 461 460

Terzo NANO:

A0: 396 396 396 396 395 395 395 395 395 395 
A1: 368 368 368 368 367 367 366 364 364 365 
A2: 349 348 349 350 349 347 346 347 348 347 
A3: 338 339 339 338 336 337 338 338 336 335 
A4: 323 321 320 320 321 322 320 319 319 320 
A5: 311 310 311 312 311 309 308 310 311 309 
A6: 320 321 321 319 318 319 319 320 318 317 
A7: 334 333 331 331 333 333 331 329 330 332

Devo provare con tutti i 7 nani? o possiamo dire che non è molto variegato il risultato?

Però possiamo dire che sei dotato quasi quanto un negozio.....

Mi chiamano Bianca Neve :wink:

Se ad inizio loop stampo millis() ottengo sempre e solo un valore che non cambia mai, che si avvii o si resetti, come da aspettativa!!!

Quindi i due metodi della analogRead e della millis producono poca varianza.
Quello con millis pressochè nessuna.

Attaccare filo libero a un pin analogico
Attorcigliarlo sul cavo della spina del frigorifero

Oppure usare tempi e bounce di un bottone cinese (no roba di marca)

Senza librerie va bene
Ma io ho due scarpiere, sono anche loro profonde 33 come le librerie, le posso usare?

Seriamente, senza hw aggiuntivo nulla si fa, poniamo un limite massimo?
Ad esempio, usando un apparecchio (sicuro per costruzione) come l'alimentatore di qualche vecchio router d-link, che andavano a 9v ca
Un partitore per stare dentro nei 5 volt di Arduino
Si misura il valore della sinusuoide dell'alimentatore
Siccome frequenza di rete e accensione di Arduino sono fenomeni asincroni, il valore misurato è abbastanza casuale per i nostri scopi?

Qui ho ripetuto la lettura di A0 per 10 volte dentro a loop, quindi ripete di continuo le 10 letture di A0

A0: 1023 691 0 0 76 748 1023 484 0 22 
A0: 1023 546 0 3 198 1023 995 143 0 150 
A0: 997 192 0 101 976 1023 217 0 42 728 
A0: 499 0 15 436 1023 749 0 0 48 652 
A0: 579 0 0 121 1023 1019 0 0 22 555 
A0: 668 0 0 70 743 1023 494 0 0 244 
A0: 972 90 0 33 654 1023 579 0 5 132 
A0: 1023 0 0 4 323 1023 890 0 0 0 
A0: 1023 737 0 0 53 698 1023 533 0 16 
A0: 1023 580 0 10 368 1023 830 0 0 23 
A0: 1023 427 0 27 505 1023 716 0 0 38 
A0: 1023 306 0 21 632 1023 587 0 0 142 
A0: 1004 0 0 30 563 1023 671 0 0 39 
A0: 1023 243 0 49 688 1023 545 0 0 178 
A0: 994 129 0 123 1023 1023 0 0 29 535 
A0: 679 0 6 58 746 1023 496 0 5 260 
A0: 968 80 0 48 654 1023 572 0 10 368 
A0: 826 0 0 6 345 1023 867 0 0 12 
A0: 1023 481 0 28 462 1023 761 0 0 28 
A0: 1023 350 0 32 585 1023 639 0 0 98 
A0: 1023 217 0 55 739 1023 480 0 25 441 
A0: 736 0 0 21 632 1023 600 0 0 133

Ad A0 ci ho attaccato in fila 7 cavi dupont da 20cm ciascuno che finiscono sopra una ciabatta, non delle mie, ma di quelle elettriche.

Già si vede l'interferenza della rete che aumenta la variabilità

Però c'è una regolarità
Guarda la prima colonna e la quinta

Se non lo faccio finire sopra la ciabatta ma lo tengo ad un metro di distanza

A0: 899 621 578 817 972 775 535 568 847 878 
A0: 493 698 885 807 580 466 701 888 743 482 
A0: 785 811 609 423 568 774 795 541 431 622 
A0: 649 414 473 715 804 604 400 461 740 755 
A0: 381 612 782 658 444 387 643 783 612 374 
A0: 724 717 478 341 547 759 697 427 371 588 
A0: 564 334 431 692 736 504 335 475 723 695 
A0: 359 614 753 572 357 371 641 728 533 313 
A0: 720 675 406 307 537 734 627 365 359 592 
A0: 495 286 423 685 689 443 300 506 733 648 
A0: 377 615 716 539 315 360 636 694 476 294 
A0: 719 634 381 321 568 726 557 308 367 616 
A0: 432 284 468 669 654 408 303 534 711 601 
A0: 369 632 693 464 287 402 661 628 418 280 
A0: 722 554 328 323 584 686 491 276 367 628

Standardoil:
Però c’è una regolarità
Guarda la prima colonna e la quinta

Si, siccome il tutto è rallentato dalla seriale, presumo si tratti della sinusoide dei 50Hz.
La seriale è a 9600 quindi rallenta parecchio

Ho aumentato la velocità della seriale a 115200 guarda cosa esce rimettendo il finale sopra il cavo della ciabatta :wink:

A0: 1023 1023 1023 1023 1023 1023 1023 1023 1023 1023 
A0: 1023 921 724 494 309 121 0 0 0 0 
A0: 0 0 0 0 0 0 0 0 0 0 
A0: 0 0 0 0 0 0 0 0 0 0 
A0: 0 0 7 0 0 9 14 0 31 0 
A0: 35 16 54 193 403 629 805 1023 1023 1023 
A0: 1023 1023 1023 1023 1023 1023 1023 1023 1023 1023 
A0: 1023 1023 1023 1023 1023 916 704 479 326 146 
A0: 0 0 0 0 0 0 0 0 0 0 
A0: 0 0 0 0 0 0 0 0 0 0 
A0: 0 0 0 0 0 0 0 0 0 0 
A0: 22 18 1 0 31 58 70 208 402 626 
A0: 1023 1023 1023 1023 1023 1023 1023 1023 1023 1023 
A0: 1023 1023 1023 1023 1023 1023 1023 1023 1006 869 
A0: 382 185 0 0 0 0 0 0 0 0 
A0: 0 0 0 0 0 0 0 0 0 0

Satura

e non di poco, contando i tempi sia in positivo che in negativo, visti gli zeri derivanti dalla semionda negativa
però il nano cinese ha resistito :wink:

Beh, è segnale ad alta impedenza, non fa danni
Torno a pensare al trasformatore del router
A bassa impedenza, si può mettere un partitore, non saturerebbe
Oppure usare il tempo che ci mette il tuo filo dal valore che trova a scendere a zero e/o salire a 1023
Quindi misurare la fase della semionda, ma è parimenti asincrona con l'istante di accensione

Hm, che schifezza di valori...

Stasera vedo se mi viene in mente qualcosa facendo anche io qualche prova con UNO, Mega e Nano...

Ho provato con UNO originale e UNO Elego, più o meno gli stessi risultatti del post #1.

La misura la fa l'ATmega, quindi dovrebbe cambiare poco se la scheda è originale o meno, almeno in base alla mia ignoranza :wink:

Comunque, ho provato a fare 3 letture per 3 volte, creando 3 unsignel long e a moltilicarli tra di loro. varianza bassa, il range restituito è sempre attorno al massimo della variabile perchè la probabilità di avere N zeri in testa è tanto più bassa quanti più zeri di fila si devono avere, quindi forse forse con questa tecnica si ha pure meno variabilità della lettura analogica a 10 bit un po' più casuale rispetto al pin fluttuante.
Però, da questo prodotto, ho preso 8 bit nel mezzo e dividendo per 32, (che sono i bit di un long), e tenendo il resto, ho un numero variabile da 0 a 31, questo lo posso usare per crearmi una maschera che azzeri i bit più significativi. In questo modo dovrei poter accorciare in modo random il numero. Non è ancora una distribuzione lineare ma almeno è molto più ampia.
Ho 1 probabilità su 32 di avere un numero binario lungo X bit.
Sofisticando un po' si potrebbe anche arrivare ad una probabilità uguale per i singoli numeri, ma richiede un calcolo più articolato.

Me pare 'na porcheria pure a me ad una seconda lettura :frowning:
Mi rimangio tutto, così attenua l'alcool della mensa che a stomaco pieno ha meno effetti collaterali :wink:

Finito l’effetto dell’alcool, per quel che mi riguarda questo codice:

void setup() {
  Serial.begin(19200);
}

void loop() {
  unsigned long w[6] = {0};
  for(byte i = 0; i < 6; i++) {
    unsigned long x = ((unsigned long)analogRead(A0))<<16;
    unsigned long y = ((unsigned long)analogRead(A0))<<8;
    unsigned long z = ((unsigned long)analogRead(A0));
    w[i] = x + y + z;
  }
  unsigned long rnd = w[0] * w[1] * w[2] * w[3] * w[4] * w[5];
  Serial.println(rnd);
}

potrebbe andare bene.
Ovvio che essendo la analogRead moooolto poco variabile, può generare facilmente lo stesso set di numeri producendo lo stesso numero finale ma da quel che ho visto è sufficientemente raro.
Già con l’antenna per captare disturbi elettromagnetici il problema si riduce quasi del tutto.

Però una cosa strana, sul mio nano cinese, l’ho vista.
Ho provato a variare il pin e con A0, A3 e A7 tutto ok.
Con A1, A2, A4, A5 dopo poche lettura va tutto a zero. Anche A3.
Con A6 va a zero come i precedenti ma ogni tot lettura da un segno di vita.

Invece di variare solo il seed, si potrebbero sfruttare i fili per generare direttamente una sequenza casuale.
Aggiungendo un paio di componenti, potremmo andare a pescare qualcosa nel range delle radio FM.

bella idea, complimenti
siamo a dove eravamo ieri:
senza HW aggiuntivo non possiamo fare nulla, il limite deve essere dato lato HW
per assurdo, se io prendo una sequenza puramemente deterministica, ma la prendo una volta sola, appare casuale
ovvero? ovvero leggo l'ora da un modulo dcf77, che più deterministico di così non si puo' (non è vero, basta prendere una sequenza di zeri...)
MA
SE la leggo una volta sola all'accensione di Arduino, essendo l'istante di accensione slegato dal segnale DCF
la lettura è completamente casuale, specialmente se ho l'accortezza di considerarla solo una sequenza di bit, e se li mischio prima di usarli

Si "torna" al mio thread di parecchio tempo fa, dove volevo costruire un generatore di impulsi casuali per "giocare" con l'oscilloscopio.
In effetti senza un minimo di hardware esterno si combina poco.