satunnaislukualgoritmi

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Tiedän, että esim. suurien alkulukujen avulla voidaan generoida melko hyvin "satunnaisia" lukuja.. mietin, että miten hyvä algoritmi tämä olisi (javaa):

[code:115l6leu]public class Random {

private double rnda, rndb, rndc;
private int kiek;

public Random() {
rnda = 0.3123231;
rndb = 0.1234556;
rndc = 0.9876594;
kiek = 1;
}
public Random(double seed) {
seed = Math.floor(seed*Math.PI)+Math.E-2;

rnda = round(Math.sqrt(seed*10+Math.PI*Math.E));
rndb = round(Math.PI*10 + 3*Math.pow(rnda, Math.E+1/(seed+1)));
rndc = round(seed*(2+rndb*(1+rnda)));
kiek = 1;

for (int i = 0; i < 10; i++)
nextRnd();
}
public int kokRnd(int a, int b) {
return a + ((int) Math.round(this.nextRnd()*100) % (b-a+1));
}
public double round(double a) {
if (a < 0)
a = 0.4999;
a -= Math.floor(a);
return Math.round(a * 10000000.0) / 10000000.0;
}
public double round2(double a) {
return Math.round(a * 100000.0) / 100000.0;
}
public double nextRnd() {
rnda = rndb;
rndb = rndc;

rndc = round(Math.sqrt(rnda+2)+Math.pow(Math.PI*rndb+2+round(kiek/10), Math.E-1)+Math.PI);
kiek++;
if (kiek == 1017)
kiek = 1;
return round2(rnda);
}
}[/code:115l6leu]

Aika paljon on pitänyt kikkailla piillä ja e:llä =P

http://en.wikipedia.org/wiki/Cryptographically_secure_pseudo-random_numb...

Every CSPRNG should satisfy the "next-bit test". The next-bit test is as follows: Given the first k bits of a random sequence, there is no polynomial-time algorithm that can predict the (k+1)th bit with probability of success higher than 50%. Andrew Yao proved in 1982 that a generator passing the next-bit test will pass all other polynomial-time statistical tests for randomness.



Hmm... tuo taitaa toteutua? Uskoisin, että algoritmi on tarpeeksi herkkä.. vai onko? En oikein osaa tarkistaa tuota..

Every CSPRNG should withstand 'state compromise extensions'. In the event that part or all of its state has been revealed (or guessed correctly), it should be impossible to reconstruct the stream of random numbers prior to the revelation. Additionally, if there is an entropy input while running, it should be infeasible to use knowledge of the input's state to predict future conditions of the CSPRNG state.

Hmm.. tuolla varmaan tarkoitetaan, että tunnetaan muuttujien rnda, rndb, rndc arvot tarkalleen (ei sillä tarkkuudella, millä ne tulostuvat ulospäin)? Siinä tapakusessa tuo ei enää kelpaisi. No olisihan se ollut vähän liian yksinkertaista =P

Siitäkään ei oikein ole varmuutta, että miten tuo käyttäytyy, kun ollaan generoitu esim. miljardi lukua.

Saas nähdä, että tuleeko tästä järkevää topickia.

Kommentit (9)

Vierailija

Käytin ohjelmaa
http://www.fourmilab.ch/random/
seuraavan tuloksen tekemiseen

EDIT: Ajoin javasoftaa siis parametrein (char)kokRnd(0,255) että sain sieltä ulos tasaisen bittibirran.

javasofta
Entropy = 6.653268 bits per byte.

Optimum compression would reduce the size
of this 1000000 byte file by 16 percent.

Chi square distribution for 1000000 samples is 1549436.79, and randomly
would exceed this value 0.01 percent of the times.

Arithmetic mean value of data bytes is 49.2746 (127.5 = random).
Monte Carlo value for Pi is 4.000000000 (error 27.32 percent).
Serial correlation coefficient is 0.021101 (totally uncorrelated = 0.0).




Eli aika pseudorandomilta näyttää verrattuna siihen mitä /dev/urandom antaa ulos

/dev/urandom
Entropy = 7.999992 bits per byte.

Optimum compression would reduce the size
of this 23183360 byte file by 0 percent.

