Gen. náhod. čísel

[css]

Dobré poledne, prosím pěkně o pošťouchnutí, jak vyřešit toto:

Zařízení s CPU, kde obsluha tu a tam stiskne tlačítko, CPU si vygeneruje náhodné číslo 0 nebo 1 a podle toho program pokračuje jednou ze dvou cest. Nechal bych v CPU běžet čítač a po stisku testoval jeden bit z jeho registru, to není problém. Problém mám s tím, že je požadavek, aby jedna varianta padala zhruba 7x častěji, než druhá, aby ze 100 pokusů program cca 15-20x provedl jednu operaci, a 80-85x jinou. Zdůrazňuji, že se nejedná o žádný herní nebo herně-hazardní automat

Prosím o obecný postup, jak tohoto docílit, do instrukcí už si to naprogramuji sám. Díky a pěkný den. Petr

[Zaky]

Dvě části zadání si lehce odporují, každopádně pokud čítač necháš běžet dostatečně rychle cyklicky od 0 do 99 a budeš testovat, jestli při stisku tlačítka byla hodnota menší, či větší, než nějakých těch 80, žádanou pravděpodobnost tím docílíš.

[css]

Zaky: Super, díky, triviální řešení, přesně tak jsem si to představoval. Ještě jednou díky a pěkný den

[Cowley]

Nahode se prece musi jit naproti

[ross4435897]

kvalitni reseni, skoro jako od RSA-CA s doporucenim NSA

[ZdenekHQ]

Možná už chápu ty gamblery, co kdysi seděli v hospodě u piva a koukali na proherní automat, jak tam jiní hází peníze, pak občas vstali a s desetikačkou vysypali 300Kč.

Asi tam byl podobnej "generátor".

[Zaky]

Chtěl bych vidět, jak s takovýmto algoritmem dokážeš vytipovat, kdy padne ta menší pravděpodobnost, když čítač napočítá do té 100 třeba za 1 ms, tak je okamžik stisku tlačítka v lidském vnímání času tak náhodný, jak jen může být. Každopádně nemám patent na rozum a pokud někdo uvede sofistikovanější řešení, rád se nechám poučit, programováním jsem byl okolnostmi donucen se začít zabývat asi tak 3 roky nazpět a nikdy jsem tento obor nestudoval.

[ZdenekHQ]

Pokud bude ten čítač běžet s periodou 1ms, tak stejné číslo vygeneruje pravidelně každou X × 1ms včetně násobků (X je např. 100). Při možnosti 80/20 je při opakovaném stisku docela slušná šance trefit správnou volbu.

Při náhodném jednorázovém stisku to samozřejmě neplatí.

[Zaky]

Pro opakovaný stisk by se to samozřejmě dalo modifikovat, aby byl interval plovoucí, nebo třeba aby se bralo jako platné vždy číslo končící na 8 a 9, dá se toho vymyslet fůra, ale stejně bych se nebál, že se někdo dokáže synchronizovat na interval 1 ms, je to pro člověka přiliš rychlé. Soft pro proherní automaty řešit nehodlám, pravidel je pro to jistě dost a tazatel se ani na žádnou takovou věc neptal. Za to se našlo dost zpochybňovačů, ale žádná relevantní odpověď.

[ZdenekHQ]

Neber si to prosím osobně, tohle je čistě technická debata.

Existují třeba kvazicyklické kódy, které to trošku rozhodí, aby to nebylo tak jednoduchý. Používají se třeba pro výpočet CRC u průmyslové komunikace MODBUS atd. Jde o to, že ta smyčka není lineární, ale pseudonáhodná. Je to vlastně jen pár exorů při každém kroku....

Viz třeba http://www.lammertbies.nl/comm/info/crc ... ation.html

[Zaky]

Samozřejmě nic osobně neberu, že je generování čehokoli pseudonáhodného deterministickým systémem vždy velký problém je jasné, naštěstí je zrovna v případě mačkání tlačítka ta náhodnost velmi dobře dána právě časem stisku a tudíž se toho zhusta využívá. Montovat do algoritmu jednočipu sofistikované řešení je v tomto případě zbytečné, v případě potřeby jistě Google napoví. Co se týče softwaru pro proherní automaty, naopak Google nenapoví celkem nic, protože tato problematika je utajená jak hrad v Karpatech. Zajímavé je, že jsem před časem zkoušel hledat nějaké informace o přenosu povelů s plovoucím kódem, tak jak to dělají třeba centrály v autech a informace o této problematice se také z Googlu nějak nesypaly, tak nezbylo, než implementovat vlastní řešení.

[ZdenekHQ]

Tak ono třeba stačí prohodit pár bitů v tom čítači a pak teprve porovnávat 80/20. Ale ta perioda se tím nezmění.

Psát do Google algoritmus plovoucího kódu se rovná sebevraždě výrobce.

[Zaky]

Neočekával bych nějaký konkrétní detailní popis, to by se rovnalo návodu výrobce, jak otevřít jeho zámek bez klíče, to je jasné, ale na druhou stranu bych si dovedl představit, že by nějaký edukativní text popisující obecné principy mohl existovat, leč nenašel jsem. Nabízí se totiž základní otázka, přenos je jednosměrný a je třeba umět odlišit na straně přijímače kódy minulé a budoucí i přes to, že si uživatel může vysílat o sto pryč mimo dosah přijímače. Z analýzy problému vyjdou zajímavé skutečnosti naznačující, kde jsou slabiny systému. Takže pokud někdo o nějakém takovém článku ví, rád bych si ho přečetl.

[ZdenekHQ]

Pravda je, že to musí umět zachytit i neplatné kódy v určitém rozsahu. Ale ten generující polynom, t.j. ta pseudonáhodná smyčka je výrobcem volitelná.

[mtajovsky]

Samozřejmě nic osobně neberu, že je generování čehokoli pseudonáhodného deterministickým systémem vždy velký problém je jasné,

Není to tak strašné. V době, kdy ješte nebyly mikrporocesory tak rozšířené, nebo se jim ještě nevěřilo, se používaly pseudonáhodné generátory na šifrování při přenosu dat. Na obou stránch běží kongruentní generátory založené třeba na 64 bitových posuvných registrech s kruhovými vazbami na členy XOR tak, jak to vidíme u schémat různých CRC. Přepínáním vazeb a různým počátečním nastavením se generují různé cykly s délkou 2^64 (alespoň se tomu věří ), čímž se generuje pseudonáhodná posloupnost sloužící jako vložené heslo pro Vernanovu šifru.