My arduino project has to perform a lot of computations and I have plans to expand it further, so to get a better understanding of the hardware can do I spent some time last night taking a look at the speed of my code. I was pleasantly surprised but began wondering what the easy and obvious optimizations might be.
To make a long story short, I found out that half my execution time was spent generating random numbers, because I was naively using arduino's random() function, which I discovered -- oh, my god -- appears to be the C standard library's random function. Which, according to its man page, is designed for cryptographic suitability and which carries a HUGE overhead both in terms of code space and execution time. ("With 256 bytes of state information, the period of the random number generator is greater than 2**69 which should be sufficient for most purposes.") Cool.
Forget all that, I just want kind-of random. But I'm using all six sensor inputs, so the obvious solution of taking an analog reading is out.
I have a hunch I can throw together some sort of "entropy pool" by taking recent sensor readings and xoring them together somehow so that it at least appears random or chaotic, but I know this is a serious topic in math and computer science so I'm hoping somebody can give me quick schooling on how I might best approach this.
(Seriously, linking to the C standard library for random numbers? And here I am, feeling deprived of printf and malloc... )
The millis function returns the length of time since the Arduino started. You could use a mask and just get the last 4 bits, if you're are looking for a small random number.
Quick and sort of random.
You can do a quick and dirty random number generator by utilising a shift register and feedback function. Implement a 32 bit shift register (just an unsigned int) look at the two most significant bits and xor them together, shift the int to the left and make the least significant bit the same as the result from the xor. Do this say 20 times and then the int will be your random number. Mask off bits with an AND function to restrict the range.
The deadbeef generator worked for my application:
I just want kind-of random
When choosing a pseudo-random number generator, it's all about purpose. High quality generators are needed for cryptography. Low quality generators are needed for cool LED displays. Most folks need something in the middle.
How will you be using your random numbers?
There could be some very simple and fast ways to get semi-random numbers, perhaps reading of a few lower bits of the millis() value, etc.
So what range of numbers do you require, i.e. 0-9, 0-255, 0-million?
How often do you need to aquire a new random number?
There could be some very simple and fast ways to get semi-random numbers, perhaps reading of a few lower bits of the millis() value
I suspect that this a bad idea for some simple Arduino applications. Hopefully I can get the stuff out of my brain into something understandable...
The first problem is if loop takes less than 1ms. The lower bits of millis will sometimes be the same.
The second problem is if loop takes an even multiple of milliseconds (say 10ms). The "random" number will have a very noticeable pattern. For something like a firefly application the result might be all the left side LEDs light then all the right side LEDs light then the ones in the middle. Over and over.
Third, even if loop takes an "odd" amount of time to run, the "random" number can still have a noticeable pattern. All it takes is for loop's execution time to have a common denominator with the millis clock.
Finally, I suspect most Arduino applications have a loop that runs in a relatively short amount of time. It's very likely that each pass through loop, the "random" values will increase a bit, increase a bit, increase a bit, then drop off.
Using micros instead of millis will give better results but will suffer from some of the same problems.
This brings up a good topic of discussion: What random number generator(s) should be used instead of random? Or is it worth discussing?
The lower bits of millis will sometimes be the same.
Ok, and duplicate numbers will sometimes be generated in any random number generator.
It just brings me back decades ago when I use to fool around with a mini-computer at work in the 70s. I would front panel input (loved those old front panels) simple little programs that would do stupid things. When we wanted crude semi-random numbers for say a slot machine game, we would use a free running counter's lower four hits and rely on human (latency) keyboard entry (hit any key) for when to capture a small number on the fly.
A counter running at hundreds of KHZ, where a player might hit any key once every second or more, the lower 4 bits are bound to be pretty random. It worked OK for the purpose and didn't pretend to be a robust PRN generator. Damn program didn't pay off any better then the Reno machines.