Chi square distribution for 23183360 samples is 265.70, and randomly
would exceed this value 50.00 percent of the times.

Arithmetic mean value of data bytes is 127.5113 (127.5 = random).
Monte Carlo value for Pi is 3.141013480 (error 0.02 percent).
Serial correlation coefficient is 0.000150 (totally uncorrelated = 0.0).

Mutta mielenkiintoinen aihe kyllä. Täytyy katsoa mitä alkeissoluautomaatti säännöllä 30 antaa tuloksia samalla ohjelmalla.

Vierailija

Uuh heti joutui kovemman tason testiin.. tuo monte carlo olikin aika jännä tapa testata tuota satunnaisuutta. :O Pitää pitää mielessä vastaisuuden varalta..

Eihän se ole hyvä juttu, ettei keskiarvo ollut puolessa välissä, muttei se välttämättä tarkoita, että tuo olisi jotenkin paremmin ennustettavissa Tai onhan sillä hieman suurempi todennäköisyys päätyä sinne lähemmäs nollaa, mutta kuitenkin...

Alunperin "kehitin tuon" (käytännössä paljoakaan miettimättä), kun piti saada randomeja siten, että tietyllä seedillä lähtee varmasti tulemaan samoja arvoja (ettei pyöristyksistä tule ongelmaa). Olisi tuohon varmaan netistä löytynyt valmiiksi fiksumpiakin koodeja, mutta ei tuo ole mitenkään turvallisuuden kannalta tärkeässä tehtävässä.

wikipediasta tuli vastaan tällainen:

x_(n+1) = (x_n)^2 mod M, missä M on kahden suuren alkuluvun (p ja q) tulo. Tuosta voi sitten tarkastella vaikka luvun parittomuutta jne, ja siten muodostaa isompia lukuja. Lisäksi oli joku muu ehto, ettei lähtenyt liian nopeasti looppaamaan.. en muista sitä ulkoa (joku mod operaatio mahd. lähelle yhtä tai kakkosta).

Vierailija

Keskiarvo olisi hyvä olla puolessa välissä. Se kuvastaa lähinnä sitä että onko siellä minkäänlaista biasta. Tuo javageneraattori tekee paljon enemmän nollia kuin ykkösiä. Joten jos lyö vetoa (tupla tai kuitti) ja veikkaa nollaa niin tienaa. Täten se ei ole hirveän randomia.

Tehokkain testi noista on ehkä tuo Chi square joka on äärimmäisen herkkä juuri pseudorandomille datalle. Mikäli se on yli 99 tai alle 1% niin silloin data on lähes täydellä varmuudella pseudorandomia. Esim pakatut tiedostot saavat tämänlaisia tuloksia. Niiden entropia on korkea mutta satunnaisuudesta ovat kaukana.

Syy miksi algoritmisi ei ole randomdataa on se, että siinä vaan heitetään normi laskutoimituksia peräjälkeen jotta saadaan tarpeeksi erilaisia lukuja. Ja desimaalit saadaan näyttämään sottaisilta pulttaamalla pii sinne sisään.

Kannattaa kokeilla tuota wikipedian kikkaa. Tai sitten jotain mersenne twisteriä tms.

Vierailija

Ehh...

[code:3e93exet] public int kokRnd(int a, int b) {
return a + ((int) Math.round(this.nextRnd()*100) % (b-a+1));
} [/code:3e93exet]

Eihän tuo toimi oikein järkevästi.. Olin näemmä käyttänyt ainoastaan tuota nextRnd() metodia, jolloin tuon kokRnd metodin järjettömyys ei oikein tullut ilmi.

[code:3e93exet] public int kokRnd(int a, int b) {
return a + ((int) Math.round(this.nextRnd()*(b-a)));
}[/code:3e93exet]

Tuo voisi olla vähän fiksumpi Kokeilen silti tehdä kaikkiaan vähän fiksumman algoritmin..

Vierailija

En tiedä missä vaiheessa ohjelmaasi tarvitset tuota randomia, mutta voisit kokeilla seuraavaa.

