how does the bs2 compute random numbers?
Archiver
Posts: 46,084
I know that the basic stamp uses a mathmatical algorithm to return a
pseudo-random number given a seed value, but how does that algorithm work?
Given the seed value, I need to be able to tell what number the basic stamp
is going to produce from the Random function. Does anybody know how to
figure out the number that the basic stamp will produce?
Thanks
pseudo-random number given a seed value, but how does that algorithm work?
Given the seed value, I need to be able to tell what number the basic stamp
is going to produce from the Random function. Does anybody know how to
figure out the number that the basic stamp will produce?
Thanks
Comments
he goes into pseudorandom generation in some detail. I haven't tested, but
I suspect the methodology is identical.
On Tue, 13 Aug 2002, Pepsi wrote:
> I know that the basic stamp uses a mathmatical algorithm to return a
> pseudo-random number given a seed value, but how does that algorithm work?
> Given the seed value, I need to be able to tell what number the basic stamp
> is going to produce from the Random function. Does anybody know how to
> figure out the number that the basic stamp will produce?
>
> Thanks
>
>
>
> To UNSUBSCRIBE, just send mail to:
> basicstamps-unsubscribe@yahoogroups.com
> from the same email address that you subscribed. Text in the Subject and Body
of the message will be ignored.
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
>
Sean T. Lamont, CTO / Chief NetNerd, Abstract Software, Inc. (ServNet)
Seattle - Bellingham - Vancouver - Portland - Everett - Tacoma - Bremerton
email: lamont@a... WWW: http://www.serv.net
"Do not fear mistakes, There Are None" - Miles Davis
a lot of different possibilities, so I agree with Sean that reading
Knuth will be useful background, but won't necessarily lead you to the
particular algorithm used in the stamp. Maybe the author of pBasic is
listening and will tell you which of many possible algorithms was used.
Dennis
Original Message
From: Sean T. Lamont .lost. [noparse]/noparse]mailto:[url=http://forums.parallaxinc.com/group/basicstamps/post?postID=dWC7mxKXiYwp4ZaU_Oi1Y5q2guQvu4e2C6ax0K0C2cCQkwlBG21-iny-Ltf7jH0rryKDN_a70bgrPoJANFK9oQ]lamont@a...[/url
Sent: Tuesday, August 13, 2002 2:19 PM
To: basicstamps@yahoogroups.com
Subject: Re: [noparse][[/noparse]basicstamps] how does the bs2 compute random numbers?
I would suggest looking in Donald Knuth's series on computer
programming, he goes into pseudorandom generation in some detail. I
haven't tested, but I suspect the methodology is identical.
On Tue, 13 Aug 2002, Pepsi wrote:
> I know that the basic stamp uses a mathmatical algorithm to return a
> pseudo-random number given a seed value, but how does that algorithm
> work? Given the seed value, I need to be able to tell what number the
> basic stamp is going to produce from the Random function. Does
> anybody know how to figure out the number that the basic stamp will
> produce?
>
> Thanks
>
>
>pseudo-random number given a seed value, but how does that algorithm work?
>Given the seed value, I need to be able to tell what number the basic stamp
>is going to produce from the Random function. Does anybody know how to
>figure out the number that the basic stamp will produce?
>
>Thanks
Hi Pepsi,
The PIC Source Book by Scott Edwards was released by him to the
public domain and is available on Dontronics web site:
http://www.dontronics.com/see.html
It has PIC source code for all the functions in the original BS1,
including RANDOM. To be sure, there is a distinction between
functionally equivalent vs the exact same code as the Stamp. Anyway,
RANDOM is implemented as a 16 bit shift register with XOR feedback
from bits 15, 14 and 4. That type of generator is fast and
economical of code, so it is a very likely candidate in a processor
where lots of code has to be crammed in a small space. The algorithm
is not particularly "potent" though. (Read Knuth to find what that
means statistically.)
I have not checked to see if that is the algorithm used in the BS2.
It would be easy to check, though.
If not, you can go ahead and generate your own sequence using that
same algorithm. Other algorithms are a bit longer both in code and
execution speed, because they require multiplications and such.
-- regards,
Tracy Allen
electronically monitored ecosystems
mailto:tracy@e...
http://www.emesystems.com
numbers d[noparse]:([/noparse]
I've made a table of the numbers generated by Random, incrementing through
seed values, and there are patterns in the bits of the generated values..
it's some sort of shift register algorithm, but it doesnt seem to be a very
simple one d[noparse]:([/noparse]
anyhow, I figured out how to identify the patterns and make a logic
equation for each bit.. i'm going to write a small program to find all the
bits in the seed that each bit in the generated number is dependant on.
from there i should be able to make a logic equation for the entire random
function d[noparse]:)[/noparse]
btw, it's important that i generate the same sequence of numbers as the bs2
>>I know that the basic stamp uses a mathmatical algorithm to return a
>>pseudo-random number given a seed value, but how does that algorithm work?
>>Given the seed value, I need to be able to tell what number the basic stamp
>>is going to produce from the Random function. Does anybody know how to
>>figure out the number that the basic stamp will produce?
>>
>>Thanks
>
>Hi Pepsi,
>
>The PIC Source Book by Scott Edwards was released by him to the
>public domain and is available on Dontronics web site:
>
> http://www.dontronics.com/see.html
>
>It has PIC source code for all the functions in the original BS1,
>including RANDOM. To be sure, there is a distinction between
>functionally equivalent vs the exact same code as the Stamp. Anyway,
>RANDOM is implemented as a 16 bit shift register with XOR feedback
>from bits 15, 14 and 4. That type of generator is fast and
>economical of code, so it is a very likely candidate in a processor
>where lots of code has to be crammed in a small space. The algorithm
>is not particularly "potent" though. (Read Knuth to find what that
>means statistically.)
>
>I have not checked to see if that is the algorithm used in the BS2.
>It would be easy to check, though.
>
>If not, you can go ahead and generate your own sequence using that
>same algorithm. Other algorithms are a bit longer both in code and
>execution speed, because they require multiplications and such.
>
> -- regards,
> Tracy Allen
> electronically monitored ecosystems
> mailto:tracy@e...
> http://www.emesystems.com
>
system you want to track. (Are you doing something like SecurID?), that
would probably be easier than reverse engineering the BS2 random function.
On Wed, 14 Aug 2002, Pepsi wrote:
> i found the code you suggested already and it doesnt generate the same
> numbers d[noparse]:([/noparse]
>
> I've made a table of the numbers generated by Random, incrementing through
> seed values, and there are patterns in the bits of the generated values..
> it's some sort of shift register algorithm, but it doesnt seem to be a very
> simple one d[noparse]:([/noparse]
>
> anyhow, I figured out how to identify the patterns and make a logic
> equation for each bit.. i'm going to write a small program to find all the
> bits in the seed that each bit in the generated number is dependant on.
> from there i should be able to make a logic equation for the entire random
> function d[noparse]:)[/noparse]
>
> btw, it's important that i generate the same sequence of numbers as the bs2
>
>
> >>I know that the basic stamp uses a mathmatical algorithm to return a
> >>pseudo-random number given a seed value, but how does that algorithm work?
> >>Given the seed value, I need to be able to tell what number the basic stamp
> >>is going to produce from the Random function. Does anybody know how to
> >>figure out the number that the basic stamp will produce?
> >>
> >>Thanks
> >
> >Hi Pepsi,
> >
> >The PIC Source Book by Scott Edwards was released by him to the
> >public domain and is available on Dontronics web site:
> >
> > http://www.dontronics.com/see.html
> >
> >It has PIC source code for all the functions in the original BS1,
> >including RANDOM. To be sure, there is a distinction between
> >functionally equivalent vs the exact same code as the Stamp. Anyway,
> >RANDOM is implemented as a 16 bit shift register with XOR feedback
> >from bits 15, 14 and 4. That type of generator is fast and
> >economical of code, so it is a very likely candidate in a processor
> >where lots of code has to be crammed in a small space. The algorithm
> >is not particularly "potent" though. (Read Knuth to find what that
> >means statistically.)
> >
> >I have not checked to see if that is the algorithm used in the BS2.
> >It would be easy to check, though.
> >
> >If not, you can go ahead and generate your own sequence using that
> >same algorithm. Other algorithms are a bit longer both in code and
> >execution speed, because they require multiplications and such.
> >
> > -- regards,
> > Tracy Allen
> > electronically monitored ecosystems
> > mailto:tracy@e...
> > http://www.emesystems.com
> >
>
>
>
> To UNSUBSCRIBE, just send mail to:
> basicstamps-unsubscribe@yahoogroups.com
> from the same email address that you subscribed. Text in the Subject and Body
of the message will be ignored.
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>
>
Sean T. Lamont, CTO / Chief NetNerd, Abstract Software, Inc. (ServNet)
Seattle - Bellingham - Vancouver - Portland - Everett - Tacoma - Bremerton
email: lamont@a... WWW: http://www.serv.net
"Do not fear mistakes, There Are None" - Miles Davis
register sequence, AKA Psuedo-Random Binary Sequence (PRBSs). A simple
explanation is in Horowitz & Hill, The Art of Electronics, pp 654-7. By
incrementing the seed to try to understand the logic, you are making
this more difficult than necessary. Use of the same seed always
produces the same sequence of zeroes and ones. That is useful for
encryption purposes, since knowing the seed used during encryption means
you can always reproduce the coded sequence and decrypt a message.
Every seed produces a different sequence of numbers. That is the reason
you shouldn't increment the seed to try to understand the logic. A
sequence of n bits produces a sequence of 2^n-1 pseudorandom bits,
before it repeats exactly the same sequence, for a given seed. A
different seed will produce a different sequence. The logic used is to
XOR certain positions in the shift register every time the register is
clocked to shift the bits, and to feed back the results into the input
end of the sequence. Tracy mentioned (below) that the correct feedback
taps for a 16-bit register are bits 15, 14 and 4. But Horrowitz and
Hill state that the correct taps are 15, 13 and 4. Another source gives
4, 8, 13 and 14 (Proc IEE 113:253, 1966). I haven't verified any of
these, but I know a lot about the correct use of 8-bit sequences, which
I used as band-limited pseudorandom noise sources for several system
identification studies.
Dennis
Original Message
From: Pepsi [noparse]/noparse]mailto:[url=http://forums.parallaxinc.com/group/basicstamps/post?postID=WVoURyGT_gcmrq7UmRyM0MM0T7kzbfOcdrrWTT50CijFPDeDqyZ_XXLBp5rG2UxVKVnU0ZrJ3ACxCqFXBmM]pepsi@c...[/url
Sent: Wednesday, August 14, 2002 2:26 PM
To: basicstamps@yahoogroups.com
Subject: Re: [noparse][[/noparse]basicstamps] how does the bs2 compute random numbers?
i found the code you suggested already and it doesnt generate the same
numbers d[noparse]:([/noparse]
I've made a table of the numbers generated by Random, incrementing
through seed values, and there are patterns in the bits of the generated
values.. it's some sort of shift register algorithm, but it doesnt seem
to be a very simple one d[noparse]:([/noparse]
anyhow, I figured out how to identify the patterns and make a logic
equation for each bit.. i'm going to write a small program to find all
the bits in the seed that each bit in the generated number is dependant
on. from there i should be able to make a logic equation for the entire
random function d[noparse]:)[/noparse]
btw, it's important that i generate the same sequence of numbers as the
bs2
>>I know that the basic stamp uses a mathmatical algorithm to return a
>>pseudo-random number given a seed value, but how does that algorithm
>>work? Given the seed value, I need to be able to tell what number the
>>basic stamp is going to produce from the Random function. Does
>>anybody know how to figure out the number that the basic stamp will
>>produce?
>>
>>Thanks
>
>Hi Pepsi,
>
>The PIC Source Book by Scott Edwards was released by him to the public
>domain and is available on Dontronics web site:
>
> http://www.dontronics.com/see.html
>
>It has PIC source code for all the functions in the original BS1,
>including RANDOM. To be sure, there is a distinction between
>functionally equivalent vs the exact same code as the Stamp. Anyway,
>RANDOM is implemented as a 16 bit shift register with XOR feedback
>from bits 15, 14 and 4. That type of generator is fast and economical
>of code, so it is a very likely candidate in a processor where lots of
>code has to be crammed in a small space. The algorithm is not
>particularly "potent" though. (Read Knuth to find what that means
>statistically.)
>
>I have not checked to see if that is the algorithm used in the BS2. It
>would be easy to check, though.
>
>If not, you can go ahead and generate your own sequence using that same
>algorithm. Other algorithms are a bit longer both in code and
>execution speed, because they require multiplications and such.
>
> -- regards,
> Tracy Allen
> electronically monitored ecosystems
> mailto:tracy@e...
> http://www.emesystems.com
>
To UNSUBSCRIBE, just send mail to:
basicstamps-unsubscribe@yahoogroups.com
from the same email address that you subscribed. Text in the Subject
and Body of the message will be ignored.
Your use of Yahoo! Groups is subject to
http://docs.yahoo.com/info/terms/
>numbers d[noparse]:([/noparse]
>I've made a table of the numbers generated by Random, incrementing through
>seed values, and there are patterns in the bits of the generated values..
>it's some sort of shift register algorithm, but it doesnt seem to be a very
>simple one d[noparse]:([/noparse]
Hi Pepsi,
I don't think it is a shift register algorithm. In a shift algorithm
you can clearly see the bits marching steadily to the left.
Here is a program that lets you see and compare the Stamp RANDOM
function with a maximal length pseudorandom shift sequence:
x var word
y var word
newbit0 var bit
loop:
random x
gosub taps ' compute y
debug dec x,tab,bin16 x,tab,dec y,tab,bin16 y,cr
goto loop
taps:
' computes new bit of maximal length shift
newbit0=y.bit15 ^ y.bit13 ^ y.bit4 ^ 1
y=y<<1|newbit0
return
Look at the march of bits in the shift sequence, and the lack of such
a march in the RANDOM function.
The next most likely routine is a linear congruential sequence:
x = (a*x + b)//m
that is, take the old value of x, multiply times a constant a, add a
constant b, and then divide by m and use the remainder as the new
value for x, which is the new "random" number. This would not take
much overhead in the bs2 interpreter, because it already has a
multiplication and a remainder function. For example, a = 25173, b
= 13849,m = 65535, computed with double precision of course. These
constants (and there are many other possibilities) are selected on
the basis of either programmingr folklore or from theoretical ideas
(which we too can understand if we read Knuth about a million+1
times!). The statistical properties of this method are well
understood (by somebody!). But this is by no means the only
additional method to generate pseudorandom sequences. There are
those that use higher order polynomials or other funcions, or time
lagged values, or sorting etc etc.
>
>anyhow, I figured out how to identify the patterns and make a logic
>equation for each bit.. i'm going to write a small program to find all the
>bits in the seed that each bit in the generated number is dependant on.
>from there i should be able to make a logic equation for the entire random
>function d[noparse]:)[/noparse]
Can you elaborate--Curious minds want to know!
>
>btw, it's important that i generate the same sequence of numbers as the bs2
>
>
>>>I know that the basic stamp uses a mathmatical algorithm to return a
>>>pseudo-random number given a seed value, but how does that algorithm work?
>>>Given the seed value, I need to be able to tell what number the basic stamp
>>>is going to produce from the Random function. Does anybody know how to
>>>figure out the number that the basic stamp will produce?
>>>
>>>Thanks
>>
>>Hi Pepsi,
>>
>>The PIC Source Book by Scott Edwards was released by him to the
>>public domain and is available on Dontronics web site:
>>
>> http://www.dontronics.com/see.html
>>
>>It has PIC source code for all the functions in the original BS1,
>>including RANDOM. To be sure, there is a distinction between
>>functionally equivalent vs the exact same code as the Stamp. Anyway,
>>RANDOM is implemented as a 16 bit shift register with XOR feedback
>>from bits 15, 14 and 4. That type of generator is fast and
>>economical of code, so it is a very likely candidate in a processor
>>where lots of code has to be crammed in a small space. The algorithm
>>is not particularly "potent" though. (Read Knuth to find what that
>>means statistically.)
>>
>>I have not checked to see if that is the algorithm used in the BS2.
>>It would be easy to check, though.
>>
>>If not, you can go ahead and generate your own sequence using that
>>same algorithm. Other algorithms are a bit longer both in code and
>>execution speed, because they require multiplications and such.
>>
>> -- regards,
>> Tracy Allen
>> electronically monitored ecosystems
>> mailto:tracy@e...
> > http://www.emesystems.com
> >
>