AW: AW: [basicstamps] Re: Tricky Random Question
Archiver
Posts: 46,084
Yes, Tracy,
I absolutely love the game of life for just that reason. I will try to
understand what you explained below, a little too much for me now because it
is late here in germany and I have a more serious problem right now, (see my
brownout cry for help)
Thanks for your help,
Uli
Urspr
I absolutely love the game of life for just that reason. I will try to
understand what you explained below, a little too much for me now because it
is late here in germany and I have a more serious problem right now, (see my
brownout cry for help)
Thanks for your help,
Uli
Urspr
Comments
>I absolutely love the game of life for just that reason. I will try to
>understand what you explained below, a little too much for me now because it
>is late here in germany and I have a more serious problem right now, (see my
>brownout cry for help)
>Thanks for your help,
>Uli
I played around with a couple of little programs that will only work
on the BS2p, because they require 90 bytes of scratchpad RAM. The
table in scratchpad holds numbers from 1 to 90 in an order that is
randomized at each step. Either of these programs will randomize the
table in a fraction of a second.
-- The first program really shakes them up, by running through the
table and exchanging each symbol with a symbol at a position selected
by the RANDOM function.
-- The second program uses an 89 bit maximal length shift "noise"
generator, as I described in an earlier message, to make permutations
of neighboring symbols if the bit is "1" and not permute if the bit
is "0". This second kind is much less random, and maybe more
interesting, because clumps of symbols (words) tend to stick together
for long runs. There is randomness at the single bit level, but high
correlation between bits as they move down the shift register.
-- best regards
Tracy Allen
electronically monitored ecosystems
http://www.emesystems.com
mailto:tracy@e...
'
'{$STAMP BS2p}
' crazyPoem.bsp
' completely randomizes the order at each step
i var byte
j var word
x var byte
y var byte
' initialize scratchpad table
for i=0 to 89
put i,i+1
next
' main loop
loop:
gosub play
gosub randomizer
nap 6 ' to slow it down
goto loop
' play the poem (display on screen)
play:
for i=0 to 89
get i,x
debug dec2 x," "
next
debug cr,cr
return
randomizer:
' swaps table elements in a random pattern
for i=0 to 89
get i,x
random j
get j//90,y
put j//90,x
put i,y
next
return
'
' {$STAMP BS2p}
' crazypoem2.bse
' permutes table elements depending on 89 bit
' maximal length sequence with XOR feedback
i var byte
k var byte
x var byte
y var byte
q var bit(90) ' bits for sequence
initialize:
for i=0 to 89
put i,i+1
random k
q(i)=k//2
next
loop:
gosub play
gosub randomizer
nap 6 ' to slow it down
goto loop
randomizer:
' scrambles the table by permuting table elements
' depending on the bits in the sequence q(i)
' 0 -- no permute
' 1 -- permute
get 0,x
for i=1 to 89
get i,y
'debug bin1 q(i+k-1//89) ' uncomment shows permutation
branch q(i+k//89),[noparse][[/noparse]noswap,swap]
noswap:
x=y
goto nextstep
swap:
put i-1,y
put i,x
nextstep:
next
'debug cr
gosub shifter
return
shifter:
' generates the next random bit
' the shift is implemented by moving a pointer in a circle
' instead of actually shifting the bits.
q(k+1//89)=q(k+82//89)^q(k+83//89)^q(k+85//89)^q(k+88//89)
k=k+1//89
return
play:
' (just show 0 to 33 for better screen display)
for i=0 to 89
get i,x
debug dec2 x," "
next
debug cr
return
correlation in maximal length shift registers is to shift multiple bits
before testing the next bit for a 0 or 1. When used for message
encryption, the method used is to generate random characters (8 bits),
and then XOR them with message characters. So shifting 8 bits to
generate a new encryption character eliminates the bit correlation that
you described here, Tracy. This could apply to your poem generator,
Uli, to make word selection more random.
Dennis
Original Message
From: Tracy Allen [noparse]/noparse]mailto:[url=http://forums.parallaxinc.com/group/basicstamps/post?postID=T4pqpNOcGugcArF-6jrodTFcQkli8dCEXx27pKhoGxTa7GkzGmlvfyYOypEquWZTRZ8ablpAaYlw-gfYEaBD]tracy@e...[/url
Sent: Friday, June 14, 2002 12:42 PM
To: basicstamps@yahoogroups.com
Subject: Re: AW: AW: [noparse][[/noparse]basicstamps] Re: Tricky Random Question
>Yes, Tracy,
>I absolutely love the game of life for just that reason. I will try to
>understand what you explained below, a little too much for me now
>because it is late here in germany and I have a more serious problem
>right now, (see my brownout cry for help) Thanks for your help,
>Uli
I played around with a couple of little programs that will only work
on the BS2p, because they require 90 bytes of scratchpad RAM. The
table in scratchpad holds numbers from 1 to 90 in an order that is
randomized at each step. Either of these programs will randomize the
table in a fraction of a second.
-- The first program really shakes them up, by running through the
table and exchanging each symbol with a symbol at a position selected
by the RANDOM function.
-- The second program uses an 89 bit maximal length shift "noise"
generator, as I described in an earlier message, to make permutations
of neighboring symbols if the bit is "1" and not permute if the bit
is "0". This second kind is much less random, and maybe more
interesting, because clumps of symbols (words) tend to stick together
for long runs. There is randomness at the single bit level, but high
correlation between bits as they move down the shift register.
-- best regards
Tracy Allen
electronically monitored ecosystems
http://www.emesystems.com
mailto:tracy@e...
<deleted>
correlation in maximal length shift registers is to shift multiple bits
before testing the next bit for a 0 or 1. When used for message
encryption, the method used is to generate random characters (8 bits),
and then XOR them with message characters. So shifting 8 bits to
generate a new encryption character eliminates the bit correlation that
you described here, Tracy. This could apply to your poem generator,
Uli, to make word selection more random.
Dennis
Original Message
From: Tracy Allen [noparse]/noparse]mailto:[url=http://forums.parallaxinc.com/group/basicstamps/post?postID=aXCB2nTa0j_cgs52BmNv3dE5fk6Psh2tDdXy1Zxecikbsz9uZnvWhp7FGorAIXAi4Uaj6ztzvlBDeA]tracy@e...[/url
Sent: Friday, June 14, 2002 12:42 PM
To: basicstamps@yahoogroups.com
Subject: Re: AW: AW: [noparse][[/noparse]basicstamps] Re: Tricky Random Question
>Yes, Tracy,
>I absolutely love the game of life for just that reason. I will try to
>understand what you explained below, a little too much for me now
>because it is late here in germany and I have a more serious problem
>right now, (see my brownout cry for help) Thanks for your help,
>Uli
I played around with a couple of little programs that will only work
on the BS2p, because they require 90 bytes of scratchpad RAM. The
table in scratchpad holds numbers from 1 to 90 in an order that is
randomized at each step. Either of these programs will randomize the
table in a fraction of a second.
-- The first program really shakes them up, by running through the
table and exchanging each symbol with a symbol at a position selected
by the RANDOM function.
-- The second program uses an 89 bit maximal length shift "noise"
generator, as I described in an earlier message, to make permutations
of neighboring symbols if the bit is "1" and not permute if the bit
is "0". This second kind is much less random, and maybe more
interesting, because clumps of symbols (words) tend to stick together
for long runs. There is randomness at the single bit level, but high
correlation between bits as they move down the shift register.
-- best regards
Tracy Allen
electronically monitored ecosystems
http://www.emesystems.com
mailto:tracy@e...
<deleted>
>correlation in maximal length shift registers is to shift multiple bits
>before testing the next bit for a 0 or 1. When used for message
>encryption, the method used is to generate random characters (8 bits),
>and then XOR them with message characters. So shifting 8 bits to
>generate a new encryption character eliminates the bit correlation that
>you described here, Tracy. This could apply to your poem generator,
>Uli, to make word selection more random.
>
>Dennis
I'm confused about that, Dennis. The guru Donald Knuth says,
"Caution: several people have been trapped into believing that this
random bit generation technique can be used to generate random whole
word fractions (...)(...), but it is actually a poor source of random
factions, even though the bits are individually quite random. See
exercise ..." (p. 32 Seminumerical Algorithms ISBN 0-201-89684-2
1998) The exercise shows that the n-tuples fail the "serial test".
I am not sure if that is because the pairs are too much or too little
uniformly distributed. The Art of Electronics has an interesting
practical take on this: "The autocorrelation function is a Kronecker
delta at zero delay, and -1/K elsewhere. This absence of "side lobes"
on the autocorrelation function is what makes PRBSs so useful for
radar ranging".
It is interesting to watch it acts as suffles the sequence of symbols
(words of the "poem"). The symbols kind of do a random walk back and
forth, hardly ever very far at a time. A long sequence of 1s is like
"chutes and ladders", taking a symbol far in the shuffle, while zeros
sort of leave things where they are. The correllations actually make
the sequence more "interesting", because there is the illusion of a
hidden pattern to the changes. Total randomness is usually not as
"interesting".
-- Tracy
shifting the wrong direction. The following makes it conform to the
maximal length 89 bit sequence I described.
' corrected routine, uses k+88//89 instead of k+1//89
' (pointer movement "left" shifts the bit sequence "right")
shifter:
' generates the next random bit
' the shift is implemented by moving a pointer in a circle
' instead of actually shifting the bits.
k=k+88//89
q(k)=q(k+83//89)^q(k+84//89)^q(k+86//89)^q(k)
return
-- Tracy
autocorrelation function, Kronecker delta at 0, and lack of side lobes
is a reference to use of PRBS signals in system identification
(including radar ranging), where they are considered periodic signals
with white noise properties. Advantages are that their bandwidths can
be adjusted to match or exceed that of the system undergoing testing,
but their periodicity allows for period averaging, and subsequent noise
reduction. I used this technique to show that shark semicircular canals
functioned as an array of bandpass filters. I published this in Nature,
Biophysical J, and J Neurophysiology. For many applications, use of
PRBS noise is superior to use of Gaussian noise, or Geiger-counter
Poisson noise.
For encryption purposes, Knuth is certainly correct for single shift
registers. I suspect that is why encryption authors run multiple very
long generators simultaneously, and XOR the results together, to produce
an encryption mask. This was pointed out in articles in both EDN and
C/C++ Users Journal. I can provide references if anyone wants them.
Your point about perceived "hidden patterns" is interesting, Tracy, and
probably highly useful for applications concerning perception.
Dennis
Original Message
From: Tracy Allen [noparse]/noparse]mailto:[url=http://forums.parallaxinc.com/group/basicstamps/post?postID=lcMFdeI9mzr-Z-S9je9ANm6P8FQQMWSYUx7Qm8CwX2DIj7h_kX7iguJDFqLW_8yCkrCelxvBTR9oIFg]tracy@e...[/url
Sent: Friday, June 14, 2002 7:18 PM
To: basicstamps@yahoogroups.com
Subject: RE: AW: AW: [noparse][[/noparse]basicstamps] Re: Tricky Random Question
>I learned from an encryption article that the way to avoid bit
>correlation in maximal length shift registers is to shift multiple bits
>before testing the next bit for a 0 or 1. When used for message
>encryption, the method used is to generate random characters (8 bits),
>and then XOR them with message characters. So shifting 8 bits to
>generate a new encryption character eliminates the bit correlation that
>you described here, Tracy. This could apply to your poem generator,
>Uli, to make word selection more random.
>
>Dennis
I'm confused about that, Dennis. The guru Donald Knuth says,
"Caution: several people have been trapped into believing that this
random bit generation technique can be used to generate random whole
word fractions (...)(...), but it is actually a poor source of random
factions, even though the bits are individually quite random. See
exercise ..." (p. 32 Seminumerical Algorithms ISBN 0-201-89684-2
1998) The exercise shows that the n-tuples fail the "serial test".
I am not sure if that is because the pairs are too much or too little
uniformly distributed. The Art of Electronics has an interesting
practical take on this: "The autocorrelation function is a Kronecker
delta at zero delay, and -1/K elsewhere. This absence of "side lobes"
on the autocorrelation function is what makes PRBSs so useful for
radar ranging".
It is interesting to watch it acts as suffles the sequence of symbols
(words of the "poem"). The symbols kind of do a random walk back and
forth, hardly ever very far at a time. A long sequence of 1s is like
"chutes and ladders", taking a symbol far in the shuffle, while zeros
sort of leave things where they are. The correllations actually make
the sequence more "interesting", because there is the illusion of a
hidden pattern to the changes. Total randomness is usually not as
"interesting".
-- Tracy
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/