Mittaa aika kahden käyttäjän tekemän klikkauksen välissä jossain ohjelman vaiheessa vaikka sekunnin miljoonasosien tarkkuudella. Nappaat tästä luvusta pari kolme numeroa jostain kohdasta ja käytät tätä taas poimiaksesi seedin aina uudelleen esim piin desimaalien joukosta.

Tässä random tulee siitä, että koskaan ihmisen tekemän kahden klikkauksen välinen aika ei ole sama.

Esim. aika on 23,123456789 sec. Poimitaan sieltä esim. 7-9 desimaali eli tässä tapauksessa luku 789, tämän jälkeen nappaat piistä desimaaleja seuraavasti:

1. 1 * 789
2. 2 * 789
3. 3 * 789
etc...

Noista kohdin nappaat aina muutaman desimaalin ja käytät sitä uutena seedinä. Kun piistä desimaalit loppuvat siirryt vaikka Neperin lukuun ja aloitat alusta

En tiedä toimiiko suuressa mittakaavassa, olen tuota joskus itse käyttänyt ja minulle se silloin riitti. Joku varmaan testaa.

Vierailija

Alunperin tein tuon muistaakseni php:lle, kun sessioon tarvitsi sitten tallentaa vain seedi, niin se näytti samat randomit kuvat.

Hmm.. testailin tuota ent.exe:ä, antoi vähän outoja tuloksia.

[code:vn124biu]
Random gen = new Random();
double max = Math.pow(10, 6);
for (int i = 0; i < max; i++)
System.out.print((char)(gen.nextInt(255)));[/code:vn124biu]

Tuo Random on siis java.util.Random.. tuolla tulee ? merkille (int 63) älyttömän suuri frekvenssi, verrattuna muihin lukuihin :S Mistä tämä johtuu?

testasin siis "ent -c koe.dat" komennolla. yleensä frekvenssit ovat noin 4000 luokkaa, mutta kysymysmerkkejä ilmestyi 12000. Jotain mätää...

edit: freqvenssi => frekvenssi =P

Vierailija

Hae radonsäteilyn lähde. Aseta mittari siihen ja tietokoneeseen. Ota mittaustuloksesta rnd siemenluku. Laavalamppujen virtauksesta saa myös aika hyvän siemenluvun.

Vierailija

No voihan.

Tein tuon saman testin. Tosiaan ? merkkejä on enemmän. Ja huomannet ettei merkkejä yli numeron 127 ole ollenkaan. Testasin niin java puskee kaikki liian suuret arvot ulos merkkinä 63. Tämä selittäää myös sen miksi keskiarvo on niin matala. Näyttää siltä että javan char on signed. Eipä tosin yllätä, kieli kun on mitä on.

Tästä syystä tulostus pitää hoitaa System.out.write metodilla mikä puskee raa-an tavun ulos. Ei tarvitse edes muuttaa charriksi.

Ajoin testin javan omalle randomille.

Entropy = 7.994165 bits per byte.

Optimum compression would reduce the size
of this 999950 byte file by 0 percent.

Chi square distribution for 999950 samples is 4184.20, and randomly
would exceed this value 0.01 percent of the times.

Arithmetic mean value of data bytes is 126.9838 (127.5 = random).
Monte Carlo value for Pi is 3.164708565 (error 0.74 percent).
Serial correlation coefficient is 0.000552 (totally uncorrelated = 0.0).




Ihan ok. Paitsi Chi square paljastaa heti että kyseessä on pseudorandomia dataa.

Nyt sinun algoritmisi (paikkasin siihen sen muokkauksesi) uudelleenajo.

Entropy = 7.997506 bits per byte.

Optimum compression would reduce the size
of this 9999915 byte file by 0 percent.

Chi square distribution for 9999915 samples is 30533.90, and randomly
would exceed this value 0.01 percent of the times.

Arithmetic mean value of data bytes is 125.6056 (127.5 = random).
Monte Carlo value for Pi is 3.185192830 (error 1.39 percent).
Serial correlation coefficient is 0.020819 (totally uncorrelated = 0.0).

Jees noin keskiarvot menivät kuntoon. Chi square huutaa edelleen leipää mikä on pseudorandomeilta odotettavissakin. Mutta nyt vaikuttaisi olevan ihan ok pseudorandomigenis.

Uusimmat

Suosituimmat