Random generator

Lutamos

I was wondering if the Basic Stamp has the capabilaty to be used as a random number generator? Cause in the book it can count up and down. So if it can how would I program it to do so?? I want it to use the debug screen of course

Thank you
Lutamos ^_^

SRLM

There is a random command, but it's more psuedo random than any sort of real randomness. The best that you can do with the stamp is use some sort of external device to approximate randomness. You could use a button, a photoresitor, a temperature probe or just about anything analog. Keep in mind that no computer generated random number is truly random, even with a desktop language like Java. Java just uses the computer timer to "generate" a number. You could do the same with a clock module. Maybe, if you get enough random things into the equation, then you might approach phi, which is the most random of numbers.

Phil Pilgrim (PhiPi)

Lutamos,

See the PBASIC RANDOM command. As SRLM mentioned it's "pseudo-random"; but its statistics are good, and it truly is adequate for most applications requiring random numbers. Here's a scatter chart that graphs values from RANDOM, each paired with its successor. Notice the apparent lack of correlation between the two:



-Phil

Post Edited (Phil Pilgrim (PhiPi)) : 8/26/2008 4:00:11 AM GMT

SRLM

Question: in the PBASIC manual, it says "[noparse][[/noparse]random numbers] are generated by a logic operation that uses the initial value in variable to 'tap' into a sequence of 65535 essentially random numbers"(pg 359). So, were these numbers generated by a more advanced method, then recorded into the ROM of the stamp? If so, then it seems that if you need to output 65536 different numbers, you'll end up with the same pattern no matter what start number you have. Therefore, that graph that PhiPi posted is the same for all values input, just shifted in one dirrection or another.

If you need only two or three numbers, the RANDOM command might work if you change the seed value. The question the goes into a sort of recursion: how do you get a random number to provide the seed value? You're back where you started.

Phil Pilgrim: have you heard about phi being the most random of numbers? I've only looked at one source, but it's pretty exhaustive on the subject.

Phil Pilgrim (PhiPi)

In PBASIC, random numbers are generated algorthmically on the fly. So, yes, the successor R_n+1 to any particular R_n will always be the same. In other words, the pattern is fixed and cycles through all 65536 values (with the possible exception of zero). For most applicaiton arenas encountered by the BASIC Stamp, this is more than adequate "randomness". If you need a different seed at each startup, you can time a button press or use some other external stimulus along with a counter to pick the first value.

Also, most Stamp apps don't require all 16 bits of a random number. The remainder operator can be used to reduce the domain of numbers generated. When limited this way, the successor to a given number will not always be the same.

SRLM, there's really no such thing as "a most-random number". Numbers are only random when considered in a sequence with other numbers. Randomness has to be analyzed statistically, and one number doesn't make up a statistically-significant sample.

-Phil

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
'Still some PropSTICK Kit bare PCBs left!

Humanoido

Can you post the PBASIC program that generated
the random numbers in the scatter chart? Thanks.

humanoido

SRLM

My memory failed me. I read a book ("The Golden Ratio" by Mario Livio) that talked about phi, and I thought that there was something in there about phi being the most random. What it really says (when I look it up) is that phi is the most irrational of numbers:

A quote, pg 84: "


1 + 1/(1 + 1/(1 + 1/(1 + 1/(...))))

This is a special cse of mathematival entities known as continued fractions, which are used quite frequently in number theory. How would we compute the value the value of this continued fraction? ... we could at least start by denoting the value by x. Thus,

x = 1 + 1/(1 + 1/(1 + 1/(1 + 1/(...))))

Note, however, that because the continued fraction goes on forever, the denomintator of the the second term on the right-hand side is in fact identical to x itself. We therefore have the equation

x = 1 + 1/x

Multiplying both sides by x, we get x^2 = x +1, which is again the equation defining the Golden Ratio! We find that this remarkable continued fraction is also equal to phi. ... Because the continued fraction corresponding to the Golden Ratio is composed of ones only, it converges very slowly. The Golden Ration is, in this sense, more 'difficult' to express as a fraction than any other irrational number - it is the 'most irrational' among irrationals."

A little off topic from randomness, but interresting never the less...

Post Edited (SRLM) : 8/26/2008 10:52:03 PM GMT

Lutamos

Ya that looks like fun the Golden Ration. I need to take so more math courses. Ya I am with humanoido tho it would be lovely to see some of you pro wirte some code since I am still a newbie and don't know how to but trying hard to learn lol.

Phil Pilgrim (PhiPi)

Here's the code that generated the random pairs:

' {$STAMP BS2}
' {$PBASIC 2.5}

W1 = 32767

FOR W0 = 1 TO 1000
  W2 = W1
  RANDOM W1
  DEBUG DEC W2, " ", DEC W1, CR
NEXT

The results were copied from the DEBUG screen and pasted into Excel, where the graph was created.

-Phil

Dgswaner

I recently saw on some tech show, 2 inventor spent years calculating Pi to a billion decimal places. trying to find a pattern. they couldn't find even a hint of a pattern. makes you think!

The golden mean is also very fascinating also. it's proportion can be found every where in nature and even in the human body. If you want a good looking bot build it to the golden Ration! how does this help you generate a random number... it doesn't

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
"A complex design is the sign of an inferior designer." - Jamie Hyneman, Myth Buster

DGSwaner

SRLM

That lack of repeatability is part of the irrational part. There are proofs that are much cheaper than two years of time that can prove that... The problem with building to phi is that it's not very easy to get the measured dimensions.

Humanoido

Thanks Phil.

Tracy Allen

The golden ratio phi does have a high degree of randomness. That is important to us because of the method used in direct digital synthesis, as is done by the NCO module in the Propeller and in the Stamp FREQOUT command. The generator is simply,
X(k+1) = X(k) + m mod (2^n)
where n is the word size (16 or 32 bits), and m is the phase advance per cycle. k is an integer 1,2,3,....
The output is a sequence of phases on a scale from 0 to 2^n.

The two graphs below compare the phase sequence when m=40503 versus m=20861, and a word size modulus of 65536. Why those numbers? 65536/40503 is a close integer approximation to the golden mean, phi, while 65536/20861 is a close integer approximation to Pi. It can be seen that in a sense the sequence for Phi is more random than the sequence for Pi. In practical terms for direct digital synthesis, the Phi sequence has far more subharmonic jitter in its frequency output and in fact Phi is the "worst" in that respect. This is related to the small coefficients of the continued fraction expansion of Phi=(1,1,1,1,....) compared, say, to the large coefficients of the continued fraction expansion of Pi=(3,7,15,1,292,...).



That does not make X(k) from Phi a good source of psuedo-random numbers. In fact they are awful and flunk almost all statistical tests. Much better generators are "conguential sequences" of the form,
X(k+1) = a*X(k) + c mod (b)
where the multiplier "a", the additive constant "c" and the modulus "b" are carefully chosen. The modulus b may be 2^n or 2^n-1. There are many other generators. While the digits of Pi in any base pass tests for randomness, they are not easy to compute.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com

Post Edited (Tracy Allen) : 8/27/2008 4:47:02 PM GMT