[C++ Random]

[Verwijderd]

Hallo,

Ik heb een probleempje om enkele random getallen te genereren tussen 0 en 10.
In normale ansi C++ kun je dit gebruiken:

C++:

#include <ctime>    // For time()
#include <cstdlib>  // For srand() and rand()
    . . .
    srand(time(0));  // Initialize random number generator.
    . . .
    r = (rand() % 10) ;

nu is het zo dit ik in mijn compiler (embedded systeem) geen time kan ophalen.
Ik kan maar geen manier vinden om random nummers aan te maken ..

De nummer zijn idd random, maar enkel 1 keer, doordat ik geen wijzigende srand kan gebruiken.

Bestaat daar een oplossing voor?

Bedankt!

[Verwijderd]

probeer eens NULL als param aan srand() te voederen..

[RobLemmens]

Heb je misschien ruis op een of andere input? of een input die continue wijzigende data binnenkrijgt? Dan zou je daarvan een seed kunnen genereren.

[Verwijderd]

Verwijderd schreef op donderdag 23 oktober 2008 @ 15:15:
probeer eens NULL als param aan srand() te voederen..

NULL geeft mij altijd dezelfde getallen ..

[Refro]

Wat ik zowieso vreemd vindt is dat je C++ draait op een systeem / cpu zonder rtc. Meestal hangt er in de embedded wereld een iets zwaardere cpu achter c++ programma's en heb je ook direct een RTC die je kan benaderen.

De enige andere optie die je hebt is ergens anders ruis vandaan toveren. Hier bij kan je denken aan de spanning op een analoge ingang of het aantal nuldoorgangen in een seconde van de voeding. Maar om hier een nuttig antwoord op te kunnen geven zijn toch meer details nodig over de beschikbare inputs en eventuele vrije pinnen en wat het mag kosten om te implementeren (zowel Hardware als software).

[Zoijar]

rand()%10 is overigens in [0,9] en is niet geheel uniform random. Dat laatste maakt misschien niet zo veel uit.

User input als randomness? Wat toetsen aanslaan, met muis/touch-pen bewegen? Weet niet waar je het voor nodig hebt...

[Soultaker]

Ik weet niet wat je met het programma doet, maar je zou kunnen overwegen om de RNG state (of gewoon een random RNG seed) op te slaan voor het afsluiten van het programma, en daar de volgende keer mee verder te gaan. Je voorkomt dan dat je elke keer dezelfde serie getallen krijgt.

Nadeel is natuurlijk dat je de eerste keer dat je het programma start nog wel gewoon dezelfde getallen krijgt, maar afhankelijk van wat je er mee doet, is dat misschien niet zo erg. De kwaliteit van de ingebouwde RNG is meestal toch niet zo hoog; als het er alleen om gaat om voor een menselijke gebruiker pseudo-random events te genereren, is het waarschijnlijk voldoende.

Verder lijkt het me trouwens heel sterk dat je platform geen enkele bron van tijd (desnoods als timestamp counter o.i.d.) heeft.

[ Voor 9% gewijzigd door Soultaker op 23-10-2008 17:29 ]

[.oisyn]

Zoijar schreef op donderdag 23 oktober 2008 @ 17:01:
User input als randomness? Wat toetsen aanslaan, met muis/touch-pen bewegen? Weet niet waar je het voor nodig hebt...

Dat was ook altijd de gebruikelijke methode op oudere handhelds en consoles, toen ze nog geen tijd bijhielden en geen opslagmogelijkheden hadden. Aan de hand van hoe lang het duurde voor je de eerste paar knoppen indrukte bepaalde je dan de seed. Of eventueel uit ongeïntialiseerd geheugen, voor zover dat mogelijk was.

[farlane]

Ik heb zelf een dergelijk probleem opgelost door de seed bij het flashen van mijn device te genereren op de PC en in de image mee te nemen.

[Onbekend]

Wat voor type embedded systeem heb je?
Met alleen programmacode krijg je nooit een echt random getal, dus je zal iets uit een externe bron (ruis) moeten halen.

