How can I get random numbers on AVR?
Clash Royale CLAN TAG#URR8PPP
$begingroup$
I will try to make the game MegaMind. I need to get a random number, but how can I get these?
I have tried something:
secret_code[1] = random()&=6;
random-number
edited Jan 2 at 15:50
Dave Tweed♦
118k9145256
asked Jan 2 at 15:33
Dion123Dion123
272
$endgroup$
|
show 8 more comments
$begingroup$
I will try to make the game MegaMind. I need to get a random number, but how can I get these?
I have tried something:
secret_code[1] = random()&=6;
random-number
edited Jan 2 at 15:50
Dave Tweed♦
118k9145256
asked Jan 2 at 15:33
Dion123Dion123
272
$endgroup$
2
$begingroup$
Which AVR? Does it have a hardware random number generator, or an ADC?
$endgroup$
– Colin
Jan 2 at 15:37
6
$begingroup$
Here are four things I know about random numbers: 1) They're fiendishly hard to do 'really right'. 2) There are tons of well-documented algorithms on the Internet, there for the searching (hint, hint). 3) You can do an adequate job on a bitty little processor, particularly if it's for casual stuff like gaming. 4) I'm no expert beyond points 1, 2 & 3. Why don't you search, then tell us what you found and why you're either still confused or unhappy with your options? I suggest "good random number generator for gaming" as a starting point for your search.
$endgroup$
– TimWescott
Jan 2 at 15:40
8
$begingroup$
"I have tried something:" -- So what happened? That line of code doesn't look like it would even compile -- a function call (random()) can't be an lvalue (for the operator&=).
$endgroup$
– Dave Tweed♦
Jan 2 at 15:52
5
$begingroup$
This is a hard problem in general, so it's usually best to look at the specific need. What are the random numbers for? What else is going on? The early Simon electronic memory game for example used the low bits of a free running counter - technically the "random" patterns were determined by how long it took the user to push a button, but at a resolution which no human could recognize or game.
$endgroup$
– Chris Stratton
Jan 2 at 16:06
1
$begingroup$
One approach for creating a new seed for non-critical applications is to just use an incrementing number that is stored in an EEPROM location at every program invocation. E.g if the initial value is 1, the next time the code uses the seed it will be 2 etc. This then will create a different set of random numbers for every game but will be easy to to test as the code doesn't rely on any randomness from switches, timers etc.
$endgroup$
– Kevin White
Jan 3 at 0:17
|
show 8 more comments
$begingroup$
I will try to make the game MegaMind. I need to get a random number, but how can I get these?
I have tried something:
secret_code[1] = random()&=6;
random-number
edited Jan 2 at 15:50
Dave Tweed♦
118k9145256
asked Jan 2 at 15:33
Dion123Dion123
272
$endgroup$
I will try to make the game MegaMind. I need to get a random number, but how can I get these?
I have tried something:
secret_code[1] = random()&=6;
random-number
random-number
edited Jan 2 at 15:50
Dave Tweed♦
118k9145256
asked Jan 2 at 15:33
Dion123Dion123
272
edited Jan 2 at 15:50
Dave Tweed♦
118k9145256
asked Jan 2 at 15:33
Dion123Dion123
272
edited Jan 2 at 15:50
Dave Tweed♦
118k9145256
edited Jan 2 at 15:50
Dave Tweed♦
118k9145256
edited Jan 2 at 15:50
Dave Tweed♦
118k9145256
118k9145256
asked Jan 2 at 15:33
Dion123Dion123
272
asked Jan 2 at 15:33
Dion123Dion123
272
asked Jan 2 at 15:33
Dion123Dion123
272
272
2
$begingroup$
Which AVR? Does it have a hardware random number generator, or an ADC?
$endgroup$
– Colin
Jan 2 at 15:37
6
$begingroup$
Here are four things I know about random numbers: 1) They're fiendishly hard to do 'really right'. 2) There are tons of well-documented algorithms on the Internet, there for the searching (hint, hint). 3) You can do an adequate job on a bitty little processor, particularly if it's for casual stuff like gaming. 4) I'm no expert beyond points 1, 2 & 3. Why don't you search, then tell us what you found and why you're either still confused or unhappy with your options? I suggest "good random number generator for gaming" as a starting point for your search.
$endgroup$
– TimWescott
Jan 2 at 15:40
8
$begingroup$
"I have tried something:" -- So what happened? That line of code doesn't look like it would even compile -- a function call (random()) can't be an lvalue (for the operator&=).
$endgroup$
– Dave Tweed♦
Jan 2 at 15:52
5
$begingroup$
This is a hard problem in general, so it's usually best to look at the specific need. What are the random numbers for? What else is going on? The early Simon electronic memory game for example used the low bits of a free running counter - technically the "random" patterns were determined by how long it took the user to push a button, but at a resolution which no human could recognize or game.
$endgroup$
– Chris Stratton
Jan 2 at 16:06
1
$begingroup$
One approach for creating a new seed for non-critical applications is to just use an incrementing number that is stored in an EEPROM location at every program invocation. E.g if the initial value is 1, the next time the code uses the seed it will be 2 etc. This then will create a different set of random numbers for every game but will be easy to to test as the code doesn't rely on any randomness from switches, timers etc.
$endgroup$
– Kevin White
Jan 3 at 0:17
|
show 8 more comments
2
$begingroup$
Which AVR? Does it have a hardware random number generator, or an ADC?
$endgroup$
– Colin
Jan 2 at 15:37
6
$begingroup$
Here are four things I know about random numbers: 1) They're fiendishly hard to do 'really right'. 2) There are tons of well-documented algorithms on the Internet, there for the searching (hint, hint). 3) You can do an adequate job on a bitty little processor, particularly if it's for casual stuff like gaming. 4) I'm no expert beyond points 1, 2 & 3. Why don't you search, then tell us what you found and why you're either still confused or unhappy with your options? I suggest "good random number generator for gaming" as a starting point for your search.
$endgroup$
– TimWescott
Jan 2 at 15:40
8
$begingroup$
"I have tried something:" -- So what happened? That line of code doesn't look like it would even compile -- a function call (random()) can't be an lvalue (for the operator&=).
$endgroup$
– Dave Tweed♦
Jan 2 at 15:52
5
$begingroup$
This is a hard problem in general, so it's usually best to look at the specific need. What are the random numbers for? What else is going on? The early Simon electronic memory game for example used the low bits of a free running counter - technically the "random" patterns were determined by how long it took the user to push a button, but at a resolution which no human could recognize or game.
$endgroup$
– Chris Stratton
Jan 2 at 16:06
1
$begingroup$
One approach for creating a new seed for non-critical applications is to just use an incrementing number that is stored in an EEPROM location at every program invocation. E.g if the initial value is 1, the next time the code uses the seed it will be 2 etc. This then will create a different set of random numbers for every game but will be easy to to test as the code doesn't rely on any randomness from switches, timers etc.
$endgroup$
– Kevin White
Jan 3 at 0:17
2
2
$begingroup$
Which AVR? Does it have a hardware random number generator, or an ADC?
$endgroup$
– Colin
Jan 2 at 15:37
$begingroup$
Which AVR? Does it have a hardware random number generator, or an ADC?
$endgroup$
– Colin
Jan 2 at 15:37
6
6
$begingroup$
Here are four things I know about random numbers: 1) They're fiendishly hard to do 'really right'. 2) There are tons of well-documented algorithms on the Internet, there for the searching (hint, hint). 3) You can do an adequate job on a bitty little processor, particularly if it's for casual stuff like gaming. 4) I'm no expert beyond points 1, 2 & 3. Why don't you search, then tell us what you found and why you're either still confused or unhappy with your options? I suggest "good random number generator for gaming" as a starting point for your search.
$endgroup$
– TimWescott
Jan 2 at 15:40
$begingroup$
Here are four things I know about random numbers: 1) They're fiendishly hard to do 'really right'. 2) There are tons of well-documented algorithms on the Internet, there for the searching (hint, hint). 3) You can do an adequate job on a bitty little processor, particularly if it's for casual stuff like gaming. 4) I'm no expert beyond points 1, 2 & 3. Why don't you search, then tell us what you found and why you're either still confused or unhappy with your options? I suggest "good random number generator for gaming" as a starting point for your search.
$endgroup$
– TimWescott
Jan 2 at 15:40
8
8
$begingroup$
"I have tried something:" -- So what happened? That line of code doesn't look like it would even compile -- a function call (
random()) can't be an lvalue (for the operator &=).$endgroup$
– Dave Tweed♦
Jan 2 at 15:52
$begingroup$
"I have tried something:" -- So what happened? That line of code doesn't look like it would even compile -- a function call (
random()) can't be an lvalue (for the operator &=).$endgroup$
– Dave Tweed♦
Jan 2 at 15:52
5
5
$begingroup$
This is a hard problem in general, so it's usually best to look at the specific need. What are the random numbers for? What else is going on? The early Simon electronic memory game for example used the low bits of a free running counter - technically the "random" patterns were determined by how long it took the user to push a button, but at a resolution which no human could recognize or game.
$endgroup$
– Chris Stratton
Jan 2 at 16:06
$begingroup$
This is a hard problem in general, so it's usually best to look at the specific need. What are the random numbers for? What else is going on? The early Simon electronic memory game for example used the low bits of a free running counter - technically the "random" patterns were determined by how long it took the user to push a button, but at a resolution which no human could recognize or game.
$endgroup$
– Chris Stratton
Jan 2 at 16:06
1
1
$begingroup$
One approach for creating a new seed for non-critical applications is to just use an incrementing number that is stored in an EEPROM location at every program invocation. E.g if the initial value is 1, the next time the code uses the seed it will be 2 etc. This then will create a different set of random numbers for every game but will be easy to to test as the code doesn't rely on any randomness from switches, timers etc.
$endgroup$
– Kevin White
Jan 3 at 0:17
$begingroup$
One approach for creating a new seed for non-critical applications is to just use an incrementing number that is stored in an EEPROM location at every program invocation. E.g if the initial value is 1, the next time the code uses the seed it will be 2 etc. This then will create a different set of random numbers for every game but will be easy to to test as the code doesn't rely on any randomness from switches, timers etc.
$endgroup$
– Kevin White
Jan 3 at 0:17
|
show 8 more comments
3 Answers
3
active
oldest
votes
$begingroup$
Random Numbers and Computers
Let us talk a second about what it takes to generate random numbers.
Randomness is very easy for humans to imagine or produce: Flip a coin. The result is random. The next time you flip the same coin, it will be random again, and there will be no correlation to the previous coin-flips.
That's way harder for processors. These are machines to be as deterministic as possible. Generally, when you build a digital circuit, any non-determinism ("random behaviour") is undesired.
In that framework, i.e. if your digital circuit (e.g. an AVR) works perfectly deterministically, then there's simply no way to generate truly random numbers. These numbers must always be a result of some calculation on numbers that were there before, so that there can only be a "seemingly" random sequence of numbers.
The next time you feed the same algorithm with the same "inital input", you get the same sequence of numbers. We call an algorithm that generates a seemingly random numbers a pseudo-random number generator (PRNG).
But that is practically always (aside from cryptography) an acceptable solution. There's typically a large numbers of initial states, and if the PRNG is any good, any of these initial states will yield a totally different, totally uncorrelated, totally fairly distributed sequence of numbers.
Pseudo-random number generation on microcontrollers in practice
On a microcontroller, you don't want to use a function like rand or srand with a hidden global state of a single pseudo random number generator (PRNG) - that is a waste of the little RAM you have, if you at some point can stop using the PRNG, and a recipe for disaster if you're interacting with the PRNG from interrupt routines.
Instead, use a "slim" random number generator function that takes and modifies an explicit, small state. The AVR stdlib possibly offers rand_r, but that's just a bad random number generator; with the same effort in state space and computation, you can get much "randomer" numbers.
For medium-to-high-quality PRNG, I personally use my state-external variant of the XOROSHIRO128+ algorithm. It requires 16B of state memory, and is probably far over the top for a microcontroller-based game.
The XORSHIFT32 algorithm, that XOROSHIRO128+ is indirectly based on, only uses four bytes of state, and should be plenty random for your use case, and will return one 32bit random number each call, and modify the state. If you look at it, it's also pretty fast – just three shifts and three XORs on 32 bit numbers. While your AVR (assuming it's not AVR32) doesn't have 32 bit integers (I think), these operations should still be faster than at least what the glibc implementation of rand() does.
Seeding your PRNG
The real question is how to initialize the state (seed the PRNG). That seed determines the only seemingly random sequence of numbers that you'll get!
That is especially challenging on a small device like an AVR: You can't use something like the current time (which was always a bad seed, but someone started telling people it's good one :(, so people use that), because it has no notion of time; you can't use physically random things like the seek time of your hard drive, because there is no hard drive, and so on.
But: your microcontroller has an ADC, for example. So, simply get a series of ADC measurements and use the least significant bits, which should essentially be noise, to generate the initial state that you use for your PRNG. Maybe take an ADC measurement, XOR with the last measurement, shift up, take the next measurement, repeat 16 times, use that as initial state.
answered Jan 2 at 17:34
Marcus MüllerMarcus Müller
32.3k35894
$endgroup$
2
$begingroup$
The other semi-common trick for getting random numbers is from comparisons of different clock sources. The jitter between the main clock and the slow watchdog timer can be used as a source of "true" entropy (by sampling a fast counter every watchdog interrupt, or similar). Works well for AVRs, where even the very cheap ones have an independent watchdog IIRC.
$endgroup$
– mbrig
Jan 2 at 22:52
3
$begingroup$
@mbrig thanks! yeah, thinking about this: since this device definitely has user interface buttons, the ringing of keypresses and their timing might be a source of entropy, too.
$endgroup$
– Marcus Müller
Jan 2 at 22:56
2
$begingroup$
A digital circuit is only perfectly (or even ideally) deterministic as long as there's only one oscillator providing a basis for all the clocks. As soon as you have at least two crystals, it's highly nondeterministic, and you can exploit this for very high quality random seeds. May be overkill for a game, but it's a good principle to know.
$endgroup$
– R..
Jan 3 at 3:25
add a comment |
$begingroup$
From the AVR Libc Reference Manual, under stdlib.h: General utilities:
Function
rand():
int rand(void)
The
rand()function computes a sequence of pseudo-random integers in
the range of0toRAND_MAX(as defined by the header file
<stdlib.h>).
The
srand()function sets its argument seed as the seed for a new
sequence of pseudo-random numbers to be returned byrand(). These
sequences are repeatable by callingsrand()with the same seed
value.
If no seed value is provided, the functions are automatically seeded
with a value of1.
In compliance with the C standard, these functions operate on int
arguments. Since the underlying algorithm already uses 32-bit
calculations, this causes a loss of precision. Seerandom()for an
alternate set of functions that retains full 32-bit precision.
Basically, you want to use srand() to set a seed for rand() to use. rand() will generate the numbers based on the seed srand() provides.
A common way to get a seed for srand() is to use a timer that is based on some user action so you get a fairly unique sequence every time. If you don't change the seed, the number sequence will always be the same.
edited Jan 2 at 18:03
Marcus Müller
32.3k35894
answered Jan 2 at 15:58
evildemonicevildemonic
1,930618
$endgroup$
2
$begingroup$
@EugeneSh. This is why I specified based on user action. Since the OP is talking about a game, I doubt they need super true authentic random. If so, yes, using for instance an ADC value reading the noise on a diode or something could be better.
$endgroup$
– evildemonic
Jan 2 at 16:27
1
$begingroup$
I appreciate you folks helping me improve my answer, and bring you up good points. Since this is a game, there should be user action at some point, and this can perhaps be 'forced' early on. The seed can be generated at any point before the random number is needed. Something as simple as timing how long it takes for the player to enter their name, or select an option from the opening menu. Without more input from the OP, it is hard to speculate on what they need and what we have to work with.
$endgroup$
– evildemonic
Jan 2 at 16:35
1
$begingroup$
I'll be honest: on a programmer's website (such as stackexchange.com), the recommendation to userandandsrandwould be worth a very comprehensive comment on why that is a very bad idea. These functions aren't reentrant-save, so interaction with their state from ISRs or multiple tasks is potentially catastrophic. If I was AVR, I'd honestly not include these functions. The way to go is not a random number generator with hidden global state, especially not on a microcontroller.
$endgroup$
– Marcus Müller
Jan 2 at 17:14
1
$begingroup$
@MarcusMüller The re-entrant version of rand() is rand_r(). I'm not sure it is needed. I'm also not sure I follow you on why it would be a very bad idea to use rand() like this on an AVR or how it would be catastrophic unless you need to reproduce the sequence and haven't been careful about how you use it. Is there something inherent to hidden global states that make them inappropriate for microcontrollers?
$endgroup$
– evildemonic
Jan 2 at 17:32
1
$begingroup$
@evildemonic well, first of all, you kind of need to allocate some space somewhere when using therandfunction, forever. That might be highly problematic on memory-starved architectures. So, you'd always go forrand_r, simply because then you / your compiler is in charge of knowing when you don't need that anymore; then, OK, this is a game, and truly random would not be a problem here, but in general, when using a PRNG likerandyou can't accept RNG behaviour.
$endgroup$
– Marcus Müller
Jan 2 at 17:38
|
show 4 more comments
$begingroup$
The other answers are more theoretical, but I have done some practical experiments in this area.
Using an AVR XMEGA microcontroller I sampled the internal temperature sensor continuously with the ADC. From each reading I took only the least significant bit, which is subject to the most noise. I then combined 8 such bits and fed them into the on-board CRC generator, using one byte of its output as my random bits. The CRC generator was just a fast, convenient way of mixing and whitening the bits, other methods work too.
This code implements it: https://github.com/kuro68k/xrng/blob/master/firmware2/xrng/rng.c
I did extensive testing of the output. Even generating 8+ megabits per second the output does will with standard randomness tests, including DieHarder.
For your purposes this is probably overkill. Unfortunately you don't mention which AVR you are using, but most only have a 10 bit ADC (the XMEGA is 12 bit) and often lack an internal temperature sensor. However, using just 10 bits and sampling the internal voltage reference, or a floating (disconnected) pin you may get decent results. I'd suggest collecting 16 bits (16 samples, take only the least significant bit) and combining them into a 16 bit word, and then repeating that 16 times with the results XORed together, and then feed the result to the srand() function. Then periodically take another 16 samples, XOR and feed into srand() again.
Then you can just use the normal rand() function to get random numbers. By seeding it with a half decent source of entropy the results should be sufficiently unpredictable for your game.
Alternatively, some AVRs have a watchdog timer that can trigger an interrupt. The watchdog timer is a fairly decent random number generator because it's frequency varies randomly, so you can just set up a fast timer (clock divider 1, maximum core clock frequency) and sample the least significant bit every time the watchdog interrupt is triggered. I believe other people have tested that method and found it to be a good source of entropy.
answered Jan 3 at 11:55
useruser
1,244616
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");
StackExchange.ifUsing("editor", function ()
return StackExchange.using("schematics", function ()
StackExchange.schematics.init();
);
, "cicuitlab");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "135"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2felectronics.stackexchange.com%2fquestions%2f414867%2fhow-can-i-get-random-numbers-on-avr%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Random Numbers and Computers
Let us talk a second about what it takes to generate random numbers.
Randomness is very easy for humans to imagine or produce: Flip a coin. The result is random. The next time you flip the same coin, it will be random again, and there will be no correlation to the previous coin-flips.
That's way harder for processors. These are machines to be as deterministic as possible. Generally, when you build a digital circuit, any non-determinism ("random behaviour") is undesired.
In that framework, i.e. if your digital circuit (e.g. an AVR) works perfectly deterministically, then there's simply no way to generate truly random numbers. These numbers must always be a result of some calculation on numbers that were there before, so that there can only be a "seemingly" random sequence of numbers.
The next time you feed the same algorithm with the same "inital input", you get the same sequence of numbers. We call an algorithm that generates a seemingly random numbers a pseudo-random number generator (PRNG).
But that is practically always (aside from cryptography) an acceptable solution. There's typically a large numbers of initial states, and if the PRNG is any good, any of these initial states will yield a totally different, totally uncorrelated, totally fairly distributed sequence of numbers.
Pseudo-random number generation on microcontrollers in practice
On a microcontroller, you don't want to use a function like rand or srand with a hidden global state of a single pseudo random number generator (PRNG) - that is a waste of the little RAM you have, if you at some point can stop using the PRNG, and a recipe for disaster if you're interacting with the PRNG from interrupt routines.
Instead, use a "slim" random number generator function that takes and modifies an explicit, small state. The AVR stdlib possibly offers rand_r, but that's just a bad random number generator; with the same effort in state space and computation, you can get much "randomer" numbers.
For medium-to-high-quality PRNG, I personally use my state-external variant of the XOROSHIRO128+ algorithm. It requires 16B of state memory, and is probably far over the top for a microcontroller-based game.
The XORSHIFT32 algorithm, that XOROSHIRO128+ is indirectly based on, only uses four bytes of state, and should be plenty random for your use case, and will return one 32bit random number each call, and modify the state. If you look at it, it's also pretty fast – just three shifts and three XORs on 32 bit numbers. While your AVR (assuming it's not AVR32) doesn't have 32 bit integers (I think), these operations should still be faster than at least what the glibc implementation of rand() does.
Seeding your PRNG
The real question is how to initialize the state (seed the PRNG). That seed determines the only seemingly random sequence of numbers that you'll get!
That is especially challenging on a small device like an AVR: You can't use something like the current time (which was always a bad seed, but someone started telling people it's good one :(, so people use that), because it has no notion of time; you can't use physically random things like the seek time of your hard drive, because there is no hard drive, and so on.
But: your microcontroller has an ADC, for example. So, simply get a series of ADC measurements and use the least significant bits, which should essentially be noise, to generate the initial state that you use for your PRNG. Maybe take an ADC measurement, XOR with the last measurement, shift up, take the next measurement, repeat 16 times, use that as initial state.
answered Jan 2 at 17:34
Marcus MüllerMarcus Müller
32.3k35894
$endgroup$
2
$begingroup$
The other semi-common trick for getting random numbers is from comparisons of different clock sources. The jitter between the main clock and the slow watchdog timer can be used as a source of "true" entropy (by sampling a fast counter every watchdog interrupt, or similar). Works well for AVRs, where even the very cheap ones have an independent watchdog IIRC.
$endgroup$
– mbrig
Jan 2 at 22:52
3
$begingroup$
@mbrig thanks! yeah, thinking about this: since this device definitely has user interface buttons, the ringing of keypresses and their timing might be a source of entropy, too.
$endgroup$
– Marcus Müller
Jan 2 at 22:56
2
$begingroup$
A digital circuit is only perfectly (or even ideally) deterministic as long as there's only one oscillator providing a basis for all the clocks. As soon as you have at least two crystals, it's highly nondeterministic, and you can exploit this for very high quality random seeds. May be overkill for a game, but it's a good principle to know.
$endgroup$
– R..
Jan 3 at 3:25
add a comment |
$begingroup$
Random Numbers and Computers
Let us talk a second about what it takes to generate random numbers.
Randomness is very easy for humans to imagine or produce: Flip a coin. The result is random. The next time you flip the same coin, it will be random again, and there will be no correlation to the previous coin-flips.
That's way harder for processors. These are machines to be as deterministic as possible. Generally, when you build a digital circuit, any non-determinism ("random behaviour") is undesired.
In that framework, i.e. if your digital circuit (e.g. an AVR) works perfectly deterministically, then there's simply no way to generate truly random numbers. These numbers must always be a result of some calculation on numbers that were there before, so that there can only be a "seemingly" random sequence of numbers.
The next time you feed the same algorithm with the same "inital input", you get the same sequence of numbers. We call an algorithm that generates a seemingly random numbers a pseudo-random number generator (PRNG).
But that is practically always (aside from cryptography) an acceptable solution. There's typically a large numbers of initial states, and if the PRNG is any good, any of these initial states will yield a totally different, totally uncorrelated, totally fairly distributed sequence of numbers.
Pseudo-random number generation on microcontrollers in practice
On a microcontroller, you don't want to use a function like rand or srand with a hidden global state of a single pseudo random number generator (PRNG) - that is a waste of the little RAM you have, if you at some point can stop using the PRNG, and a recipe for disaster if you're interacting with the PRNG from interrupt routines.
Instead, use a "slim" random number generator function that takes and modifies an explicit, small state. The AVR stdlib possibly offers rand_r, but that's just a bad random number generator; with the same effort in state space and computation, you can get much "randomer" numbers.
For medium-to-high-quality PRNG, I personally use my state-external variant of the XOROSHIRO128+ algorithm. It requires 16B of state memory, and is probably far over the top for a microcontroller-based game.
The XORSHIFT32 algorithm, that XOROSHIRO128+ is indirectly based on, only uses four bytes of state, and should be plenty random for your use case, and will return one 32bit random number each call, and modify the state. If you look at it, it's also pretty fast – just three shifts and three XORs on 32 bit numbers. While your AVR (assuming it's not AVR32) doesn't have 32 bit integers (I think), these operations should still be faster than at least what the glibc implementation of rand() does.
Seeding your PRNG
The real question is how to initialize the state (seed the PRNG). That seed determines the only seemingly random sequence of numbers that you'll get!
That is especially challenging on a small device like an AVR: You can't use something like the current time (which was always a bad seed, but someone started telling people it's good one :(, so people use that), because it has no notion of time; you can't use physically random things like the seek time of your hard drive, because there is no hard drive, and so on.
But: your microcontroller has an ADC, for example. So, simply get a series of ADC measurements and use the least significant bits, which should essentially be noise, to generate the initial state that you use for your PRNG. Maybe take an ADC measurement, XOR with the last measurement, shift up, take the next measurement, repeat 16 times, use that as initial state.
answered Jan 2 at 17:34
Marcus MüllerMarcus Müller
32.3k35894
$endgroup$
2
$begingroup$
The other semi-common trick for getting random numbers is from comparisons of different clock sources. The jitter between the main clock and the slow watchdog timer can be used as a source of "true" entropy (by sampling a fast counter every watchdog interrupt, or similar). Works well for AVRs, where even the very cheap ones have an independent watchdog IIRC.
$endgroup$
– mbrig
Jan 2 at 22:52
3
$begingroup$
@mbrig thanks! yeah, thinking about this: since this device definitely has user interface buttons, the ringing of keypresses and their timing might be a source of entropy, too.
$endgroup$
– Marcus Müller
Jan 2 at 22:56
2
$begingroup$
A digital circuit is only perfectly (or even ideally) deterministic as long as there's only one oscillator providing a basis for all the clocks. As soon as you have at least two crystals, it's highly nondeterministic, and you can exploit this for very high quality random seeds. May be overkill for a game, but it's a good principle to know.
$endgroup$
– R..
Jan 3 at 3:25
add a comment |
$begingroup$
Random Numbers and Computers
Let us talk a second about what it takes to generate random numbers.
Randomness is very easy for humans to imagine or produce: Flip a coin. The result is random. The next time you flip the same coin, it will be random again, and there will be no correlation to the previous coin-flips.
That's way harder for processors. These are machines to be as deterministic as possible. Generally, when you build a digital circuit, any non-determinism ("random behaviour") is undesired.
In that framework, i.e. if your digital circuit (e.g. an AVR) works perfectly deterministically, then there's simply no way to generate truly random numbers. These numbers must always be a result of some calculation on numbers that were there before, so that there can only be a "seemingly" random sequence of numbers.
The next time you feed the same algorithm with the same "inital input", you get the same sequence of numbers. We call an algorithm that generates a seemingly random numbers a pseudo-random number generator (PRNG).
But that is practically always (aside from cryptography) an acceptable solution. There's typically a large numbers of initial states, and if the PRNG is any good, any of these initial states will yield a totally different, totally uncorrelated, totally fairly distributed sequence of numbers.
Pseudo-random number generation on microcontrollers in practice
On a microcontroller, you don't want to use a function like rand or srand with a hidden global state of a single pseudo random number generator (PRNG) - that is a waste of the little RAM you have, if you at some point can stop using the PRNG, and a recipe for disaster if you're interacting with the PRNG from interrupt routines.
Instead, use a "slim" random number generator function that takes and modifies an explicit, small state. The AVR stdlib possibly offers rand_r, but that's just a bad random number generator; with the same effort in state space and computation, you can get much "randomer" numbers.
For medium-to-high-quality PRNG, I personally use my state-external variant of the XOROSHIRO128+ algorithm. It requires 16B of state memory, and is probably far over the top for a microcontroller-based game.
The XORSHIFT32 algorithm, that XOROSHIRO128+ is indirectly based on, only uses four bytes of state, and should be plenty random for your use case, and will return one 32bit random number each call, and modify the state. If you look at it, it's also pretty fast – just three shifts and three XORs on 32 bit numbers. While your AVR (assuming it's not AVR32) doesn't have 32 bit integers (I think), these operations should still be faster than at least what the glibc implementation of rand() does.
Seeding your PRNG
The real question is how to initialize the state (seed the PRNG). That seed determines the only seemingly random sequence of numbers that you'll get!
That is especially challenging on a small device like an AVR: You can't use something like the current time (which was always a bad seed, but someone started telling people it's good one :(, so people use that), because it has no notion of time; you can't use physically random things like the seek time of your hard drive, because there is no hard drive, and so on.
But: your microcontroller has an ADC, for example. So, simply get a series of ADC measurements and use the least significant bits, which should essentially be noise, to generate the initial state that you use for your PRNG. Maybe take an ADC measurement, XOR with the last measurement, shift up, take the next measurement, repeat 16 times, use that as initial state.
answered Jan 2 at 17:34
Marcus MüllerMarcus Müller
32.3k35894
$endgroup$
Random Numbers and Computers
Let us talk a second about what it takes to generate random numbers.
Randomness is very easy for humans to imagine or produce: Flip a coin. The result is random. The next time you flip the same coin, it will be random again, and there will be no correlation to the previous coin-flips.
That's way harder for processors. These are machines to be as deterministic as possible. Generally, when you build a digital circuit, any non-determinism ("random behaviour") is undesired.
In that framework, i.e. if your digital circuit (e.g. an AVR) works perfectly deterministically, then there's simply no way to generate truly random numbers. These numbers must always be a result of some calculation on numbers that were there before, so that there can only be a "seemingly" random sequence of numbers.
The next time you feed the same algorithm with the same "inital input", you get the same sequence of numbers. We call an algorithm that generates a seemingly random numbers a pseudo-random number generator (PRNG).
But that is practically always (aside from cryptography) an acceptable solution. There's typically a large numbers of initial states, and if the PRNG is any good, any of these initial states will yield a totally different, totally uncorrelated, totally fairly distributed sequence of numbers.
Pseudo-random number generation on microcontrollers in practice
On a microcontroller, you don't want to use a function like rand or srand with a hidden global state of a single pseudo random number generator (PRNG) - that is a waste of the little RAM you have, if you at some point can stop using the PRNG, and a recipe for disaster if you're interacting with the PRNG from interrupt routines.
Instead, use a "slim" random number generator function that takes and modifies an explicit, small state. The AVR stdlib possibly offers rand_r, but that's just a bad random number generator; with the same effort in state space and computation, you can get much "randomer" numbers.
For medium-to-high-quality PRNG, I personally use my state-external variant of the XOROSHIRO128+ algorithm. It requires 16B of state memory, and is probably far over the top for a microcontroller-based game.
The XORSHIFT32 algorithm, that XOROSHIRO128+ is indirectly based on, only uses four bytes of state, and should be plenty random for your use case, and will return one 32bit random number each call, and modify the state. If you look at it, it's also pretty fast – just three shifts and three XORs on 32 bit numbers. While your AVR (assuming it's not AVR32) doesn't have 32 bit integers (I think), these operations should still be faster than at least what the glibc implementation of rand() does.
Seeding your PRNG
The real question is how to initialize the state (seed the PRNG). That seed determines the only seemingly random sequence of numbers that you'll get!
That is especially challenging on a small device like an AVR: You can't use something like the current time (which was always a bad seed, but someone started telling people it's good one :(, so people use that), because it has no notion of time; you can't use physically random things like the seek time of your hard drive, because there is no hard drive, and so on.
But: your microcontroller has an ADC, for example. So, simply get a series of ADC measurements and use the least significant bits, which should essentially be noise, to generate the initial state that you use for your PRNG. Maybe take an ADC measurement, XOR with the last measurement, shift up, take the next measurement, repeat 16 times, use that as initial state.
answered Jan 2 at 17:34
Marcus MüllerMarcus Müller
32.3k35894
edited Jan 2 at 20:41
answered Jan 2 at 17:34
Marcus MüllerMarcus Müller
32.3k35894
answered Jan 2 at 17:34
Marcus MüllerMarcus Müller
32.3k35894
answered Jan 2 at 17:34
Marcus MüllerMarcus Müller
32.3k35894
32.3k35894
2
$begingroup$
The other semi-common trick for getting random numbers is from comparisons of different clock sources. The jitter between the main clock and the slow watchdog timer can be used as a source of "true" entropy (by sampling a fast counter every watchdog interrupt, or similar). Works well for AVRs, where even the very cheap ones have an independent watchdog IIRC.
$endgroup$
– mbrig
Jan 2 at 22:52
3
$begingroup$
@mbrig thanks! yeah, thinking about this: since this device definitely has user interface buttons, the ringing of keypresses and their timing might be a source of entropy, too.
$endgroup$
– Marcus Müller
Jan 2 at 22:56
2
$begingroup$
A digital circuit is only perfectly (or even ideally) deterministic as long as there's only one oscillator providing a basis for all the clocks. As soon as you have at least two crystals, it's highly nondeterministic, and you can exploit this for very high quality random seeds. May be overkill for a game, but it's a good principle to know.
$endgroup$
– R..
Jan 3 at 3:25
add a comment |
2
$begingroup$
The other semi-common trick for getting random numbers is from comparisons of different clock sources. The jitter between the main clock and the slow watchdog timer can be used as a source of "true" entropy (by sampling a fast counter every watchdog interrupt, or similar). Works well for AVRs, where even the very cheap ones have an independent watchdog IIRC.
$endgroup$
– mbrig
Jan 2 at 22:52
3
$begingroup$
@mbrig thanks! yeah, thinking about this: since this device definitely has user interface buttons, the ringing of keypresses and their timing might be a source of entropy, too.
$endgroup$
– Marcus Müller
Jan 2 at 22:56
2
$begingroup$
A digital circuit is only perfectly (or even ideally) deterministic as long as there's only one oscillator providing a basis for all the clocks. As soon as you have at least two crystals, it's highly nondeterministic, and you can exploit this for very high quality random seeds. May be overkill for a game, but it's a good principle to know.
$endgroup$
– R..
Jan 3 at 3:25
2
2
$begingroup$
The other semi-common trick for getting random numbers is from comparisons of different clock sources. The jitter between the main clock and the slow watchdog timer can be used as a source of "true" entropy (by sampling a fast counter every watchdog interrupt, or similar). Works well for AVRs, where even the very cheap ones have an independent watchdog IIRC.
$endgroup$
– mbrig
Jan 2 at 22:52
$begingroup$
The other semi-common trick for getting random numbers is from comparisons of different clock sources. The jitter between the main clock and the slow watchdog timer can be used as a source of "true" entropy (by sampling a fast counter every watchdog interrupt, or similar). Works well for AVRs, where even the very cheap ones have an independent watchdog IIRC.
$endgroup$
– mbrig
Jan 2 at 22:52
3
3
$begingroup$
@mbrig thanks! yeah, thinking about this: since this device definitely has user interface buttons, the ringing of keypresses and their timing might be a source of entropy, too.
$endgroup$
– Marcus Müller
Jan 2 at 22:56
$begingroup$
@mbrig thanks! yeah, thinking about this: since this device definitely has user interface buttons, the ringing of keypresses and their timing might be a source of entropy, too.
$endgroup$
– Marcus Müller
Jan 2 at 22:56
2
2
$begingroup$
A digital circuit is only perfectly (or even ideally) deterministic as long as there's only one oscillator providing a basis for all the clocks. As soon as you have at least two crystals, it's highly nondeterministic, and you can exploit this for very high quality random seeds. May be overkill for a game, but it's a good principle to know.
$endgroup$
– R..
Jan 3 at 3:25
$begingroup$
A digital circuit is only perfectly (or even ideally) deterministic as long as there's only one oscillator providing a basis for all the clocks. As soon as you have at least two crystals, it's highly nondeterministic, and you can exploit this for very high quality random seeds. May be overkill for a game, but it's a good principle to know.
$endgroup$
– R..
Jan 3 at 3:25
add a comment |
$begingroup$
From the AVR Libc Reference Manual, under stdlib.h: General utilities:
Function
rand():
int rand(void)
The
rand()function computes a sequence of pseudo-random integers in
the range of0toRAND_MAX(as defined by the header file
<stdlib.h>).
The
srand()function sets its argument seed as the seed for a new
sequence of pseudo-random numbers to be returned byrand(). These
sequences are repeatable by callingsrand()with the same seed
value.
If no seed value is provided, the functions are automatically seeded
with a value of1.
In compliance with the C standard, these functions operate on int
arguments. Since the underlying algorithm already uses 32-bit
calculations, this causes a loss of precision. Seerandom()for an
alternate set of functions that retains full 32-bit precision.
Basically, you want to use srand() to set a seed for rand() to use. rand() will generate the numbers based on the seed srand() provides.
A common way to get a seed for srand() is to use a timer that is based on some user action so you get a fairly unique sequence every time. If you don't change the seed, the number sequence will always be the same.
edited Jan 2 at 18:03
Marcus Müller
32.3k35894
answered Jan 2 at 15:58
evildemonicevildemonic
1,930618
$endgroup$
2
$begingroup$
@EugeneSh. This is why I specified based on user action. Since the OP is talking about a game, I doubt they need super true authentic random. If so, yes, using for instance an ADC value reading the noise on a diode or something could be better.
$endgroup$
– evildemonic
Jan 2 at 16:27
1
$begingroup$
I appreciate you folks helping me improve my answer, and bring you up good points. Since this is a game, there should be user action at some point, and this can perhaps be 'forced' early on. The seed can be generated at any point before the random number is needed. Something as simple as timing how long it takes for the player to enter their name, or select an option from the opening menu. Without more input from the OP, it is hard to speculate on what they need and what we have to work with.
$endgroup$
– evildemonic
Jan 2 at 16:35
1
$begingroup$
I'll be honest: on a programmer's website (such as stackexchange.com), the recommendation to userandandsrandwould be worth a very comprehensive comment on why that is a very bad idea. These functions aren't reentrant-save, so interaction with their state from ISRs or multiple tasks is potentially catastrophic. If I was AVR, I'd honestly not include these functions. The way to go is not a random number generator with hidden global state, especially not on a microcontroller.
$endgroup$
– Marcus Müller
Jan 2 at 17:14
1
$begingroup$
@MarcusMüller The re-entrant version of rand() is rand_r(). I'm not sure it is needed. I'm also not sure I follow you on why it would be a very bad idea to use rand() like this on an AVR or how it would be catastrophic unless you need to reproduce the sequence and haven't been careful about how you use it. Is there something inherent to hidden global states that make them inappropriate for microcontrollers?
$endgroup$
– evildemonic
Jan 2 at 17:32
1
$begingroup$
@evildemonic well, first of all, you kind of need to allocate some space somewhere when using therandfunction, forever. That might be highly problematic on memory-starved architectures. So, you'd always go forrand_r, simply because then you / your compiler is in charge of knowing when you don't need that anymore; then, OK, this is a game, and truly random would not be a problem here, but in general, when using a PRNG likerandyou can't accept RNG behaviour.
$endgroup$
– Marcus Müller
Jan 2 at 17:38
|
show 4 more comments
$begingroup$
From the AVR Libc Reference Manual, under stdlib.h: General utilities:
Function
rand():
int rand(void)
The
rand()function computes a sequence of pseudo-random integers in
the range of0toRAND_MAX(as defined by the header file
<stdlib.h>).
The
srand()function sets its argument seed as the seed for a new
sequence of pseudo-random numbers to be returned byrand(). These
sequences are repeatable by callingsrand()with the same seed
value.
If no seed value is provided, the functions are automatically seeded
with a value of1.
In compliance with the C standard, these functions operate on int
arguments. Since the underlying algorithm already uses 32-bit
calculations, this causes a loss of precision. Seerandom()for an
alternate set of functions that retains full 32-bit precision.
Basically, you want to use srand() to set a seed for rand() to use. rand() will generate the numbers based on the seed srand() provides.
A common way to get a seed for srand() is to use a timer that is based on some user action so you get a fairly unique sequence every time. If you don't change the seed, the number sequence will always be the same.
edited Jan 2 at 18:03
Marcus Müller
32.3k35894
answered Jan 2 at 15:58
evildemonicevildemonic
1,930618
$endgroup$
2
$begingroup$
@EugeneSh. This is why I specified based on user action. Since the OP is talking about a game, I doubt they need super true authentic random. If so, yes, using for instance an ADC value reading the noise on a diode or something could be better.
$endgroup$
– evildemonic
Jan 2 at 16:27
1
$begingroup$
I appreciate you folks helping me improve my answer, and bring you up good points. Since this is a game, there should be user action at some point, and this can perhaps be 'forced' early on. The seed can be generated at any point before the random number is needed. Something as simple as timing how long it takes for the player to enter their name, or select an option from the opening menu. Without more input from the OP, it is hard to speculate on what they need and what we have to work with.
$endgroup$
– evildemonic
Jan 2 at 16:35
1
$begingroup$
I'll be honest: on a programmer's website (such as stackexchange.com), the recommendation to userandandsrandwould be worth a very comprehensive comment on why that is a very bad idea. These functions aren't reentrant-save, so interaction with their state from ISRs or multiple tasks is potentially catastrophic. If I was AVR, I'd honestly not include these functions. The way to go is not a random number generator with hidden global state, especially not on a microcontroller.
$endgroup$
– Marcus Müller
Jan 2 at 17:14
1
$begingroup$
@MarcusMüller The re-entrant version of rand() is rand_r(). I'm not sure it is needed. I'm also not sure I follow you on why it would be a very bad idea to use rand() like this on an AVR or how it would be catastrophic unless you need to reproduce the sequence and haven't been careful about how you use it. Is there something inherent to hidden global states that make them inappropriate for microcontrollers?
$endgroup$
– evildemonic
Jan 2 at 17:32
1
$begingroup$
@evildemonic well, first of all, you kind of need to allocate some space somewhere when using therandfunction, forever. That might be highly problematic on memory-starved architectures. So, you'd always go forrand_r, simply because then you / your compiler is in charge of knowing when you don't need that anymore; then, OK, this is a game, and truly random would not be a problem here, but in general, when using a PRNG likerandyou can't accept RNG behaviour.
$endgroup$
– Marcus Müller
Jan 2 at 17:38
|
show 4 more comments
$begingroup$
From the AVR Libc Reference Manual, under stdlib.h: General utilities:
Function
rand():
int rand(void)
The
rand()function computes a sequence of pseudo-random integers in
the range of0toRAND_MAX(as defined by the header file
<stdlib.h>).
The
srand()function sets its argument seed as the seed for a new
sequence of pseudo-random numbers to be returned byrand(). These
sequences are repeatable by callingsrand()with the same seed
value.
If no seed value is provided, the functions are automatically seeded
with a value of1.
In compliance with the C standard, these functions operate on int
arguments. Since the underlying algorithm already uses 32-bit
calculations, this causes a loss of precision. Seerandom()for an
alternate set of functions that retains full 32-bit precision.
Basically, you want to use srand() to set a seed for rand() to use. rand() will generate the numbers based on the seed srand() provides.
A common way to get a seed for srand() is to use a timer that is based on some user action so you get a fairly unique sequence every time. If you don't change the seed, the number sequence will always be the same.
edited Jan 2 at 18:03
Marcus Müller
32.3k35894
answered Jan 2 at 15:58
evildemonicevildemonic
1,930618
$endgroup$
From the AVR Libc Reference Manual, under stdlib.h: General utilities:
Function
rand():
int rand(void)
The
rand()function computes a sequence of pseudo-random integers in
the range of0toRAND_MAX(as defined by the header file
<stdlib.h>).
The
srand()function sets its argument seed as the seed for a new
sequence of pseudo-random numbers to be returned byrand(). These
sequences are repeatable by callingsrand()with the same seed
value.
If no seed value is provided, the functions are automatically seeded
with a value of1.
In compliance with the C standard, these functions operate on int
arguments. Since the underlying algorithm already uses 32-bit
calculations, this causes a loss of precision. Seerandom()for an
alternate set of functions that retains full 32-bit precision.
Basically, you want to use srand() to set a seed for rand() to use. rand() will generate the numbers based on the seed srand() provides.
A common way to get a seed for srand() is to use a timer that is based on some user action so you get a fairly unique sequence every time. If you don't change the seed, the number sequence will always be the same.
edited Jan 2 at 18:03
Marcus Müller
32.3k35894
answered Jan 2 at 15:58
evildemonicevildemonic
1,930618
edited Jan 2 at 18:03
Marcus Müller
32.3k35894
edited Jan 2 at 18:03
Marcus Müller
32.3k35894
edited Jan 2 at 18:03
Marcus Müller
32.3k35894
32.3k35894
answered Jan 2 at 15:58
evildemonicevildemonic
1,930618
answered Jan 2 at 15:58
evildemonicevildemonic
1,930618
answered Jan 2 at 15:58
evildemonicevildemonic
1,930618
1,930618
2
$begingroup$
@EugeneSh. This is why I specified based on user action. Since the OP is talking about a game, I doubt they need super true authentic random. If so, yes, using for instance an ADC value reading the noise on a diode or something could be better.
$endgroup$
– evildemonic
Jan 2 at 16:27
1
$begingroup$
I appreciate you folks helping me improve my answer, and bring you up good points. Since this is a game, there should be user action at some point, and this can perhaps be 'forced' early on. The seed can be generated at any point before the random number is needed. Something as simple as timing how long it takes for the player to enter their name, or select an option from the opening menu. Without more input from the OP, it is hard to speculate on what they need and what we have to work with.
$endgroup$
– evildemonic
Jan 2 at 16:35
1
$begingroup$
I'll be honest: on a programmer's website (such as stackexchange.com), the recommendation to userandandsrandwould be worth a very comprehensive comment on why that is a very bad idea. These functions aren't reentrant-save, so interaction with their state from ISRs or multiple tasks is potentially catastrophic. If I was AVR, I'd honestly not include these functions. The way to go is not a random number generator with hidden global state, especially not on a microcontroller.
$endgroup$
– Marcus Müller
Jan 2 at 17:14
1
$begingroup$
@MarcusMüller The re-entrant version of rand() is rand_r(). I'm not sure it is needed. I'm also not sure I follow you on why it would be a very bad idea to use rand() like this on an AVR or how it would be catastrophic unless you need to reproduce the sequence and haven't been careful about how you use it. Is there something inherent to hidden global states that make them inappropriate for microcontrollers?
$endgroup$
– evildemonic
Jan 2 at 17:32
1
$begingroup$
@evildemonic well, first of all, you kind of need to allocate some space somewhere when using therandfunction, forever. That might be highly problematic on memory-starved architectures. So, you'd always go forrand_r, simply because then you / your compiler is in charge of knowing when you don't need that anymore; then, OK, this is a game, and truly random would not be a problem here, but in general, when using a PRNG likerandyou can't accept RNG behaviour.
$endgroup$
– Marcus Müller
Jan 2 at 17:38
|
show 4 more comments
2
$begingroup$
@EugeneSh. This is why I specified based on user action. Since the OP is talking about a game, I doubt they need super true authentic random. If so, yes, using for instance an ADC value reading the noise on a diode or something could be better.
$endgroup$
– evildemonic
Jan 2 at 16:27
1
$begingroup$
I appreciate you folks helping me improve my answer, and bring you up good points. Since this is a game, there should be user action at some point, and this can perhaps be 'forced' early on. The seed can be generated at any point before the random number is needed. Something as simple as timing how long it takes for the player to enter their name, or select an option from the opening menu. Without more input from the OP, it is hard to speculate on what they need and what we have to work with.
$endgroup$
– evildemonic
Jan 2 at 16:35
1
$begingroup$
I'll be honest: on a programmer's website (such as stackexchange.com), the recommendation to userandandsrandwould be worth a very comprehensive comment on why that is a very bad idea. These functions aren't reentrant-save, so interaction with their state from ISRs or multiple tasks is potentially catastrophic. If I was AVR, I'd honestly not include these functions. The way to go is not a random number generator with hidden global state, especially not on a microcontroller.
$endgroup$
– Marcus Müller
Jan 2 at 17:14
1
$begingroup$
@MarcusMüller The re-entrant version of rand() is rand_r(). I'm not sure it is needed. I'm also not sure I follow you on why it would be a very bad idea to use rand() like this on an AVR or how it would be catastrophic unless you need to reproduce the sequence and haven't been careful about how you use it. Is there something inherent to hidden global states that make them inappropriate for microcontrollers?
$endgroup$
– evildemonic
Jan 2 at 17:32
1
$begingroup$
@evildemonic well, first of all, you kind of need to allocate some space somewhere when using therandfunction, forever. That might be highly problematic on memory-starved architectures. So, you'd always go forrand_r, simply because then you / your compiler is in charge of knowing when you don't need that anymore; then, OK, this is a game, and truly random would not be a problem here, but in general, when using a PRNG likerandyou can't accept RNG behaviour.
$endgroup$
– Marcus Müller
Jan 2 at 17:38
2
2
$begingroup$
@EugeneSh. This is why I specified based on user action. Since the OP is talking about a game, I doubt they need super true authentic random. If so, yes, using for instance an ADC value reading the noise on a diode or something could be better.
$endgroup$
– evildemonic
Jan 2 at 16:27
$begingroup$
@EugeneSh. This is why I specified based on user action. Since the OP is talking about a game, I doubt they need super true authentic random. If so, yes, using for instance an ADC value reading the noise on a diode or something could be better.
$endgroup$
– evildemonic
Jan 2 at 16:27
1
1
$begingroup$
I appreciate you folks helping me improve my answer, and bring you up good points. Since this is a game, there should be user action at some point, and this can perhaps be 'forced' early on. The seed can be generated at any point before the random number is needed. Something as simple as timing how long it takes for the player to enter their name, or select an option from the opening menu. Without more input from the OP, it is hard to speculate on what they need and what we have to work with.
$endgroup$
– evildemonic
Jan 2 at 16:35
$begingroup$
I appreciate you folks helping me improve my answer, and bring you up good points. Since this is a game, there should be user action at some point, and this can perhaps be 'forced' early on. The seed can be generated at any point before the random number is needed. Something as simple as timing how long it takes for the player to enter their name, or select an option from the opening menu. Without more input from the OP, it is hard to speculate on what they need and what we have to work with.
$endgroup$
– evildemonic
Jan 2 at 16:35
1
1
$begingroup$
I'll be honest: on a programmer's website (such as stackexchange.com), the recommendation to use
rand and srand would be worth a very comprehensive comment on why that is a very bad idea. These functions aren't reentrant-save, so interaction with their state from ISRs or multiple tasks is potentially catastrophic. If I was AVR, I'd honestly not include these functions. The way to go is not a random number generator with hidden global state, especially not on a microcontroller.$endgroup$
– Marcus Müller
Jan 2 at 17:14
$begingroup$
I'll be honest: on a programmer's website (such as stackexchange.com), the recommendation to use
rand and srand would be worth a very comprehensive comment on why that is a very bad idea. These functions aren't reentrant-save, so interaction with their state from ISRs or multiple tasks is potentially catastrophic. If I was AVR, I'd honestly not include these functions. The way to go is not a random number generator with hidden global state, especially not on a microcontroller.$endgroup$
– Marcus Müller
Jan 2 at 17:14
1
1
$begingroup$
@MarcusMüller The re-entrant version of rand() is rand_r(). I'm not sure it is needed. I'm also not sure I follow you on why it would be a very bad idea to use rand() like this on an AVR or how it would be catastrophic unless you need to reproduce the sequence and haven't been careful about how you use it. Is there something inherent to hidden global states that make them inappropriate for microcontrollers?
$endgroup$
– evildemonic
Jan 2 at 17:32
$begingroup$
@MarcusMüller The re-entrant version of rand() is rand_r(). I'm not sure it is needed. I'm also not sure I follow you on why it would be a very bad idea to use rand() like this on an AVR or how it would be catastrophic unless you need to reproduce the sequence and haven't been careful about how you use it. Is there something inherent to hidden global states that make them inappropriate for microcontrollers?
$endgroup$
– evildemonic
Jan 2 at 17:32
1
1
$begingroup$
@evildemonic well, first of all, you kind of need to allocate some space somewhere when using the
rand function, forever. That might be highly problematic on memory-starved architectures. So, you'd always go for rand_r, simply because then you / your compiler is in charge of knowing when you don't need that anymore; then, OK, this is a game, and truly random would not be a problem here, but in general, when using a PRNG like rand you can't accept RNG behaviour.$endgroup$
– Marcus Müller
Jan 2 at 17:38
$begingroup$
@evildemonic well, first of all, you kind of need to allocate some space somewhere when using the
rand function, forever. That might be highly problematic on memory-starved architectures. So, you'd always go for rand_r, simply because then you / your compiler is in charge of knowing when you don't need that anymore; then, OK, this is a game, and truly random would not be a problem here, but in general, when using a PRNG like rand you can't accept RNG behaviour.$endgroup$
– Marcus Müller
Jan 2 at 17:38
|
show 4 more comments
$begingroup$
The other answers are more theoretical, but I have done some practical experiments in this area.
Using an AVR XMEGA microcontroller I sampled the internal temperature sensor continuously with the ADC. From each reading I took only the least significant bit, which is subject to the most noise. I then combined 8 such bits and fed them into the on-board CRC generator, using one byte of its output as my random bits. The CRC generator was just a fast, convenient way of mixing and whitening the bits, other methods work too.
This code implements it: https://github.com/kuro68k/xrng/blob/master/firmware2/xrng/rng.c
I did extensive testing of the output. Even generating 8+ megabits per second the output does will with standard randomness tests, including DieHarder.
For your purposes this is probably overkill. Unfortunately you don't mention which AVR you are using, but most only have a 10 bit ADC (the XMEGA is 12 bit) and often lack an internal temperature sensor. However, using just 10 bits and sampling the internal voltage reference, or a floating (disconnected) pin you may get decent results. I'd suggest collecting 16 bits (16 samples, take only the least significant bit) and combining them into a 16 bit word, and then repeating that 16 times with the results XORed together, and then feed the result to the srand() function. Then periodically take another 16 samples, XOR and feed into srand() again.
Then you can just use the normal rand() function to get random numbers. By seeding it with a half decent source of entropy the results should be sufficiently unpredictable for your game.
Alternatively, some AVRs have a watchdog timer that can trigger an interrupt. The watchdog timer is a fairly decent random number generator because it's frequency varies randomly, so you can just set up a fast timer (clock divider 1, maximum core clock frequency) and sample the least significant bit every time the watchdog interrupt is triggered. I believe other people have tested that method and found it to be a good source of entropy.
answered Jan 3 at 11:55
useruser
1,244616
$endgroup$
add a comment |
$begingroup$
The other answers are more theoretical, but I have done some practical experiments in this area.
Using an AVR XMEGA microcontroller I sampled the internal temperature sensor continuously with the ADC. From each reading I took only the least significant bit, which is subject to the most noise. I then combined 8 such bits and fed them into the on-board CRC generator, using one byte of its output as my random bits. The CRC generator was just a fast, convenient way of mixing and whitening the bits, other methods work too.
This code implements it: https://github.com/kuro68k/xrng/blob/master/firmware2/xrng/rng.c
I did extensive testing of the output. Even generating 8+ megabits per second the output does will with standard randomness tests, including DieHarder.
For your purposes this is probably overkill. Unfortunately you don't mention which AVR you are using, but most only have a 10 bit ADC (the XMEGA is 12 bit) and often lack an internal temperature sensor. However, using just 10 bits and sampling the internal voltage reference, or a floating (disconnected) pin you may get decent results. I'd suggest collecting 16 bits (16 samples, take only the least significant bit) and combining them into a 16 bit word, and then repeating that 16 times with the results XORed together, and then feed the result to the srand() function. Then periodically take another 16 samples, XOR and feed into srand() again.
Then you can just use the normal rand() function to get random numbers. By seeding it with a half decent source of entropy the results should be sufficiently unpredictable for your game.
Alternatively, some AVRs have a watchdog timer that can trigger an interrupt. The watchdog timer is a fairly decent random number generator because it's frequency varies randomly, so you can just set up a fast timer (clock divider 1, maximum core clock frequency) and sample the least significant bit every time the watchdog interrupt is triggered. I believe other people have tested that method and found it to be a good source of entropy.
answered Jan 3 at 11:55
useruser
1,244616
$endgroup$
add a comment |
$begingroup$
The other answers are more theoretical, but I have done some practical experiments in this area.
Using an AVR XMEGA microcontroller I sampled the internal temperature sensor continuously with the ADC. From each reading I took only the least significant bit, which is subject to the most noise. I then combined 8 such bits and fed them into the on-board CRC generator, using one byte of its output as my random bits. The CRC generator was just a fast, convenient way of mixing and whitening the bits, other methods work too.
This code implements it: https://github.com/kuro68k/xrng/blob/master/firmware2/xrng/rng.c
I did extensive testing of the output. Even generating 8+ megabits per second the output does will with standard randomness tests, including DieHarder.
For your purposes this is probably overkill. Unfortunately you don't mention which AVR you are using, but most only have a 10 bit ADC (the XMEGA is 12 bit) and often lack an internal temperature sensor. However, using just 10 bits and sampling the internal voltage reference, or a floating (disconnected) pin you may get decent results. I'd suggest collecting 16 bits (16 samples, take only the least significant bit) and combining them into a 16 bit word, and then repeating that 16 times with the results XORed together, and then feed the result to the srand() function. Then periodically take another 16 samples, XOR and feed into srand() again.
Then you can just use the normal rand() function to get random numbers. By seeding it with a half decent source of entropy the results should be sufficiently unpredictable for your game.
Alternatively, some AVRs have a watchdog timer that can trigger an interrupt. The watchdog timer is a fairly decent random number generator because it's frequency varies randomly, so you can just set up a fast timer (clock divider 1, maximum core clock frequency) and sample the least significant bit every time the watchdog interrupt is triggered. I believe other people have tested that method and found it to be a good source of entropy.
answered Jan 3 at 11:55
useruser
1,244616
$endgroup$
The other answers are more theoretical, but I have done some practical experiments in this area.
Using an AVR XMEGA microcontroller I sampled the internal temperature sensor continuously with the ADC. From each reading I took only the least significant bit, which is subject to the most noise. I then combined 8 such bits and fed them into the on-board CRC generator, using one byte of its output as my random bits. The CRC generator was just a fast, convenient way of mixing and whitening the bits, other methods work too.
This code implements it: https://github.com/kuro68k/xrng/blob/master/firmware2/xrng/rng.c
I did extensive testing of the output. Even generating 8+ megabits per second the output does will with standard randomness tests, including DieHarder.
For your purposes this is probably overkill. Unfortunately you don't mention which AVR you are using, but most only have a 10 bit ADC (the XMEGA is 12 bit) and often lack an internal temperature sensor. However, using just 10 bits and sampling the internal voltage reference, or a floating (disconnected) pin you may get decent results. I'd suggest collecting 16 bits (16 samples, take only the least significant bit) and combining them into a 16 bit word, and then repeating that 16 times with the results XORed together, and then feed the result to the srand() function. Then periodically take another 16 samples, XOR and feed into srand() again.
Then you can just use the normal rand() function to get random numbers. By seeding it with a half decent source of entropy the results should be sufficiently unpredictable for your game.
Alternatively, some AVRs have a watchdog timer that can trigger an interrupt. The watchdog timer is a fairly decent random number generator because it's frequency varies randomly, so you can just set up a fast timer (clock divider 1, maximum core clock frequency) and sample the least significant bit every time the watchdog interrupt is triggered. I believe other people have tested that method and found it to be a good source of entropy.
answered Jan 3 at 11:55
useruser
1,244616
answered Jan 3 at 11:55
useruser
1,244616
answered Jan 3 at 11:55
useruser
1,244616
answered Jan 3 at 11:55
useruser
1,244616
1,244616
add a comment |
add a comment |
Thanks for contributing an answer to Electrical Engineering Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2felectronics.stackexchange.com%2fquestions%2f414867%2fhow-can-i-get-random-numbers-on-avr%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
Which AVR? Does it have a hardware random number generator, or an ADC?
$endgroup$
– Colin
Jan 2 at 15:37
6
$begingroup$
Here are four things I know about random numbers: 1) They're fiendishly hard to do 'really right'. 2) There are tons of well-documented algorithms on the Internet, there for the searching (hint, hint). 3) You can do an adequate job on a bitty little processor, particularly if it's for casual stuff like gaming. 4) I'm no expert beyond points 1, 2 & 3. Why don't you search, then tell us what you found and why you're either still confused or unhappy with your options? I suggest "good random number generator for gaming" as a starting point for your search.
$endgroup$
– TimWescott
Jan 2 at 15:40
8
$begingroup$
"I have tried something:" -- So what happened? That line of code doesn't look like it would even compile -- a function call (
random()) can't be an lvalue (for the operator&=).$endgroup$
– Dave Tweed♦
Jan 2 at 15:52
5
$begingroup$
This is a hard problem in general, so it's usually best to look at the specific need. What are the random numbers for? What else is going on? The early Simon electronic memory game for example used the low bits of a free running counter - technically the "random" patterns were determined by how long it took the user to push a button, but at a resolution which no human could recognize or game.
$endgroup$
– Chris Stratton
Jan 2 at 16:06
1
$begingroup$
One approach for creating a new seed for non-critical applications is to just use an incrementing number that is stored in an EEPROM location at every program invocation. E.g if the initial value is 1, the next time the code uses the seed it will be 2 etc. This then will create a different set of random numbers for every game but will be easy to to test as the code doesn't rely on any randomness from switches, timers etc.
$endgroup$
– Kevin White
Jan 3 at 0:17