Fórumok

Mac Xcode C++ segítség! Valódi véletlenszám-generátor

ismeretlen.exe

Eredeti plakát
2007. szeptember 22
Valahol a Földön
  • 2007. december 13
Sup, írok egy C++ programot, amely a DNS 4 komponensét (A, G, T és C) véletlen sorrendben 1 000 000-szer adja ki, hogy megismételje, hogyan nézne ki egyetlen sejt DNS-e. Íme a kódom:

{
//KÖSZVÉNY
KÖSZVÉNY:
int randnum;
for(hosszú double i = 1,0; i<1000000.0; i++)
{
srand((unsigned)time(0));
for(int index=0; index<1; index++)
randnum = (rand ()% 1000) +1;
if (randnum<=250)
költség<< 'A';
else if (randnum> 250 && randnum<= 500)
költség<< 'C';
else if (randnum> 500 && randnum<=750)
költség<< 'T';
más
költség<< 'G';
}
}

Jól lefordítja és mindent, de a kimenet így néz ki:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAACCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
CCCCCCCCCCCCCCCCCCCCCCCCCGGGGGGGGGGGGGGGGGGGGGGGGG
GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG
GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG
GGGGGGGGGGGGGGGGGGGTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT..................................stb.

Nyilvánvalóan a véletlenszám-generátor nagyon... úúúúú... nem véletlen? Nos, ha valaki tud egy nagyon véletlenszám-generátort, vagy tudja, hogyan tudom megváltoztatni a kódomat ennek érdekében, kérem, mondja meg!

gnasher729

Felfüggesztett
2005. november 25


  • 2007. december 13
Mi a baj a srand ()-nak szóló hívásoddal?

ChrisBrightwell

2004. április 5
Huntsville, AL
  • 2007. december 13
Helyezze a srand() hívását a megjelenésén kívülre. Csak egyszer kell magolni az RNG-t.

Itt van azonban a probléma: Ez a ciklus másodperc ezredmásodpercben többször is végrehajtódik. Ha minden alkalommal újraindítja az RNG-t a cikluson keresztül, akkor minden egyes ezredmásodperc alatt többször is ugyanazt az értéket kapja.

ismeretlen.exe

Eredeti plakát
2007. szeptember 22
Valahol a Földön
  • 2007. december 13
ChrisBrightwell azt mondta: Helyezze át a hívást a srand()-ra a megjelenésén kívül. Csak egyszer kell magolni az RNG-t.

Itt van azonban a probléma: Ez a ciklus másodperc ezredmásodpercben többször is végrehajtódik. Ha minden alkalommal újraindítja az RNG-t a cikluson keresztül, akkor minden egyes ezredmásodperc alatt többször is ugyanazt az értéket kapja.

Mit értesz azon, hogy 'kinézeteden kívül'... hurokra gondolsz?

ismeretlen.exe

Eredeti plakát
2007. szeptember 22
Valahol a Földön
  • 2007. december 13
A srand() cikluson kívülre helyezése sikerült! Nagyon köszönöm!

ShosMeister

2007. december 28
  • 2007. december 30
Ha keresést végez az interneten, talál néhány online forrást, amelyek valódi véletlen számokat szolgáltatnak, ha valóban szüksége van rájuk. Ezek egy része ingyenes (csak bejelentkezési fiók létrehozása szükséges), mások pedig fizetősek. Van néhány, amely megmutatja, hogyan hozhat létre saját hardveres véletlenszám-generátort.

Az általam végzett összes kutatás kulcspontja az, hogy valódi véletlen számokat nem lehet előállítani valamilyen hardveres bemenet (például videó, hang stb.) nélkül, ahogyan azt az online források jelzik. Még a PokerStars is egy hardveres véletlenszám-rendszerhez lépett, amihez mindent felhasznált, amit csak lehetett, beleértve az adott asztalnál ülő felhasználók egértevékenységét is!

Mint láthatja (talán), ez egy olyan téma, amely nagyon érdekelt az évek során, mióta az első olyan számítógépet használtam, amelyen valódi (nem algoritmikus) véletlenszám-generátort használtam - az Atari 800-am. az órafrekvencia alsó 4 vagy 5 számjegyét használta (a könyveket teljesen biztosra kell venni, de ez közel van). Ezután visszaküldte ezt a programnak, balra tolva egy 0 és 1 közötti számra.

Az évek során megpróbáltam ezt megismételni, de úgy tűnik, hogy a legtöbb modern számítógép (a rendelkezésre álló nyelveken) nem fér hozzá ezekhez az adatokhoz. Tehát elkészítettem a sajátomat a legnagyobb felbontású elérhető időzítővel (például a nanoTime). Ha ezt figyelembe veszi, és megfelelően eltolja, elég lenyűgöző valódi véletlenszámokat kaphat. Ezt 10000-szer futtattam le és a beépített rand függvényeket 10000-szer, és összehasonlítottam a statisztikai eredményeket, és ezek viszonylag azonosak voltak.