[M-slayer]

Ik weet niet of het gaat op embedded systeem maar batterij status opvragen? en daarvanuit je random genereren? Dit getal lijkt me meestal altijd uniek (float ofzo)

[H!GHGuY]

niet elk embedded systeem heeft een RTC.

Wat je kan doen is bvb:
- timen van een ping of andere vorm van netwerk trafiek.
- user input
- andere vormen van input
- etc...

Je kan zoals al aangehaald je seed uiteindelijk opslaan op stable storage om daarmee na reboot verder te gaan. Entropie genereren kan dan tijdens het verdere verloop wel.

[farlane]

M-slayer schreef op donderdag 23 oktober 2008 @ 21:09:
Ik weet niet of het gaat op embedded systeem maar batterij status opvragen? en daarvanuit je random genereren? Dit getal lijkt me meestal altijd uniek (float ofzo)

Als je al de mogelijkheid hebt om de batterijstatus op te vragen zal het zeker geen float zijn. In de meeste gevallen echter heb je externe hardware nodig om dit te doen, en dan vraag ik me af of die spanning juist niet te stabiel is om een goede seed uit te halen.

[user109731]

Heeft het OS niet iets als /dev/random die je uit kan lezen?

[ Voor 30% gewijzigd door user109731 op 23-10-2008 23:13 ]

[farlane]

JanDM schreef op donderdag 23 oktober 2008 @ 23:11:
Heeft het OS niet iets als /dev/random die je uit kan lezen?

Je gaat ervan uit dat er een OS opstaat

[Recursio]

Kun je iets meer vertellen over het systeem waar het op gebruikt gaat worden? Als we meer over de hardware (en OS?) weten wordt het vast makkelijker.

[Jaap-Jan]

farlane schreef op donderdag 23 oktober 2008 @ 23:34:
[...]

Je gaat ervan uit dat er een OS opstaat

En ook nog eens een Unix- afgeleide.

En met Onbekend: welk systeem heb je. Er zijn honderden 'embedded systemen', iets meer details kan wel van pas komen om wat specifieke mogelijkheden te kunnen dragen.

[Verwijderd]

De meeste embedded CPU's hebben wel een api waarmee je een seed kunt krijgen.

[farlane]

Verwijderd schreef op donderdag 23 oktober 2008 @ 23:43:
De meeste embedded CPU's hebben wel een api waarmee je een seed kunt krijgen.

Ik werk oa met Atmel, ST, TI, Analog en Coldfire en voor zover die uP's al een library meekrijgen hebben alleen sommige versies met een RF gedeelte een dergelijke functie ( deze halen hun seed uit de rf ruis die ze meten )

Zou jij me kunnen vertellen op welke trefwoorden ik moet zoeken want ik heb ze niet gevonden?

[Verwijderd]

Je zou idd kunnen zoeken of je een (analoge) externe poort kunt vinden waar je een waarde uit haalt of een RF deel. Maar het zo afhankelijk van welke proc je gebruikt. Er is geen vaste zoek richting. Dan moet je met types komen van chips die je inzet. Zoeken in deze contreien is weten met wat voor chip je te maken hebt en bij mij komt daar een stuk onderbuik gevoel. Weten wat je kunt en wat je mag verwachten is geen "1-2-3-stappen-plan-zodat-je-altijd-resultaat-hebt" formule. Er zal vast wel zoiets zijn maar dat is niet mijn werkmethode. Sorry.

Als het je niet lukt om een correcte seed te krijgen kun je altijd nog het volgende doen.
Bij het starten van het systeem kun je een seed doen op een waarde die je uit eeprom haalt. Bij iedere "shutdown" van het systeem update je de "start"-waarde in eeprom met een nieuwe random waarde. Op die manier hou je een "echte" random over (want ECHT mathematische random kennen we natuurlijk niet).

