? Operator

fatmanforprez

the recent thread on the ~ and ~~ operators has made me realize that there is another misfit on the operator table that I have never paid attention to before. Namely the ? operator. According to the data sheet it produces a (?x) random number forward or a (x?) random number reverse.

I have a few questions here, first is from where is this randomness derived?

The fact that it has a forward and reverse version makes me think that the propeller is using the variable as a random seed to produce a common seed based PRN. That would be cool.

Though it could also be using the counter or the input/output states as a seed. That would also be cool.

Can I trust it's bi-directional nature?

Also how expensive is it (I know it's a spin operand so it can't be quick, but I sense the possibility to be REALLY slow).

Time to do some testing.

P.S. I am almost sure this has to have been asked before, however due to the odd name the search was less than fruitful. If it has been discussed before I apologize, please simply point me in the right direction.

Mike Green

The ? operator uses a LFSR (Linear Feedback Shift Register) to produce a pseudorandom number. Because this is linear, it can be run forward and backward. Chip has done some experimenting with true (physical process related) random number generation with the Propeller and there are some threads on that subject. The ? operator is no more expensive than other Spin operators, probably less than 1us.

RossH

I just discovered this operator while translating some SPIN code to C - does anyone know the specifics of the LFSR that SPIN uses? I would like to emulate it in C.

Thanks,

Ross.

Mike Green

You'll have to look at the source code for the Spin interpreter. That'll have the polynomial in it.

Ariba

from the interpreter source:

:rnd                    min     x,#1                    '?var/var?
                        mov     y,#32
                        mov     a,#%10111
        if_nz           ror     a,#1
:rndlp                  test    x,a             wc
        if_z            rcr     x,#1
        if_nz           rcl     x,#1
                        djnz    y,#:rndlp       wc      'c=0
                        jmp     #:stack

Andy

RossH

Thanks Mike, Ariba! Should have thought of that myself.

JRetSapDoog

Ah, so the polynomial is built in to the firmware, i.e., fixed? Then does that mean that I'd always be "walking" (moving) around (either forward or backwards) within the same random number sequence...no matter what number I seeded it with? Prior to this post, I was naively assuming that each seed gave a unique sequence (even though not perfectly random being a pseudo-random technique). However, if the polynomial is fixed, then perhaps the seed would just vary the starting point within the one-and-only-one availble sequence if only using the built-in implementation.

So, for example, for a game, one could seed the generator from the 32-bit cnt register, perhaps instigated by a button press to vary the seed (although, IIRC, using a button wasn't neccssary in my testing to vary the starting point...as it seems that the Propeller either somehow doesn't boot up with the same cnt value each time or takes variable time to boot, or both (or some other reason)). However, whether using a button or not, if the polynomial is fixed, then it would seem to be the case that if a player recorded several sequential random numbers (at least to the extent that they were presented from the game interface), then they could perhaps ascertain the current place in the overall sequence and thereby determine (predict with certainty) the next "random" number to be generated.

Still, to do that for a die, for example, would be difficult, wouldn't it...because so many 32-bit numbers would truncate (modulo) and map to the same numbers, 1..6. Therefore, one would likely have to record a long sequence of die rolls (rather than 32-bit numbers) to get something unique enough that would identify the current place in the overall sequence (and they'd have to have the entire sequence available and run a search for that pattern, you know, via a wireless connection with their co-conspirator in a nearby room). Or probably I've got something wrong. Anyway, if that's mostly correct, then I guess that's not worth worrying about at all for a game...unless the lottery were involved or similar. Hmm, though, actually, I don't know on average how many die roll results would be necessary after all, meaning perhaps it's not as many as one would expect. Anyway, just musing. I'm not running the lottery or doing encryption. And as far as the pseudorandomness, I'm not thinking about scientific analysis or simulation. True randomness, it turns out, is hard. Who knew! (Well, everyone, nowadays) But I think that the pseudorandomness will work for me...for now, anyway.

Okay...I see there's a big Wikipedia page available on the technique, but I'll throw this out there for possible comment (or not) anyway for what it's worth. Thanks.

RossH

JRetSapDoog wrote: »

Ah, so the polynomial is built in to the firmware, i.e., fixed? Then does that mean that I'd always be "walking" (moving) around (either forward or backwards) within the same random number sequence...no matter what number I seeded it with? Prior to this post, I was naively assuming that each seed gave a unique sequence (even though not perfectly random being a pseudo-random technique). However, if the polynomial is fixed, then perhaps the seed would just vary the starting point within the one-and-only-one availble sequence if only using the built-in implementation.

Hi JRetSapDoog,

Your first paragraph describes the situation correctly.

LFSR generates each value in the non-random sequence exactly once, so you can figure out what the forward random or reverse random will be from any value - which is exactly what the ? operator does.

This is not the same as a more typical random function, which usually involves a hidden variable - precisely to make this more difficult.

In summary, the ? operartor is ok for games or demos - but is emphatically not recommended for security or encryption!

Ross.

JRetSapDoog

Thanks, Ross. Ah...each value "exactly once"...such that *any* value (thanks for the italics, though I'm not sure where to get the font formatting on this new forum (my first day back)) from the sequence could be used to determine the next or prior value. Hmm...well performing modulo division on a 32-bit value to get down to, for example, a 3- or 4-bit value makes doing that impossible (since it's a many-to-one mapping), though some information it would seem could be gleaned from analyzing a long sequence of, for example, "die" values. Anyway, nothing to worry about for a general game.

Coincidentally, as I was reading your post, I was listening to a video report on MSNBC on a Princeton study about whether people's collective consciousness in emotionally-moving times (such as major disasters reported in the news) has any effect on random number generators scattered around the globe, with the current data supposedly suggesting that there might be a link...perhaps carried in some kind of "information field." Yeah, that's a bit on the edge, but it's worth having an open-mind and considering the possibilities rather than just dismissing things outright (perhaps perpetual motion machines excepted, lol, though I just contradicted myself). Anyway, by chance, it periodically happens that the word one is reading (the word "random" in my case just a bit ago) and the word being spoken on TV, etc. are the same (if one multitasks, that is). Hmm, then again, perhaps "cosmic forces" are at play and the seeming coincidence that I just reported was actually manifested by all that is or the powers that be (cue strange music).

While I'm on the fringe, allow me to venture even further and farther afield: I've occassionally wondered if a perturbation in a complex "pattern" in one location could have a sympathetic effect on an identical pattern "running" (operating) in another location. Yeah, I know, it's called radio, but I'm talking about physio-electrical patterns and something that could be a point-to-point communication mechanism, though the transceivers could move around (and don't ask me about if it'd communicate at the speed of light or not). Anyway, it seems to me that, for something like that to be possible, there would have to be a randomness factor involved. I mean, if you injected a data signal (the above perturbation) into the so-called "transmitter," there'd have to be something really small in the transmitter (maybe at the quantum level) that was affected, but in order to be able to observe that, there'd likely have to be an at least seeming randomness of some sort in the receiver. Hmm...gee...the Propeller with 8 seemingly identical and deterministic cogs (as opposed to some complicated non-deterministic operating system) might just be the device to experiment on (though something like a memory chip would probably be even better). Uh-oh! Might need more than this LFSR method's randomess, then, lol. Anyway, at present, I was only asking because I just used the Prop's ?N operator in a game, not an interstellar communication's device. You have to start small, see. Okay, enough of that...although it would be nice to put the Internet service providers and wireless Telcos out of business.