Egy másik gondolatom az volt, hogy vessek egy pillantást a hálózati vagy merevlemez-tevékenységre, és nézzem meg, van-e valami, amivel véletlenszerű számot rögzíthetek. Valamint a véletlenszámom kombinációját használva, majd bemegyek valahova a memóriába (a véletlen szám alapján), és lekérem onnan az adatokat (vagy akár egy képernyőbitet/byte-ot).

Csak néhány gondolat arra az esetre, ha valóban valódi véletlen számokra van szüksége/szüksége van.

Gelfin

2001. szeptember 18
Denver, CO
  • 2007. december 30
Az unknown.exe azt mondta: Írok egy C++ programot, amely a DNS 4 komponensét (A, G, T és C) véletlenszerű sorrendben 1 000 000-szer adja ki annak érdekében, hogy megismételje, hogyan nézne ki egyetlen sejt DNS-e.

Helytelenül használod a rand-ot azzal, hogy ismételten újraolvasod, ahogy ChrisBrightwell leírta, de ez egy nagyon rossz példa a PRNG-re általában, és azt tanácsoljuk, hogy ne szokd meg a használatát.

Két jobb alternatíva áll rendelkezésére: Ha aggódik a hordozhatóság miatt (mondjuk a Windows felé), nézze meg a dokumentációban a „random” szót a „rand” helyett. Ha ragaszkodik a Machez (és bizonyos más Unixokhoz), akkor érdemes lehet egyszerűen megnyitni és beolvasni a bájtokat a /dev/random fájlból. A rendszer fenntartja a saját entrópiakészletét a /dev/random számára, így általában nem kell beágyaznia, és elég véletlenszerű bármihez, kivéve a komoly titkosítást.

Mellesleg, hacsak nem csupán a DNS-szerűség homályos benyomását kívánja kelteni nyomtatott formában, egy millió bázisból álló véletlenszerű választék határozottan nem hogy nézne ki egyetlen sejt DNS-e.

ShosMeister azt mondta: Mint láthatja (talán), ez egy olyan téma, amely nagyon érdekelt engem az évek során, mióta az első olyan számítógépet használtam, amelyen valódi (nem algoritmikus) véletlenszám-generátort - az Atari 800-at - használtam. Amit csinált, az az órafrekvencia alsó 4 vagy 5 számjegyét használta (a könyveknek meg kell győződni róla, de ez közel van). Ezután visszaküldte ezt a programnak, balra tolva egy 0 és 1 közötti számra.

Az évek során megpróbáltam ezt megismételni, de úgy tűnik, hogy a legtöbb modern számítógép (a rendelkezésre álló nyelveken) nem fér hozzá ezekhez az adatokhoz. Tehát elkészítettem a sajátomat a legnagyobb felbontású elérhető időzítővel (például a nanoTime). Ha ezt figyelembe veszi, és megfelelően eltolja, elég lenyűgöző valódi véletlenszámokat kaphat. Ezt 10000-szer futtattam le és a beépített rand függvényeket 10000-szer, és összehasonlítottam a statisztikai eredményeket, és ezek viszonylag azonosak voltak.

A nagy felbontású időzítő könnyen elérhető Mac OS X rendszerben. Vegye fel és hívja meg a mach_absolute_time() függvényt, hogy megkapja a 64 bites CPU órajelét. Más platformok is hasonló eszközökkel rendelkeznek ugyanennek a megvalósítására.

Ez azt jelenti, hogy gondolkodj ezen egy percre. Ha a jó véletlenszerűséget olcsón meg lehet szerezni, miért találta volna fel bárki is az algoritmikus PRNG-ket? Az eloszlás hasonlónak tűnhet bizonyos típusú elemzéseknél, de távol áll a véletlentől. C

Chris A.

2006. január 5
Redondo Beach, Kalifornia
  • 2007. december 30
ShosMeister azt mondta: Amint láthatja (talán), ez egy olyan téma, amely nagyon érdekelt az évek során az első számítógépem óta

Olvastad Knuth 2. kötetét, „Félnumerikus algoritmusok”? A legtöbbünk számára Knuth a végleges forrás ezzel kapcsolatban. Az egyik téma a generált számok statisztikája. Valóban egyenletesen oszlanak el a tartományban? Az elosztás a legtöbb ad-hoc technika szokásos problémája. NAK NEK

kpua

2006. július 25
  • 2007. december 31