Dit is overigens een heel gebruikelijke methode in de embedded wereld voor systemen die geen RTC hebben maar toch een random waarde nodig hebben. Het enige dilemma dat je hebt is dat je niet precies weet wanneer je moet schrijven. En wss wil je niet na iedere random actie de seed schrijven (anders is je eeprom wel erg snel stuk).

[ Voor 34% gewijzigd door Verwijderd op 24-10-2008 10:16 . Reden: typo + meer toelichting ]

[Verwijderd]

Bedankt voor de reacties allemaal,

Op mijn systeem zit er inderdaad geen RTC, en zelfs geen OS. Het is een eigen systeem draaiende op een 16Bit Infineon Processor. (XC-167)

Wat ik nu wel heb kunnen bereiken is de srand invullen aan de hand van een timer die ik laat lopen. Dit in combinatie met de gebruikersinput. (Het is een grafische display interface).

Dus de gebruiker drukt op een functie, en dan wordt de srand gegeneerd met de timer die loopt. Deze timer is atijd (meestal toch) verschillend, omdat de gebruiker nooit op hetzelfde tijdstip de actie kan uitvoeren.

Dit werkt toch naar behoren.

[Verwijderd]

FF zo maar een losse opmerking: een seed hoef je maar 1 keer te doen in de hele uptime van je systeem......? Dus waarom geen eeprom waarde gebruiken??? Dit kost je alleen maar batteries en proc tijd.

Het zal je nu mss nog niets uit maken maar al die kleine beetjes gaan je op een bepaald moment nekken in performance van je hele systeem. En om vervolgens een timer speciaal hiervoor in te zetten is ook erg zonde van je resources.

Als het code was die ik moest reviewen zou het opnieuw gedaan moeten worden en krijgt het een duidelijke NOK tijdens de code-review.

[ Voor 25% gewijzigd door Verwijderd op 24-10-2008 12:00 ]

[Verwijderd]

Verwijderd schreef op vrijdag 24 oktober 2008 @ 11:58:
FF zo maar een losse opmerking: een seed hoef je maar 1 keer te doen in de hele uptime van je systeem......? Dus waarom geen eeprom waarde gebruiken??? Dit kost je alleen maar batteries en proc tijd.

Het zal je nu mss nog niets uit maken maar al die kleine beetjes gaan je op een bepaald moment nekken in performance van je hele systeem. En om vervolgens een timer speciaal hiervoor in te zetten is ook erg zonde van je resources.

Als het code was die ik moest reviewen zou het opnieuw gedaan moeten worden en krijgt het een duidelijke NOK tijdens de code-review.

Een seed doe ik meerdere keren tijdens de uptime van een systeem. Het systeem wordt ingezet voor een random code-generator systeem. Iedere keer dat de gebruiker het schermpje voor de code ziet, moet er een andere random nummer getoond worden.

In normale omstandigheden zal dit inderdaad maar 1 keer gebeuren, en zal dit effectief maar 1 keer uitgevoerd worden ook.

Het gebruik van een timer is vrij simpel te verklaren, aangezien de timer in het systeem toch wordt gebruikt. Het is een bestaande timer die ik nu 'gebruik' om m'n seed te doen, geen resource problemen dus.

[Zoijar]

Verwijderd schreef op vrijdag 24 oktober 2008 @ 11:58:
FF zo maar een losse opmerking: een seed hoef je maar 1 keer te doen in de hele uptime van je systeem......? Dus waarom geen eeprom waarde gebruiken??? Dit kost je alleen maar batteries en proc tijd.

Het zal je nu mss nog niets uit maken maar al die kleine beetjes gaan je op een bepaald moment nekken in performance van je hele systeem. En om vervolgens een timer speciaal hiervoor in te zetten is ook erg zonde van je resources.

Als het code was die ik moest reviewen zou het opnieuw gedaan moeten worden en krijgt het een duidelijke NOK tijdens de code-review.

