Could you elaborate on that I can't make sense of it?
Are you saying that adding a waitcnt(0) prior to running cessnapilots random number generator always gives the same result. If so that is what I would expect as the code is now synched to the counter.
What cessnapilot seems to be saying is that there is no such sync happening from reset naturally. Which is a bit odd to me and implies the clock counter is never reset.
Are you saying that adding a waitcnt(0) prior to running cessnapilots random number generator always gives the same result. If so that is what I would expect as the code is now synched to the counter.
That's not quite enough. cnt == 0 can happen at any of 16n+0..16n+15 (hub window). When you do a value := cnt this op is aliased to hub (always the same code sequence in the interpreter). Meaning just the waitcnt(0) will do what you want but reading cnt later snaps back to the hub grid. So what I did is run the test inside a repeat loop which preserves the hub alignment and placed the waitcnt(0) before the Start_Driver call. Which shows expected behaviour.
What cessnapilot seems to be saying is that there is no such sync happening from reset naturally. Which is a bit odd to me and implies the clock counter is never reset.
I only know about no reset during soft reset (it just keeps counting). Not sure about cold power up. That said, the video frame counter and the counter flip-flops (A1 and A2) are definitely not reset (after power on).
That's just an observation, I'm not judging the quality of the generator.
The basic premiss is that we want a real random number from somewhere at start up. Perhaps to seed a pseudo random number generator as in cessnapilot's case.
So, is it so that that the value of CNT is unpredictable when read at start up or not?
I would naturally assume that CNT is initialized to zero on cold or warm reset. Then as my code executes it increments to to some value that I read from CNT. I would assume that value is always the same.
Except:
1) If CNT is not reset on a warm reset. In which case it is as random as the timing of my reset.
2) Something else odd is going on during cold start that causes CNT to not be reset to zero but some other random number or there is some random delay between CNT counter starting and my code executing. Or both.
There is something here we need to know is there not?
OK, I checked (as in tested on real h/w). cnt is NOT initialised even after cold boot (power cycle). The manual actually states: The System Counter is not cleared upon startup since its practical use is for differential timing. So its behaviour is the same as for the video frame counter(s).
My point in #33 was that since you know it's cnt based you can force a specific sequence.
1) During a warm reset CNT just keeps rolling along and is not reset in any way. Strange but fair enough.
2) Just nit picking but during a cold restart the CNT counter sure is reset. After all it starts from a no power state i.e. all zeros.
Question is, then what happens? Do the flip flops of CNT just adopt some odd pattern at power up? Is there some analog process going on there that holds up program execution for a while with jittery results? Or both? Or what? How random can this be?
If we don't know the mechanism and it is not documented then we cannot rely on it.
2) Just nit picking but during a cold restart it the CNT counter sure is reset. After all it starts from a no power state i.e. all zeros.
It's based on flip-flops. If they are not explicitly reset then their initial state can be anything. As for cnt being reset, its top byte shows $Bx which is close to 4min at RCFAST. Very unlikely I'd say (assuming it starts at 0).
1. I'm aware of modulo bias, but when the seed is 32 bits and the range is 0 to 100, it hardly matters.
2. Regarding all that byte moving business: Yes, if the byte moving were being done one at a time in Spin code, it would be very inefficient. However, the Spin byte-code interpreter does the byte moving quickly enough that, compared to the speed of Spin itself, bytemove can be thought of as a single, native operation -- especially on small data sets. But, now that you point it out, simply swapping bytes at the ends of a segment would accomplish the same end as rotating the entire segment, which is what I did.
Istvan,
I had assumed (wrongly it now appears) that CNT was initialized to zero on startup, just like all the other SFRs. That now appears not to be the case. That leaves only the question of whether, for a given chip, the bits in CNT have probabilistically preferred states from power-up.
I had assumed (wrongly it now appears) that CNT was initialized to zero on startup, just like all the other SFRs. That now appears not to be the case. That leaves only the question of whether, for a given chip, the bits in CNT have probabilistically preferred states from power-up.
-Phil
Phil,
It took me some time to reboot the same chip with 120 times while documenting the results for the CNT. For that Propeller all bits except bit 28 were 0 or 1 with acceptable Head or Tail fashion. However bit 28 was notoriously zero.
With the add CNT then multiply with CNT method it means that for a given seed there will be more than 2 billion starting sequences (for that chip). A real code will invoke even more entropy by using CNT with an incoherent way, like waiting for a key-press, reading a serial line or an input pin from a sensor. With a few random bits at the start, then time entropy at the calls is enough to stir up any reproducible pattern.
Phil,
Quite so, it's a small bias introduced by the mod operator which most people most of the time would not notice or care about. Still it's there and may causes issues for serious random number users so it's good to be aware of it. I guess the Prop is unlikely to be used for such apps though.
Using string/block operations is quite efficient as you say, not sure how it pans out in this case. But the fisher-yates shuffle is a lot more elegant isn't it?
CessnaPilot,
Still haven't managed to check out the randomness of CNT on power up. I don't have a Prop board here that I can power cycle easily.
From the results you have I would be wary of using CNT as a source of randomness like that. As you say you have one "stuck" bit. Reducing the "randomness" by half. We cannot be sure how this works from chip to chip.
Because it would be great to get a random seed value at startup with just the use of CNT, I made some tests.
I've used this code:
VAR
long seed
OBJ
di : "FullDuplexSerial"
PUB Main
seed := cnt
di.start(31,30,0,105200)
waitcnt(clkfreq + cnt)
di.dec(seed)
di.tx(13)
repeat
This runs with RCfast and the odd baudrate value is to compensate the difference between 12MHz and the frequency of my test-chip. The code is in the EEPROM.
The Prop is connected through a PropPlug to show the values on the PropTerminal on my PC. If I remove the PropPlug and the power, then connect the PropPlug again and then power the board up, I get the following results:
There is always a increasing value in seed, no matter how long I wait until I connect the power again. So it seems that the PropPlug powers the Propeller enough to keep the value of the CNT flipflops, but CNT is not counting until the Prop is really powered up.
So you need to do the tests very carefully. And for me it seems the CNT register starts with nearly the same value each time you power the Propller up.
This is neat stuff. The random game theory is beyond me but i wrote a neat powerball picker based on the code posted in this thread. This implementation uses the PSM board from rayslogic.com. It could easily be built on any platform with tv out and one pushbutton. In fact the psm text driver is a drop in replacement for tv text if i recall correctly... good times.
Phil
Looks good but I wanted real random number so I included this object
obj
rand : "RealRandom"
and changed this line of code
j := ||?seed // (RANGE - i + 1) + i
with this
j := (rand.random >> 1) // (RANGE - i + 1) + i
So far its working ill need to do a lot of testing. Thanks
There is the code I use.
CON
_clkmode = xtal1 + pll16x
_xinfreq = 5_000_000
RANGE = 5 'Range is 0 to RANGE.
SAMPLES = 1 'Number of samples to pick: 1 to RANGE + 1
VAR
long seed
byte numbers[RANGE + 1]
OBJ
pst : "Parallax Serial Terminal"
rand : "RealRandom"
PUB start | i
pst.start(9600)
repeat 100
fill_array
pst.str(string("Samples: "))
repeat i from 0 to RANGE
pst.dec(numbers[i])
if (i == SAMPLES - 1)
pst.str(string(13, "Remainder: "))
else
pst.char(" ")
PUB fill_array | i, j, sample
repeat i from 0 to RANGE 'Fill numbers array in order.
numbers[i] := i
repeat i from 0 to SAMPLES - 1
j := (rand.random >> 1) // (RANGE - i + 1) + i 'Pick a number at random from the remaining choices.
sample := numbers[j]
bytemove(@numbers[i + 1], @numbers[i], j - i) 'Shift the values to make room.
numbers[i] := sample 'Put the selected number in the newly vacated spot.
waitcnt ( _xinfreq *2 + cnt )
I need a reel random, i was thinking it would be nice if this simple line can make it work but for me it is not.
j := (rand.random >> 1) // (RANGE - i + 1) + i 'Pick a number at random from the remaining choices.
Or can you tel me how can I do for never take the same number as before like "0,0,1,3,2,4,4,5,5"
I want to blink some LED whit this program and i don't want to blink the same LED like "0,0,1,3,2,4,4,5,5" the LED 0,4 and 5 blinks
I am not sure what you mean its not working? If I remember correctly the code fills each byte with a integer. If you want to light up LEDs then port the byte as a output
led := number[0]
Outa := %Led
The random number range will have to be limited to the max number your LEDs can show. Look into BCD as well.
The problem is that the code selects sometimes the same number as the presedent and this causes the same LED flash repeatedly without other LED lights.
PUB fill_array | i, j, sample repeat
if keycode == 136
Start_IR1
next
else
keycode := rcvir.fifo_get
repeat i from 10 to RANGE 'Fill numbers array in order.
numbers[i] := i
keycode := rcvir.fifo_get
repeat i from 10 to (SAMPLES - 1)
j := ||?seed // (RANGE - i + 1) + i 'Pick a number at random from the remaining choices.
sample := numbers[j]
bytemove(@numbers[i + 1], @numbers[i], j - i) 'Shift the values to make room.
numbers[i] := sample
waitcnt( _xinfreq+cnt)
outa[10..15]~
waitcnt( _xinfreq+cnt)
!outa[sample]
'Put the selected number in the newly vacated spot.
keycode := rcvir.fifo_get 'try a get from fifo
There are many kinds of random sampling, including "sampling with replacement" and "sampling without replacement" The typical random number generator is of the former variety, where each choice is independent of the choices that came before it, and the number chosen is immediately "thrown back into the hopper." That is not a "problem" per se, but just a characteristic of independent random number generation. If you want to eliminate sequential duplicates, it's a simple matter to keep sampling until a unique successor is produced.
There are many kinds of random sampling, including "sampling with replacement" and "sampling without replacement" The typical random number generator is of the former variety, where each choice is independent of the choices that came before it, and the number chosen is immediately "thrown back into the hopper." That is not a "problem" per se, but just a characteristic of independent random number generation. If you want to eliminate sequential duplicates, it's a simple matter to keep sampling until a unique successor is produced.
-Phil
Yes that what i need. but I'm not sure how to do the " keep sampling until a unique successor is produced" I tray different thing and noting work for me.. do you have a idea whit the last code i post?
Just store the last value in a variable and keep calling the random method, comparing it with the last value, until you get a different number. Then store that number, etc.
Comments
Could you elaborate on that I can't make sense of it?
Are you saying that adding a waitcnt(0) prior to running cessnapilots random number generator always gives the same result. If so that is what I would expect as the code is now synched to the counter.
What cessnapilot seems to be saying is that there is no such sync happening from reset naturally. Which is a bit odd to me and implies the clock counter is never reset.
I only know about no reset during soft reset (it just keeps counting). Not sure about cold power up. That said, the video frame counter and the counter flip-flops (A1 and A2) are definitely not reset (after power on).
That's just an observation, I'm not judging the quality of the generator.
The basic premiss is that we want a real random number from somewhere at start up. Perhaps to seed a pseudo random number generator as in cessnapilot's case.
So, is it so that that the value of CNT is unpredictable when read at start up or not?
I would naturally assume that CNT is initialized to zero on cold or warm reset. Then as my code executes it increments to to some value that I read from CNT. I would assume that value is always the same.
Except:
1) If CNT is not reset on a warm reset. In which case it is as random as the timing of my reset.
2) Something else odd is going on during cold start that causes CNT to not be reset to zero but some other random number or there is some random delay between CNT counter starting and my code executing. Or both.
There is something here we need to know is there not?
My point in #33 was that since you know it's cnt based you can force a specific sequence.
1) During a warm reset CNT just keeps rolling along and is not reset in any way. Strange but fair enough.
2) Just nit picking but during a cold restart the CNT counter sure is reset. After all it starts from a no power state i.e. all zeros.
Question is, then what happens? Do the flip flops of CNT just adopt some odd pattern at power up? Is there some analog process going on there that holds up program execution for a while with jittery results? Or both? Or what? How random can this be?
If we don't know the mechanism and it is not documented then we cannot rely on it.
Test program:
It's no good I have to try this for myself. Problem is that Christmas is in the way....
A couple comments:
1. I'm aware of modulo bias, but when the seed is 32 bits and the range is 0 to 100, it hardly matters.
2. Regarding all that byte moving business: Yes, if the byte moving were being done one at a time in Spin code, it would be very inefficient. However, the Spin byte-code interpreter does the byte moving quickly enough that, compared to the speed of Spin itself, bytemove can be thought of as a single, native operation -- especially on small data sets. But, now that you point it out, simply swapping bytes at the ends of a segment would accomplish the same end as rotating the entire segment, which is what I did.
Istvan,
I had assumed (wrongly it now appears) that CNT was initialized to zero on startup, just like all the other SFRs. That now appears not to be the case. That leaves only the question of whether, for a given chip, the bits in CNT have probabilistically preferred states from power-up.
-Phil
Phil,
It took me some time to reboot the same chip with 120 times while documenting the results for the CNT. For that Propeller all bits except bit 28 were 0 or 1 with acceptable Head or Tail fashion. However bit 28 was notoriously zero.
With the add CNT then multiply with CNT method it means that for a given seed there will be more than 2 billion starting sequences (for that chip). A real code will invoke even more entropy by using CNT with an incoherent way, like waiting for a key-press, reading a serial line or an input pin from a sensor. With a few random bits at the start, then time entropy at the calls is enough to stir up any reproducible pattern.
-Istvan
Quite so, it's a small bias introduced by the mod operator which most people most of the time would not notice or care about. Still it's there and may causes issues for serious random number users so it's good to be aware of it. I guess the Prop is unlikely to be used for such apps though.
Using string/block operations is quite efficient as you say, not sure how it pans out in this case. But the fisher-yates shuffle is a lot more elegant isn't it?
CessnaPilot,
Still haven't managed to check out the randomness of CNT on power up. I don't have a Prop board here that I can power cycle easily.
From the results you have I would be wary of using CNT as a source of randomness like that. As you say you have one "stuck" bit. Reducing the "randomness" by half. We cannot be sure how this works from chip to chip.
I've used this code: This runs with RCfast and the odd baudrate value is to compensate the difference between 12MHz and the frequency of my test-chip. The code is in the EEPROM.
The Prop is connected through a PropPlug to show the values on the PropTerminal on my PC. If I remove the PropPlug and the power, then connect the PropPlug again and then power the board up, I get the following results: If I only power it down, but don't remove the PropPlug in between the tests I get these results: There is always a increasing value in seed, no matter how long I wait until I connect the power again. So it seems that the PropPlug powers the Propeller enough to keep the value of the CNT flipflops, but CNT is not counting until the Prop is really powered up.
So you need to do the tests very carefully. And for me it seems the CNT register starts with nearly the same value each time you power the Propller up.
Andy
If I connect first the power and then the PropPlug I get more randomness: If I first connect the PropPlug and then the power, I get always nearly the same value. Last 4 tries: So it depends a lot of the power up procedure.
Andy
Attachment not found.
There is the code I use.
CON _clkmode = xtal1 + pll16x _xinfreq = 5_000_000 RANGE = 5 'Range is 0 to RANGE. SAMPLES = 1 'Number of samples to pick: 1 to RANGE + 1 VAR long seed byte numbers[RANGE + 1] OBJ pst : "Parallax Serial Terminal" rand : "RealRandom" PUB start | i pst.start(9600) repeat 100 fill_array pst.str(string("Samples: ")) repeat i from 0 to RANGE pst.dec(numbers[i]) if (i == SAMPLES - 1) pst.str(string(13, "Remainder: ")) else pst.char(" ") PUB fill_array | i, j, sample repeat i from 0 to RANGE 'Fill numbers array in order. numbers[i] := i repeat i from 0 to SAMPLES - 1 j := (rand.random >> 1) // (RANGE - i + 1) + i 'Pick a number at random from the remaining choices. sample := numbers[j] bytemove(@numbers[i + 1], @numbers[i], j - i) 'Shift the values to make room. numbers[i] := sample 'Put the selected number in the newly vacated spot. waitcnt ( _xinfreq *2 + cnt )I need a reel random, i was thinking it would be nice if this simple line can make it work but for me it is not.
j := (rand.random >> 1) // (RANGE - i + 1) + i 'Pick a number at random from the remaining choices.Or can you tel me how can I do for never take the same number as before like "0,0,1,3,2,4,4,5,5"
I want to blink some LED whit this program and i don't want to blink the same LED like "0,0,1,3,2,4,4,5,5" the LED 0,4 and 5 blinks
The random number range will have to be limited to the max number your LEDs can show. Look into BCD as well.
PUB fill_array | i, j, sample repeat if keycode == 136 Start_IR1 next else keycode := rcvir.fifo_get repeat i from 10 to RANGE 'Fill numbers array in order. numbers[i] := i keycode := rcvir.fifo_get repeat i from 10 to (SAMPLES - 1) j := ||?seed // (RANGE - i + 1) + i 'Pick a number at random from the remaining choices. sample := numbers[j] bytemove(@numbers[i + 1], @numbers[i], j - i) 'Shift the values to make room. numbers[i] := sample waitcnt( _xinfreq+cnt) outa[10..15]~ waitcnt( _xinfreq+cnt) !outa[sample] 'Put the selected number in the newly vacated spot. keycode := rcvir.fifo_get 'try a get from fifo-Phil
Yes that what i need. but I'm not sure how to do the " keep sampling until a unique successor is produced" I tray different thing and noting work for me.. do you have a idea whit the last code i post?
-Phil