Ezenkívül a rand() nem jó választás az eredmény módosításakor. A megfelelőbb random() függvény man oldala szerint a rand() függvény alsó bitjei ciklikus mintázatban mennek, ami kizárja a jó véletlenszerű eredményeket. A random() biztosítja, hogy minden egymást követő szám minden bitje véletlenszerű legyen. A /dev/random használata szintén jó javaslat volt, de a random() általában elérhetőbb, praktikusabb és hordozhatóbb.

Radírfej

2005. november 3
Egyesült Királyság
  • 2007. december 31
Az ember véletlenszerűsége szerint az arc4random kriptográfiai erősségű véletlenszámokat ad (a részletekért lásd: man arc4random).

ShosMeister

2007. december 28
  • 2007. december 31
Gelfin azt mondta: Ez azt mondta, gondoljon ezen egy percre. Ha a jó véletlenszerűséget olcsón meg lehet szerezni, miért találta volna fel bárki is az algoritmikus PRNG-ket? Az eloszlás hasonlónak tűnhet bizonyos típusú elemzéseknél, de távol áll a véletlentől.

Évek óta azon tűnődöm, és az egyetlen ok, amivel elő tudok jutni, az az, hogy az idő előrehaladtával az emberek rájöttek, hogy nincs szükség másra, mint pszeudo véletlen számokra. Emellett sokan elfelejtik, hogy gyakran a legegyszerűbb megoldás a legjobb.

Személyes érzésem az, hogy mivel a hardver olyan gyorsan változott az elmúlt 15 év alatt, a programozók nem tudtak lépést tartani. Minden idejüket azzal töltik, hogy lépést tartanak a hardverrel, és nincs sok idejük az 1980-as években létező valódi innovációra. Csak az én véleményem.

Gelfin

2001. szeptember 18
Denver, CO
  • 2008. január 1
ShosMeister azt mondta: Évek óta azon tűnődöm, és az egyetlen ok, amivel elő tudok jönni, az az, hogy az idő előrehaladtával az emberek rájöttek, hogy nincs szükség másra, mint pszeudo véletlen számokra. Emellett sokan elfelejtik, hogy gyakran a legegyszerűbb megoldás a legjobb.

Ez egy jó csak úgy történet, de egyszerűen nem mosódik. Az Atari 800-as megoldásba vetett hited itt szinte babonásnak tűnik. Azt próbálom elmondani, hogy ez félrevezetett, és nem jó befektetés az idejében, ha megpróbál egy nagyon rossz megoldást lemásolni.

Az algoritmikus PRNG-k, amelyek elegendőek a kriptográfiához, számítási szempontból nagyon drágák, összehasonlítva az óraszámláló magasabb rendű bitjeinek elfedésével. Amit korábban retorikusan kérdeztem, most igenlően kijelentem: Soha senki nem alkotott volna ilyen fantasztikusan drágát, amikor elég egy óraszámlálóra lesni. A probléma az, hogy az óraszámlálóra kukucskál szokás elegendő, ha valami többet vár el, mint a játékokhoz szükséges gyengén félig véletlenszerű viselkedést. Az Atari csak ennyiért lőtt.

Személyes érzésem az, hogy mivel a hardver olyan gyorsan változott az elmúlt 15 év alatt, a programozók nem tudtak lépést tartani. Minden idejüket azzal töltik, hogy lépést tartanak a hardverrel, és nincs sok idejük az 1980-as években létező valódi innovációra. Csak az én véleményem.

Azta. Biztosan ilyen érzés orvosnak lenni, aki az „alternatív gyógyászat” híveit hallgatja. A számítógép-ipar működéséről alkotott elképzelései enyhén szólva is érdekesek.

Nézze, utálom nem tisztelni egy ember első számítógépét, de a POKEY chipben nincs varázslat. A teljes terv 14 kézzel rajzolt sematikus oldalon él. A rá vonatkozó szabadalmak közel egy évtizede lejártak. A szükséges tranzisztorok bármely modern CPU-hoz hozzáadhatók nulla effektív költséggel. És lennének, ha bármit megtennének, amit érdemes megtenniük. A POKEY RNG nagyjából ugyanúgy alkalmas a feladatára, mint a POKEY hanggenerátor hangvisszaadási feladatra. 1979-ben ez volt a legolcsóbb módja annak, hogy véletlenszerűnek tűnő viselkedést vigyenek be a játékgépekbe. Inicializálódik egy jól meghatározott állapotba. Számláló alapú, tehát minél gyakrabban hívjuk, annál kiszámíthatóbbá válik még egy hétköznapi szemlélő számára is, de az elszánt támadó meg tudja számolni az órákat, és pontosan tudja, hogy a művelet bármely pontján mekkora értéket kapunk belőle.

Ami ott van, az nem „igazi” véletlenszám-generátor. Egy pszeudovéletlen számgenerátorod van, olyan triviális, hogy azt hiszed, nem ugyanaz az állat.