Die timer gebruik je maar 1 keer, als je je systeem aanzet en dan op de eerste actie. Een statische waarde moet je na elke random actie opslaan in je eprom. Wat anders als je de batterij eruit haalt en je geen kans meer krijgt om de seed op te slaan? Dan ga je herhalende randoms krijgen. Wanneer sla je je random seed dan op? Kan je het net zo goed een keer genereren aan het begin.

Ik ben blij dat ik geen code hoef te laten reviewen...

[Verwijderd]

Maar nu krijg je als je je systeem automatisch gaat testen (wat ik ff nu aanneem) wss altijd dezelfde (dus niet random) waardes te zien. En het is me nu even niet duidelijk of je tijdens de uptime van je systeem nu 1 of meerdere keren een seed doet (en ik heb het over uptime die eindigd bij een volledige power down waar bij al je volatile geheugen geleegd wordt/is).

[Verwijderd]

Zoijar schreef op vrijdag 24 oktober 2008 @ 12:11:
[...]

Die timer gebruik je maar 1 keer, als je je systeem aanzet en dan op de eerste actie. Een statische waarde moet je na elke random actie opslaan in je eprom. Wat anders als je de batterij eruit haalt en je geen kans meer krijgt om de seed op te slaan? Dan ga je herhalende randoms krijgen. Wanneer sla je je random seed dan op? Kan je het net zo goed een keer genereren aan het begin.

Je zou er ook voor kunnen kiezen om de eerste random request die gedaan wordt als seedinput te schrijven in eeprom. (we hebben het over non-volatile memory dat dus niet verdwijnt na battery remove).

Ik ben blij dat ik geen code hoef te laten reviewen...

HAHAHAHA, ach ik denk dat je er alleen maar van kunt leren. En er zijn idd genoeg wegen die naar Rome leiden alleen heb ik al iets te vaak de kreet: "Random-function is not Random" als problem report gezien. B.v. heb ik ooit gewerkt aan een BT-stack waar dit toch echt wel van belang was..... De seed afhankelijk maken van een user input lijkt mooi maar is wss niet random genoeg. (En tja dat kan best wel bull zijn want ik ken de toepassing niet waar we het hier over hebben. Voor 't zelfde geld is dit helemaal niet functie kritisch, dan slik ik bij deze al m'n commentaar graag in).


p.s. huidige functie, System Architect, 15 jaar ervaring in o.a. embedded systems ;-), Just trying to help....

[ Voor 4% gewijzigd door Verwijderd op 24-10-2008 14:35 ]

[.oisyn]

Verwijderd schreef op vrijdag 24 oktober 2008 @ 14:33:
De seed afhankelijk maken van een user input lijkt mooi maar is wss niet random genoeg. (En tja dat kan best wel bull zijn want ik ken de toepassing niet waar we het hier over hebben).

Dus vanwaar dan de "waarschijnlijk"? Je zegt zelf al dat je er eigenlijk geen zinnig woord over kunt zeggen. Dus dat "waarschijnlijk" kun je net zo goed achterwege laten. Btw, user input heeft zich al jaren bewezen als entropy source in gamedevelopment én cryptografie (hoewel je bij die laatste misschien niet louter wilt concentreren op user input). Hoe zinvol het daadwerkelijk is hangt geheel af van de use case.

p.s. huidige functie, System Architect, 15 jaar ervaring in o.a. embedded systems ;-)

Stoer hoor

[ Voor 10% gewijzigd door .oisyn op 24-10-2008 16:59 ]

[curry684]

Verwijderd schreef op vrijdag 24 oktober 2008 @ 14:33:
[...]

De seed afhankelijk maken van een user input lijkt mooi maar is wss niet random genoeg.

De gemiddelde systemtimer rekent stiekem toch echt in millisecondes of erger nog clock ticks. De toepassing waar we het over hebben staat in de TS:

Ik heb een probleempje om enkele random getallen te genereren tussen 0 en 10.

Nou daarvoor is dit echt wel afdoende

[Elijan9]

