How to generate random #'s
Electronegativity
Posts: 311
Hi everyone, I'm trying to figure out how to generate a table of random numbers with an SX.
Is it possible to simply read or copy the random values that the data registers initialize to?
Using the analog comparator on 2 RC circuits of different frequencies would probably generate effectively random bits, but there must be a better way.
Any ideas?
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I wonder if this wire is hot...
Is it possible to simply read or copy the random values that the data registers initialize to?
Using the analog comparator on 2 RC circuits of different frequencies would probably generate effectively random bits, but there must be a better way.
Any ideas?
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I wonder if this wire is hot...
Comments
Although I'm not going to give a good mathematical answer to your question, your idea of using the apparently random state of registers on power up is NOT a good idea. While those values may appear to be rendom, they generally, or at least often, are the same every time you boot. So not good randomness there.
I have not really studied this subject; there may be some good pointers in the SXList site.
If I needed random numbers, and it depends on the number of bits required, I would probably make a Pseudo Random Sequence Generator by simulating a sufficiently long shift resgister in software, and provide the appropriate feedback taps for the maximal configuration. This is pretty easy really. Google can probably get you there, and then you will need to do some experimentation.
Once I had that generator running, I would simply pick off a number when I needed one.
While this process may not be mathematically pure, or correct, I believe it will at least get you close.
Cheers,
Peter (pjv)
Here's the routine I got from the SxList:
;--------------------------------------------- ; 7/02/04 PJM - This function uses a linear congruential ; sequence generator as a pseudo-random number generator. RandomNumGen ;Rnew = Rold * 221 + 53 ;221 = 256 - 32 - 4 + 1 ;256 can be eliminated ;so we need to calculate Rnew = Rold * (1 - 32 - 4) + 53 using ;truncating arithmetic ;or Rnew = Rold * (-32 - 3) + 53 clrb C rl RandomNum ;RandomNum' = 2*RandomNum and carry contains the original MSb mov W, <>RandomNum and W, #$E0 ;W = 16*RandomNum'=32*RandomNum rr RandomNum ;restore RandomNum add W, RandomNum add W, RandomNum add RandomNum, W ;RandomNum'' = 32*RandomNum + 3*RandomNum not RandomNum ;RandomNum''' = 255-RandomNum'' = -1 - RandomNum'' mov W, #54 add RandomNum, W ;RandomNum''''=-1 - 32*RandomNum - 3*RandomNum + 54"RandomNum" is a variable (in this case it's a global variable) that holds the value of most recent random number generated between interations. Every time you call this routine, you'll update the value of "RandomNum". If you want to find the original, search for "congruential" on the SxList site. Make sure you go to the page with the SX code and not the PIC code.
Thanks, PeterM
; seed = seed * 5 + 123
Random
· MOV W,·seed
· ADD seed, W················
· ADD seed, W·················
· ADD seed, W················
· ADD seed, W·················
· ADD seed, #123
· RETP
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Jon Williams
Applications Engineer, Parallax
I still need a way to generate a random seed though, or add some non-volatile memory to hold the current value of RandomNum when the device is shut off.
When I get home I am going to try using the analog comparator with no input on either pin.
At worst case I can have a ADC digitize accross a range that exceeds its sensitivity and read the least significant bit.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I wonder if this wire is hot...
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
The problem with stuff like the zener noise is that the noise has to fluctuate randomly above and below the TTL or CMOS voltage threshold.
If I can come up with an elegant hardware solution I'll report back
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I wonder if this wire is hot...
Thanks!
John Gjonola
I hooked up the 4MHz oscillator that came with the SX Tech KIT to 2 of the pins on an SX18, with one pin configured to input and the other to output. The SX is clocked at just above or below 4MHz Using one of the IRC_CAL directives. (I'm not sure which will work better yet.
The output pin kicks the clock to start it running and the input pin polls the signal.
From the SX temporal reference frame the resonator output will appear as a slowly varying sine wave with a frequency equal to the difference between the actual clock speed and 4.00MHz.
I believe that if you were to poll the input pin at full speed you would see a bunch of 1's in a row followed by a few random bits, then a bunch of zeros in a row followed by a few random bits and back to 1's again.
The period of randomness occurs when the oscillator voltage is very close to the CMOS threshold (2.5V), making it difficult for the SX to decide if the value is high or low.
I plan to set a voltage transition interrupt on the pin to mark the point at which the oscillator output crosses the CMOS threshold, and then poll at a frequency that enables me to repeatedly sample the oscillator output when it is very close to the 2.5V portion of its phase.
This will be done in software by a calibration routine that "wastes" progressively more time between polling events until a predefined criteria for randomness is met. Since in the long term the polling rate would surely walk off the transition into the high or low regions, I plan to generate the random numbers one byte at a time with each determination initiated by a transition interrupt.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I wonder if this wire is hot...
<edit> If you want a simple method that is computationally simple, get a large capacity SD/MMC card, fill it up with numbers from www.random.org and have the SX indicate when it has used up the number set so you can fill it with another set of numbers
For cryptography purposes, it is a misnomer to say you want a true random number generator, a true random number generator is not reproducable, meaning objects encrypted by true randomness cannot be decoded by anyone including the machine that encrypted it. </edit>
<edit level 2> Link to patent on lava lamp random seed generator fixed since it was a session enabled link, click on "Images" button to see actual patent. I will check back later to see if the new link is also session enabled. </edit level 2>
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
Post Edited (Paul Baker) : 10/5/2005 3:36:46 PM GMT
The short story is that if you generate two simultaneous photons from the same source they will have the same phase at a later time regardless of the paths traveled. The phase of a photon can be rendered completely random by repeated scattering events.
Here's the encryption scheme:
A central source generates two phase-entangled photons and sends one to each of our computers down their respective optical cables. The phase of the photons are randomized by scattering in the cable, but are measured to be the same by ploarizers at the point where the photons reach our computers.
We use the phase of the photon as an encryption key.
This effectively creates 2 identical private keys for RSA encryption without the need of a public key, and nothing, not even the source that generated the photons, could predict what the phase would be at the time of measurement.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I wonder if this wire is hot...
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com
That sounds like it might be a better idea then what I am doing since it uses only one pin and doesn't require elaborate timing.
The unfortunate thing about both methods is that you have to waste a a lot of time waiting for the signal level to be near the logical voltage threshold and then only get a few random bits.
What if we set an input pin for CMOS level and then piped in Vdd/2 from a voltage divider?
I suppose it would be a little over or under Vdd/2 because of the resistor tolerances, but it may be close enough.
Maybe adding a bit of ringing from something like a ground bounce or coupling unlike inductors in series would mess the signal up enough that we could read random bits at will.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I wonder if this wire is hot...
Another idea would be to hook up the comarator with direct positive feedback from the output to (+), and with (-) at V//2. The propagation delay in the comparator makes it oscillate with lots of jitter at around 40 mhz. In any case, sampling the comparator output would be a pretty fair Smile shoot.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com
I will try feeding in the input from a voltage divider when I get home.
As far as pushing the pin off the threshold when it's not in use for noise detection, a transistor could control the voltage into the noisemaker so it can be turned off when not in use.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I wonder if this wire is hot...
With the comparator hooked up to nothing it actually generates pretty random bits, but it seems to favor 0 a little over 1.
I have the port A registers attached to 4 diodes and am sampling the comparator output with the following code:
GetNumber
sb rb.0
jmp BlueGreen
jmp RedYellow
BlueGreen
sb rb.0
jmp Blue
jmp Green
RedYellow
sb rb.0
jmp Red
jmp Yellow
Blue
mov LIT, #%0001
ret
Red
mov LIT, #%0010
ret
Green
mov LIT, #%0100
ret
Yellow
mov LIT, #%1000
ret
After returning it moves the value in LIT to ra and lights whatever diode corresponds to the bit that is set.
The favoritism of zero over one manifests itself as the blue diode being lit a little bit more than the others.
Grounding one of the two comparator inputs will consistently cause it to choose the other input as high.
Now here's the odd part:
When I momentarily tap Vdd to pin rb.2 (through a resistor) it correctly lights the yellow diode, but then it stays lit for about 24 seconds before returning to semi-randomness. This is at 4Mhz with the SX key detached.
It takes longer for slower clock speeds out to around 38 seconds at 32kHz.
If I tap rb.2 with Vdd/2, it stays lit for about half the time before rb.0 starts flickering again.
Just in case you thought this couldn't get any more bizzarre, when I tap rb.3 with Vdd/2 the comparator output goes to zero and stays there indefinitely.
I have attached the rest of the code.
The circuit is nothing more than an SX18AC/75 powered by an L7805 and Guenther's recommended capacitance circuit (without the back EMF protection diodes). There is also a programming header and 4 diodes hooked up to the ra register. with a 570 ohm resistor on the ground side to keep them from frying. The voltage divider is constructed from 2 4.7k resistors, and there is a 10k resistor plugged into Vdd.
-Electronegativity signing off.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I wonder if this wire is hot...
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
The comparator can be made into a high frequency oscillator, by connecting a wire from RB0 to RB1, and by connecting RB2 to a medium voltage. That could be ~Vdd/2 from a potentiometer between Vdd and Vss. The oscillator frequency is determined by the comparator propagation delay. It has lots of jitter and probably 1/f noise and temperature dependence too. It would be like having a madman sitting there pushing a button. The program could sample that occasionally to get random bits or to spice up a psuedo random sequence.
I looked back at some old notes, reported in this thread,
http://forums.parallax.com/showthread.php?p=521238
and the period of the oscillation was around 40 nanoseconds on a 5 volt supply, an oscillation frequency of around 25 megahertz. The period is determined by the two propagation delays, how long it stays in the "1" state vs how long in the "0" state.
-- The ratio of high to low is affected by the threshold applied to RB2 and becomes highly asymmetric if the potentiometer takes the rb2 threshold near Vss or Vdd. One way to equalize 1s and 0s would be to feed the oscillator output into the RTCC and sample the /2 bit of that. Or there may be some way to equalize in software like Paul suggested.
-- A program sampling at anywhere near the 40nS period could run into serious aliasing problems. But for occasional samples (at more than 10 microsecond apart, say), the statistical correlation should drop practically to zero.
Another way to use the comparator, instead of a direct wire connection from rb0 to rb1, would be a high value resistor (~1M) there. That more gentle negative feedback should bias the comparator as an op amp without the oscillation. Couple in an intrinsic or external noise source, and it would be amplified up to digital level for sampling.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com
Paul, that is a reasonable suggestion but it would make it difficult to port the code from one chip to the next since I suspect that each chip would require a slightly different transform, and even within a given chip the local temperature and electromagnetic environments could affect the weighting towards 1 or 0.
Tracy, there is nothing connected to any of the comparator pins. rb.1 and rb.2 are initialized as inputs and set low.
rb.0 is initialized as an output, set low, and is configured to output the comparator value.
I will try your oscillating comparator trick when I get home.
Does anyone have a clue why the strange behavior I described at the end of my last post occurs?
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I wonder if this wire is hot...
Tracy's "Madman circuit proved more random than leaving the comparator pins open, and seened to improve a bit further by using a lower voltage on pin rb.2, but showed a slight favoritism of 1 over zero.
This could probably be cleaned up nicely by Paul's binomial stochastic transform.
Whenever the device resets it could run a calibration cycle where it samples a large number of bits and determines the proper number of high or low results to throw away.
If using up 3 valuable pins on port B is a problem then the madman circuit can be connected or disconnected by a transistor that is actuated from one of the port A pins.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I wonder if this wire is hot...
Sampling it rapidly would lead to aliasing with the processor clock. The longer the program waits between sample bits, the less the correlation between them.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com
Even as it is it's good enough to generate a sufficently random seed values.
One could easily imagine a Psuedo-random generator that used 3 or 4 variables that were all randomly seeded.
Good enough for game purposes, but maybe not aerospace engineering
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I wonder if this wire is hot...
There is a simple way to avoid having to normalize the data for a process that favors either zero or one.
You collect 2 bits in a row.
If they are both positive or both negative you throw them out and collect 2 more bits.
If the first one is negative and the second positive then the result is zero.
If the first one is positive and the second one is negative then the result is one.
I think this will yield random bits even for a semi random system that is more likely on the average to be high or low.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I wonder if this wire is hot...
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·1+1=10
Post Edited (Paul Baker) : 10/10/2005 8:03:12 PM GMT
Yes, that is true, and I realized it when I came up with the algorithm, but I think it works if you poll at a rate which is slower than and asynchronous to the rate at which the bits are generated.
Tracey estimated that the comparator would oscillate at ~40 Mhz. I am clocking the SX at 32kHz and not even sampling every cycle.
The logic is as follows:
Imagine a source that generates more zeros than ones.
This could happen if the crossover point of a sinusoidal voltage is lower than the logical transition voltage.
In this case the sine wave would spend most of its time below the transition threshold and only occasionally peep above into the region corresponding to a one.
If you sample a source like the one above at a rate which is slower than and asynchronous to the period of the sine wave you would get a lot of zeros and a smattering of randomly distributed ones.
Applying the "two-bit" algorithm to a case in which nine times as many zeros as ones are randomly generated would have the following effect.
81% of the time you would get two zeros in a row and discard the result.
1% of the time you woulg get 2 ones in a row and discard the result.
9% of the time you would get first a zero then a one (90% X 10%) = 0.
9% of the time you would get first a one then a zero (10% X 90%) = 1.
I have it up and running on a breadboard at home and at least to my eye it appears perfectly random.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I wonder if this wire is hot...
You mention that you have it wired up and running, and it appears random to your eye. Well, take your eye out of the loop and let a computer tell you if you have a random number generator or not. On your testbed, add some RS-232 code (and whatever level shifting hardware you need) and have your testbed send the values from the random number generator to your PC. On the PC side, write a small program to receive the numbers from the SX and create a histogram from them.
The program is pretty much dead simple - for each number that comes in, use it as an index into an array of 32 bit integers which you increment. Run the program for some finite length of time. For example, try running the program for a minute, ten minutes, and an hour. Better yet, use the data rate to calculate a number of samples that takes close to those times to collect, but which is evenly divisible by 256.
At the end of each run, have the program write out a simple comma or tab delimited text file of the final value of each entry in the array. You can now open that text file into Excel and do things like graph it, or calculate the min, max, and mean values, etc, etc. Since you have collected a number of samples evenly divisible by 256, you should have (theoretically) the same value in each of your PC's array entries. If not, you can see which way you are weighted.
Thanks, PeterM
PS - I did something similar to this to verify that the pseudo-random number generators on SxList.com provided an even distribution.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
---
James Newton, Host of SXList.com
james at sxlist,com 1-619-652-0593 fax:1-208-279-8767
SX FAQ / Code / Tutorials / Documentation:
http://www.sxlist.com Pick faster!
I was recalling fuzzily. The comparator with direct feedback oscillates with a period of about 40 microseconds, a frequency of around 25 megahertz. What do you plan to do with the inductors to make it more chaotic?
Donald Knuth's volume, "Seminumerical Algorithms", goes into great depth on different random number generators and statistical tests that they should pass. The introductory lesson that sticks in my mind is, paraphrased, " never choose a random number algorithm randomly".
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com
As long as the user cannot perceive any divergence from randomness it is good enough.
James, even if the Pseudo-random code is perfect I still need to generate a random seed or the colors will always be the same. I know I could have the user press a button and read a seed value of the RTCC, but I want them to be able to start a new game by pressing only a single reset button instead of having to reset and then press a second button.
Tracey, my plan was to randomly choose a random number generator.
I figured that by slapping enough mismatched inductors and capacitors together I could build something completely chaotic.
I don't think I will need to do that though, since your oscillating capacitor idea can be implemented here in a very simple way.
I can bridge rb.0 and rb.1 with the emitter and collector of a transistor. The base is hooked up to ra.3.
Rb.0 and rb.1 are also hooked up to blue diodes, while rb.2 is attached to a red diode. When ra.3 turns on the transistor it sets up the oscillation of the comparator.
The "marginal voltage" on rb.2 is supplied by the fact that there is a higher forward voltage drop accross the blue diodes than the red. Once the table of random numbers is generated, I drop the voltage on ra.3 which disconnects the bridge. In this way I can use your method without using up any pins at all since ra.3 is subsequently set as an input and used to read a button.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I wonder if this wire is hot...
Try it?
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
---
James Newton, Host of SXList.com
james at sxlist,com 1-619-652-0593 fax:1-208-279-8767
SX FAQ / Code / Tutorials / Documentation:
http://www.sxlist.com Pick faster!
I figured that since you wanted a true random number generator, you needed to be sure it was truly random. Since you're just making a game, any old psuedo-random number generator will be more than adequate. You're killing yourself with all this extra effort.
James' suggestion will work fine, but can be made even better. Run a pseudo-random number generator in the RTCC. Assuming a reasonably fast interrupt rate, you will be generating hundreds or thousands of random numbers per second. Whenever the user presses a button to start a new game, there's basically no way they will ever be accurate enough to predictably get the same random seed each time. I used this exact technique on a project and it works great.
Thanks, PeterM