A modern PRNG-kben az algoritmus tetszőleges értékkel van beágyazva. A programozók gyakran az aktuális időt használják magként, de ez nem kötelező. A POKEY PRNG-ben a 'seed' egy rögzített érték, amely a chip inicializálásakor betöltődik a regiszterbe.

A POKEY 'algoritmusa' a következő: (véletlen = (mag+órák_eltelt)&0xff). Számodra úgy tűnik, hogy nem algoritmikus, mert gyakorlatilag nincs megvizsgálható algoritmus, és mert hardverben van implementálva. Ezzel szemben gyakori, hogy a legmodernebb PRNG-k kezdetben erős titkosításon alapulnak. Az Ön által megadott seed egy belső puffer titkosításához használt kulcs levezetésére szolgál. A rendszer véletlenszerű bájtokat olvas ki ebből a titkosított pufferből, és amikor a pufferben lévő összes bájt visszakerült a fogyasztókhoz, csak újra titkosítja a puffert, hogy többet kapjon. Így az RNG ereje közvetlenül kapcsolódik a kriptográfiai algoritmus erősségéhez.

A lényeg: az „igazi” véletlen az ellenkezője annak, amit a számítógépek csinálnak, és ezt meggyőzően meghamisítani nehezebb, mint amilyennek látszik. A POKEY RNG nem egy csipetnyi romantikus szilícium-bölcsesség, amit mi, modern, rejtőzködő shlubok elfelejtettünk. A POKEY-t könnyen emulálhatnánk; egyszerűen nem jó ötlet.

ShosMeister

2007. december 28
  • 2008. január 6
Sajnálom, hogy ennyire felzaklatlak ezzel az egészgel, bár egy kicsit nem értek egyet. Nem hiszem, hogy mi (emberekként) mindig megtaláljuk a legegyszerűbb megoldást. Gyakran találunk olyan megoldásokat, amelyek működnek, és remekül működnek, de ez nem mindig jelenti azt, hogy ez a legjobb/legegyszerűbb/legkönnyebb/leghatékonyabb. Bár mindegy.

Igazad van, ha csak az órára nézel. Eléggé kiszámítható. Ha nem tévedek, nem magát az órát nézték, hanem a folyamatosan változó és kicsit kevésbé kiszámítható frekvenciát. Azonban, ahogy említetted, ez nagyszerű olyan gépekhez, amelyek 1,8 MHz-en futnak, és elsősorban játékgépek. Ez azonban nem jelenti azt, hogy az ötlet ostoba, és nem indokolja a vizsgálatot a modern rendszerek esetében. Ha ez olyasvalami, amely ugyanolyan véletlenszerű eloszlást biztosít, mint a rendelkezésre álló PRNG, anélkül, hogy egy algoritmus pontosan megjósolható lenne, akkor miért ne.

Nem vagyok orvos (de tegnap este a Holiday Inn Expressben szálltam meg). Komolyan, úgy gondolom, hogy a 70-es és 80-as években létező innováció lényegesen több volt, mint manapság. A szoftvermérnökök gyakran terveztek és programoztak olyan dolgokat, amelyekről a hardvermérnökök azt mondták, hogy nem képesek – mégis megtörtént. Az újítások egy része ma olyan dolgokhoz vezetett, mint például a különálló grafikus kártyák, amelyek egykor csak szoftver-illesztőprogramok voltak. Ez nem azt jelenti, hogy nincs még kreativitás és innováció, csak azt gondolom, hogy a hardver gyors fejlődése miatt már kevesebb.

Vegyünk példának a tévét. Mielőtt létezett, valakinek meg kellett teremtenie az ötletet. Nos, nem azt akarom mondani, hogy az azóta történt változások nem fantasztikusak (love my HD), de bizonyos mértékig csak továbbfejlesztései az eredeti ötletnek. Ez nem jelenti azt, hogy akár az eredeti, akár a változtatások kevésbé lenyűgözőek, csak más.

Nem éreztem tiszteletlenséget, de volt benne egy kis varázslat, különben miért segített a videojátékok megszületésében. Nagyon egyedi ötlet volt külön grafikus vezérlőt kínálni – nem azt, hogy ők voltak az elsők vagy az egyetlenek, csak népszerűbbé tette. És 20 év múlva a béna 32 bites CPU-inkról fogunk beszélni, amelyek csak 2 GHz-en futnak (nagyjából). A technológia mindig változik és fejlődik. Ez nem zárja ki a hatását. Hol lennénk, ha az első tranzisztoros áramkört nem tervezték meg? Ez is béna? Azt hiszem, nem.

Még egyszer, nem próbáltam megemelni a vérnyomását, és elnézést, ha megtettem.