Tja, een C167 levert nu eenmaal ook niet zoveel mogelijkheden (ook niet voor C++ trouwens, waarom C++ en geen C?! )

Als je echt goede random getallen wilt hebben (dat denk ik niet, dan doe je geen modulo 10), dan kun je ook een random generator IC kopen en erop aansluiten. Dat is hoe een voormalig werkgever dat had opgelost voor een c16x systeempje die 64bit sleutels moest uitgeven.

Je kunt het ook proberen met een ruis genererend circuitje aan te sluiten op een volt-comparator, waarbij afhankelijk van het nivo de uitgang op 1 of 0 komt te staan. Door dit bit een aantal keren uit te lezen heb je een eenvoudig pseudo random generatortje. Niet enorm betrouwbaar en dan vooral afhankelijk van de implementatie in hardware, maar wel goedkoop te realiseren.

Als je het in software wil doen, waarschijnlijk heb je een mainloop en verder interrupt gebaseerde functies? Eventueel kun je ook in je mainloop een bewerking doen op een variabele (bijvoorbeeld een rc4 berekening) en bij een of meerdere interrupt routines (bijvoorbeeld keyboard/keypad) de waarde van dat moment in een circulair buffer stoppen. Uit deze buffer haal je dan weer je random getal.

[Jaap-Jan]

Elijan9 schreef op vrijdag 24 oktober 2008 @ 15:57:
(...)

De processor heeft ook een A/D- converter die je daarvoor kunt gebruiken.

[ Voor 6% gewijzigd door Jaap-Jan op 24-10-2008 16:14 ]

[Elijan9]

Jaap-Jan schreef op vrijdag 24 oktober 2008 @ 16:13:
[...]
De processor heeft ook een A/D- converter die je daarvoor kunt gebruiken.

Als die niet al in gebruik is, dat dan wel...

[Zoijar]

Verwijderd schreef op vrijdag 24 oktober 2008 @ 14:33:
Je zou er ook voor kunnen kiezen om de eerste random request die gedaan wordt als seedinput te schrijven in eeprom. (we hebben het over non-volatile memory dat dus niet verdwijnt na battery remove).

Daar had ik het ook over. Mijn punt was dat je het over resources en performance had. Een user-input seed genereer je een keer en heb je in principe geen resources voor nodig die je niet meteen weer vrij geeft. Mijn battery remove opmerking was gebasseerd op het feit dat als je een seed opslaat in een eeprom, je dat toch op een bepaald moment moet doen. Er is altijd de mogelijkheid dat je device uitgezet wordt voordat die write wordt gedaan, en op dat moment gebruik je weer dezelfde seed en genereer je weer dezelfde getallen in een volgende sessie. Dus moet je op een goed moment die opslag doen.

Na je eerste random de seed naar eeprom schrijven lijkt me ook een oplossing idd. Enige "nadeel" vind ik hier dat je sequences volledig deterministisch zijn en niet 100% veilig mocht je dat nodig hebben. Plus dat elk device uit factory settings waarschijnlijk dezelfde getallen gaat genereren in sequence. Of je moet elke anders initialiseren. Plus dat je eeprom geheugen nodig hebt. Alles bij elkaar lijkt me het dynamisch genereren van een seed dan toch een betere oplossing.

HAHAHAHA, ach ik denk dat je er alleen maar van kunt leren. En er zijn idd genoeg wegen die naar Rome leiden alleen heb ik al iets te vaak de kreet: "Random-function is not Random" als problem report gezien. B.v. heb ik ooit gewerkt aan een BT-stack waar dit toch echt wel van belang was.....

Van luisteren naar andere opties leer je idd altijd wel wat. Ik nam je kennis niet in twijfel. Maar om meteen een redelijke oplossing af te doen als zeker niet door een review cycle te komen... hmmm...

De seed afhankelijk maken van een user input lijkt mooi maar is wss niet random genoeg. (En tja dat kan best wel bull zijn want ik ken de toepassing niet waar we het hier over hebben. Voor 't zelfde geld is dit helemaal niet functie kritisch, dan slik ik bij deze al m'n commentaar graag in).

Hmm dat ligt eraan hoe je het implementeert. Van wat ik weet wordt key-generation altijd op user-input randomness gedaan omdat dat meestal de enige betrouwbare source van entropie is op je systeem. 10 seconden met je muis bewegen en toetsen aanslaan en dat dan op microseconde niveau timen. Als je in een applicatie iets inbouwt dat zegt "click mouse to start" en je timed de microseconde fractie van hoe lang het duurt voordat je klikt, plus de positie van het inputdevice kan dat prima werken. Het ligt er natuurlijk aan wat voor device je hebt. Op een wasmachine is dat lastig. Er is denk ik altijd wel iets slims te bedenken dat zo werkt.

p.s. huidige functie, System Architect, 15 jaar ervaring in o.a. embedded systems ;-), Just trying to help....

Ik weet eigenlijk niets van embedded systems... ik denk gewoon logisch na, daar wordt ik voor opgeleid. En om kritisch te zijn.

[farlane]

Trouwens, ik weet niet of je aan deze chip vast zit maar er zijn inmiddels high performance 32bit uP's op de markt voor een prijs van rond de 3 dollar per 1000 stuks.

Als je in een dergelijk traject zit, zou ik je willen aanraden om naar de STM32F10X serie te kijken. Met een Cortex-M3 ARM core / 72Mhz is dit echt een racemonster ( relatief dan he )

[edit]
Ehm ja, 3 dollar per stuk bij 1000stuks

[ Voor 6% gewijzigd door farlane op 24-10-2008 17:02 ]

[MSalters]

3000 dollar per 1000 stuks, neem ik aan.

[Refro]

Verwijderd schreef op vrijdag 24 oktober 2008 @ 11:28:
Op mijn systeem zit er inderdaad geen RTC, en zelfs geen OS. Het is een eigen systeem draaiende op een 16Bit Infineon Processor. (XC-167)

offtopic:
Welke compiler gebruk je hierbij? Wij hebben naar die van keil gekeken maar die was/is bagger (en werkt ook niet met onze lauterbach emulatoren).

[Verwijderd]

.oisyn schreef op vrijdag 24 oktober 2008 @ 15:27:
[...]

Dus vanwaar dan de "waarschijnlijk"? Je zegt zelf al dat je er eigenlijk geen zinnig woord over kunt zeggen. Dus dat "waarschijnlijk" kun je net zo goed achterwege laten. Btw, user input heeft zich al jaren bewezen als entropy source in gamedevelopment én cryptografie (hoewel je bij die laatste misschien niet louter wilt concentreren op user input). Hoe zinvol het daadwerkelijk is hangt geheel af van de use case.


[...]

Stoer hoor

Was niet bedoeld als stoer en flames mag je ergens anders posten.

[.oisyn]

Ik zie geen flames in mijn post

[Zoijar]

dat soort houdingen zijn idd een van de redenen dat ik het niet in de industrie zoek...

[Wimo.]

Zoijar schreef op woensdag 29 oktober 2008 @ 00:11:
dat soort houdingen zijn idd een van de redenen dat ik het niet in de industrie zoek...

Daar zijn de BI'ers ook voor

[farlane]

Zoijar schreef op woensdag 29 oktober 2008 @ 00:11:
dat soort houdingen zijn idd een van de redenen dat ik het niet in de industrie zoek...

Idd, in de kantoorautomatisering heb je mensen die dit soort opmerkingen maken niet...

[Zoijar]

ok, ok, vertalingsfoutje... "industry" i.e. non-academic

[farlane]

Zoijar schreef op woensdag 29 oktober 2008 @ 13:58:
ok, ok, vertalingsfoutje... "industry" i.e. non-academic

Idd, in een academische omgeving heb je mensen die dit soort opmerkingen maken niet...

[writser]

Nee, daar mag je de hele dag nutteloze papers schrijven die keihard door je collegae worden afgebrand.