Exact match. Not showing close matches.
PICList
Thread
'[PIC]: Random Number Sequence'
2006\06\11@172423
by
Phil Keller

All,
I have an application that I need to generate a random number sequence
for. Not just a random number, I know how to do that, but an entire
pseudo random sequence. The sledgehammer approach would be to generate
a random number, see if it is already in the sequence and store it if it
is new, then generate a new random number. Early in the process this
would work OK, but when I need the last four numbers the time required
to generate the numbers could be excessive to say the least.
The details:
 The user will have a random number of sound files (2 to 127) on a
memory card.
 The PIC will count the number of available files and create a
random number sequence that is nonrepeating and inclusive of all file
numbers. (Each file is assigned a number so that I don't need to
'shuffle' the file names, just the numbers.) I can skip files numbers
that are greater than the number available but a sequence that stops at
the maximum would be nice.
 The PIC will select the first file number and send the file to a
player.
 Once that file is played the PIC will select the next file number
in the sequence and send it to the player.
 Once all songs have been played once, the PIC will generate a new
random sequence and start over.
Suggestions or pointers are greatly appreciated.
Phil
2006\06\11@175940
by
William Chops Westfield
AppleMail1042713177
ContentTransferEncoding: 7bit
ContentType: text/plain;
charset=USASCII;
format=flowed
On Jun 11, 2006, at 2:22 PM, Phil Keller wrote:
>
> I have an application that I need to generate a random number
> sequence for. Not just a random number, I know how to do that,
> but an entire pseudo random sequence.
You want a "shuffle" algorithm. With a similar problem some time
ago, I came up with this framework (in C):
The enclosed code in shuffle_lib.c will return a shuffled sequence of
any
number of items up to 65535, using only 6 bytes or less of storage. A
pseudorandom number generator (PRNG) can be used to produce a
nonrepeating
sequence of numbers, but the usual implementation will generate only a
sequence of length 2^N1 (for an N bit number.) That's not a problem,
you
can just filter out all the numbers that are outside the range of
interest.
The other problem with a PRN is that the sequence itself repeats; 12
always
follows 232, or whatever. Since our PRNG is generating a larger range
than
we want anyway, this can be fixed by permuting the number somehow before
filtering, using a separate permutation constant. This means that our
final
algorithm is something like:
shufflednum(max) = filter(max, permute(prng(randreg),
permuteconst));
The code example enclosed uses a standard shiftwithxorfeedback
scheme for
the PRNG, simple subtraction for the permutation, and a test against the
maximum as the filter, making it quite fast. (however, it needs to be
fast
if the number of items to be shuffled is much smaller than the size of
the
PRNG. to get 10 items with a 16 bit PRN, you may end up filtering out
65525
numbers. This can be optimized by using a shorter PRN, of course.)
Note
that by changing the PRNG seed, you change the starting position of the
shuffled list, but not the list itself, while changing the permutation
constant results in dramatically different sequences.
Enclosed files:
shuffle_lib.c: library functions in hopefully machineindependent C code
shuffle_test.c: demonstration program, written for unix, tested on
Solaris
shuffle_log.c: sample run, demonstrating effects of seed vs permutation
constant changes
AppleMail1042713177
ContentTransferEncoding: base64
ContentType: application/zip; xmactype=5A495020; xunixmode=0755;
xmaccreator=53495421; name="Shuffle.zip"
ContentDisposition: attachment;
filename=Shuffle.zip
UEsDBBQAAAAIACy2uTAnbZBSHwIAAPwFAAAPAAAAc2h1ZmZsZV9sb2cudHh0hZRNj5swEIbv/hWj
lXJjqW0wJJH20ktP/VDbW7WqWDABLbFTMO3uv69nEGZTleBIr8aeseN5ZvC3sm8vDgZX9E5XYA18
HzV8LF5BKhDZUSVHpUBynrLRtC9iB6eyhKEZ67rTP50eXLxMu/bJz+7tlZ/2yR3E765W2Y+hOF86
Df1oHhlr7J9zYV4jsHU9aBfBoHXFJAcBInjhwd8kAoDPFOSnYgpEi4EfAiVByXGWoSgUjiJRUhTy
HjBujxYKpCi0ljFcpGMkCp1AR3PG7lfG1vAZl01hTq05gWs0fPn66cN0eVrWA0xVQP/FDq1rrYng
aXRgrPOBv0ZtSh0DvLeuYT627ToorXFFa0D4pHOfr8/W5xrH8eNNohyRbiHFMKKxCuOK+BZxtop8
Ybo1tphedH8eXYHoEI3naRyc2t8ebgHnsWygauta99osRG82H7/dffyf9ssnXphfgJaEfiOHCgR4
6DdCRTtSorKgkgEnbZE3UW2hqm0PhbEeVA/6xX99Opq/VI/nrtLlsycAZdFXw53voVUySvqrJCmo
LN+/xaPkWzwUMwOaYjE5iSJCCyy9ckCHCqBQJErC0bGf+UqBU2onFSgnRJ4CaXNyRVSGZkvC15/S
33FcSxiqnAuT0oEC92GM4mjlcyHSdK6LpLhsanNUnCqGHonmAS0qN1l0DN1hv17FrbFWEQ7+Ry9t
smPD9KZX1uj/POjqKLLpQf8LUEsDBBQAAAAIABKwNjLj4+zvdgQAANYIAAALAAAAc2h1ZmZsZS50
eHRdVU2P2zYQvfNXDHKJjcpGdhebQ4Ie0iQIeugiaHJuQUsjiV2JVDjketVf3zeUtI5rwF8i+ebN
mzfD3+lshX5kl5gaJ3aagvOJGzr37GmcyfOZ7g9YeqQ/vt7Rx09U99Z3HOkc8tD418m8kj637cCv
aDcNdiYJvhMKvmZiW/fkPEXrmzBSiA3HPQk/cbSDAE0AE1NPoTWAX4/uxM4V3bx588v6YEI4RG5D
VETdTalnuleA4/G4J/pAJ5cUJTKY1MkFT3XwT87XSGZk7LepHJpi6KIdR46CjDUBevThTD3eKZjR
In+8ydKSFo4PThR740199k3E84Vc2Tu6OgYETDEMA0dz7oMw4o4hziqxhj3Z0zBTm4eBToxcWPnM
ZJsGWEptnO6o4TpApCPRbzmZOWRqgnJ8+Pz5E/jRCz/JEMIu3P7J+MAigjS55p+4G+EfmSHC0Zjv
CIGfQxDE0yigvm38e3CnY01nB3KRU45XAmwgKoL1s/F5PHHUf/DNKJQnjf72/v7uvqIszncoP3J9
S6c5sRDqNrBI0TCFaDtGfh/MJJybcFjNsYJ27CFywpHd1z8fvuypth56AZab6xx98IfIE9uEgOYn
jiuUVHTKWnQ9nFE3N04Djwz91B8l2S0cL4TtzzDg7Dt48/avh8MN7dR9oPKgTlsjqPO+w1ivBWQS
2VJlhKgIhTMgvlSmdUNSuTK2ICQIbQwXW9rIuiiu4bIYtcGKuh7nWNKx1C5gLW4hwD5p/aERObnY
+4W/S8JDS4tA8p5ubhH8bGcxLSwazkK3d7eVluaMs/xUPPfNldRzVNwvAF70KQqr2WxE5y/8NKQ3
Z4a7fVJXALvCQ5xZKoa0n1Gy06ztO+YCcUkdzTMyem5tBbNohD2bgSxSmayWZj1vt6aWhIgg+11j
jWz9kr7SRkxvB2OHLkToMyKDEij1Cjm4R35nDOG1WRtkdqN93tOva5X0X7VG5N0UfbeLVtu92788
Lhz2+/elpZZO4mcLc136S+0qmkPCYRsbBHRtOmjRDs8hHlrm5mTrR5K6hyV1tBmIU2SvSIpT0eKn
FG0ZZroBWV5pURGwEQMdhgJ0GAr4xh6DFNyYR7Kif9fEKoyOR1XBpXXet1ZUxh2qoOWvdMWDl2ib
nZZ145ZRe93x647LgNBC6DyS0er4K95Y7Oj+VScXWpob4uFoxwnjfYHajHzztjQWNpXuAdsZajY6
W168oV2iY+b23qwNVGxwsVyYkhsRUm138VEfIs4XaOVSwyjC2rsPIbFR72D7cq+tJl3sLxCjkFnW
SnNqRWPx8hTEaRm29K6uizJ6dCjoUnmyNmSFdnMDv0T7f1HNZnBC4+chlfulwYWF1Rrizri02hZT
ATu2XhcM98+b8VqgC1x+NdjfEb6ijXr9+GKogtuHifU+mqF2jRbhg/MNBgY+AP+xWPsFSG2mSA2P
SjEWutt1irTQcIkXo2bv0ER6AISw6VvA5HBy4RQ6RZKlZ2L21QW1aMtIsU6yXLrAeJIrjej6tUm2
lknMf1BLAwQUAAAACAAstrkwUapEBz8FAAAMDQAADQAAAHNodWZmbGVfbGliLmOFVllvGzcQfo5+
xUAPheRKsuQcCOK4QFsUrYHAKZIUQV9qULuzEmEuueUhWQ3y3ztDcnd1Gd4HGyLn4jffHJcXA7gA
tw5VpfBeyeWs4INfTbOzcrX2cDWfX03pzytY7uAXqRR8RecriaokQZb9WYNQK2OlX9dQGQuNNWUo
pF6BACt0aWpw+G9AXSBUln7dgfRYOwiOhWqpZS1UjMMbK1YIo5dXsJTejQG+rLHX3rJ/bTxYbFD4
ZGYCy+ChEBqWmC+wZGtmg1aQwnKXPXm2JWo2iKUDCg1MVTn0bkbyl4NBQkNqj1YL1YbDj2LdFqb+
uSTNATo6snQdmsY4LMEbDmXxJr4BUBTra3hAbMgj4A7BaNiZYKEwdSMV2uTdeeFlAUE7udJYkjdj
fQTQ4uoa4nfJuZIVA7CSjsKEPz/dxec8baFBWwe+Mfq+MJqEtL+Optpf/MB9MbbVgtE4DKVJaaTf
5NgHqyMcGh99vp/mPOtQLymoEUU1zqALgpEuhS2hFo+yDjWwHYV65dfwaOy0ovCXonggxKaE2NEL
Zwlk6bJrx76zo0SnBQP+5vXrl68pdeSvko9YRlKIpqHEaK92ZOSYizOAO0O5aI1l7rjocBQ9yuRs
2L5gCEpqFPY4CVuZngLtUzgt15GDpJ+StEJNdCRGOcI9qJIpEogts/HT2T9An/g02hhZjgffBkSF
Y1GNWwbvBubXg3gvKxhl9sANHY+B9PLXncPiOh5+P1H5AeaPb+dzUkuWW9lTqVf7Uv88KbZIYs+J
kdTbU7E+4l76/XtYjOHHLBvFMke6qhl8zzzu6I2pwsHYkhLjTZsXhDooLxuFGfSeLRiILS5xTQCT
WrGVlvpHghPYIiVKWCmWajeG0pDS4t0CamIj6VLLiaSqpHWezERyeBIiC1SQJf3zRM3PYemtKGI5
bo19cKSgybhw9JPpI8pS8u2EiTdhQxRH5hu1ISeXUpEARj4/1xso4qMbqZvgI9V6VEfxEKZnW8qY
wWa0u++577kvz5cvDJZRymwZvYowZr+OW24EEh9Tu1Y72Eh6tsLUwStRkIBhGTJz2rwZl+577nvu
6+dHP01prvn0Bs5pjLUFy8XSp8m0P1fK3Ij6VjHL6reMu3t3kj2r72Pvn0Yz7E/S2NoIFbqhddh7
2Fj+SPzMbCBTvTqdeEvIE+77kjmo0d8m8NglL1I/ZFo7CiMGS3VSN2rHfPVbQwA0giLIo5f4/YfZ
4gYTcaFYC72KtaFVhKR/Wi12RD9HtUmGu97NfZnmfxkaJQvh6TeZ946NUSCpCjphcjeK4tJNqN3w
7E0esfPXjdEJDBfDuGdEW1Sy3O7ZlawqtMiYKcEByDgEOydpC/H7XG3T2VtTW7Fz1Pi7TSQ2f777
GHxKsabYSTdn/nLAHf+AUTB6ggWTsxlta7hvoJ1C6piXF/FfjOFoUuV9i/LULnUI/6E13VsPloav
tx8+tKaCpu5Kb7E18bGQtgg18T7lAn7TLlhMGdxii8pabGjSJpVs5lBzyOVSSicyvDGU2WyWhS+7
aXICQRp/gxdnLtr5cq6l0fXpcexyx5XOm9CItpsxH/4uN6j3lxRTtYtqI4sHatN7e0m7lAzZRBSb
DdnIX7xTnl+uRFpKlsLJgjRSqmJKuKl0RE2z5eOnL7cf7z7n6nxyZAmeOw+yicWfqys2WBPYDqtb
Lpi2IX1Kq1gU72ohibDsfDZjOKaLceqLh4w9gI2HiufN8Pxak2s/rTQ8S78NXsSj/eTg6HBPGo3H
eauB7VoqGm5Z5aeb6OlgVYhXMa3/A1BLAwQUAAAACAAstrkwMotUgp0CAABsBQAADgAAAHNodWZm
bGVfdGVzdC5jhVNRb9MwEH6Of8WpaFPadVs7tqeuSMADICF4AImXSZUTXxqL2C62s65M++/cOUm7
DiEsq6rj7/vu7rvz5UTABL7VbVU1uIoY4kXJX967zc7rdR3haja7Oqefayh28E43DfwgVKWxUQRk
7FsLslk7r2NtoHIeNt6pttR2DRK8tMoZCPirRVsiVJ5OX0BHNAHawCCjrTayYakQnZdrhPz1FRQ6
hjHA9xoP7C3Hty6Cxw3K2MlMoWgjlNJCgf0FKlZz9+glEYpdHymyljQsiCoApQauqgLGcNHVQtF0
ANoSFBpnQ/Qyame5pLWXhhQoKj6U6EsdMCTFRhde+h1oC6EzMnl4KYR4pW3ZtArhNkSl3UX9Rgh8
iOgttDbotUVFHOfjwFxZus61jWDkw3gxgO+dVnsI2RXzYzrlZ1dc1JSyoBN608aU+arkKqSNJCZE
0uEuQz4WjwJoMV4vsizjw+UEPju3gdK1lgJTEXtM7bZG2t1iD/zotsBfwLamQE9euCHFnveyRm/V
gT6KZPWon4+kcRSvb8yUW3VgdY3jIUvOr9EiNcglYmIqB48io6nOYEIyGxoMJaNkxnFHCUCcbOMp
VpWP+uqmR2Hv7IhcywKNFkFOFKQ9msLpHn464E+ZwGhdQd5fw+0SZmORci88yp8Lsc/tEzVRy0b/
Rq5kb5zBspZWB9Pnd9RzDjFkOH6m9QFjmuVUTJLz/GBCpJnvnSXWEEMNDXthwZ0d0l5SlVPK+WuK
1B85OP9lV6ZE7dZfvg02sOG5Xs4WoOF2gNHh7GwMjx3dWxI8HvweRwIJMaR2ckOuM364YJM1nMD8
BpZLmF8nzWeVjAbgk8hov7g4HM//sf637mwnlULAttbUunxOH56EMFLb/fNKjy3vLv4AUEsBAhQD
FAAAAAgAErA2MuPj7O92BAAA1ggAAAsAAAAAAAAAAAAAACSBTAIAAHNodWZmbGUudHh0UEsBAhQD
FAAAAAgALLa5MFGqRAc/BQAADA0AAA0AAAAAAAAAAAAAACSB6wYAAHNodWZmbGVfbGliLmNQSwEC
FAMUAAAACAAstrkwJ22QUh8CAAD8BQAADwAAAAAAAAAAAAAAJIEAAAAAc2h1ZmZsZV9sb2cudHh0
UEsBAhQDFAAAAAgALLa5MDKLVIKdAgAAbAUAAA4AAAAAAAAAAAAAACSBVQwAAHNodWZmbGVfdGVz
dC5jUEsFBgAAAAAEAAQA7QAAAB4PAAAAAA==
AppleMail1042713177
ContentType: text/plain; charset="usascii"
MIMEVersion: 1.0
ContentTransferEncoding: 7bit
ContentDisposition: inline
2006\06\11@181342
by
Martin K

There are many interesting methods of generating random numbers. Chaotic
differential equations are sometimes used as could be the mersenne
twister algorithm or the linear congruential generator.
You probably don't require such a thing, but there are many novel
techniques involving hardware generation such as heat patterns,
radiation, human interaction intervals, etc.

MK
Phil Keller wrote:
{Quote hidden}>All,
>
> I have an application that I need to generate a random number sequence
>for. Not just a random number, I know how to do that, but an entire
>pseudo random sequence. The sledgehammer approach would be to generate
>a random number, see if it is already in the sequence and store it if it
>is new, then generate a new random number. Early in the process this
>would work OK, but when I need the last four numbers the time required
>to generate the numbers could be excessive to say the least.
>
>The details:
> The user will have a random number of sound files (2 to 127) on a
>memory card.
> The PIC will count the number of available files and create a
>random number sequence that is nonrepeating and inclusive of all file
>numbers. (Each file is assigned a number so that I don't need to
>'shuffle' the file names, just the numbers.) I can skip files numbers
>that are greater than the number available but a sequence that stops at
>the maximum would be nice.
> The PIC will select the first file number and send the file to a
>player.
> Once that file is played the PIC will select the next file number
>in the sequence and send it to the player.
> Once all songs have been played once, the PIC will generate a new
>random sequence and start over.
>
> Suggestions or pointers are greatly appreciated.
>
>Phil
>
>
>
>
2006\06\11@191922
by
Jinx
part 1 1096 bytes contenttype:text/plain; (decoded 7bit)
> when I need the last four numbers the time required to
> generate the numbers could be excessive to say the least
What would you call excessive ? AIUI you want to create a
sequence from 2 (min) to 127 (max) using numbers once and
once only. I've done similar s/w in the past, with a very much
longer sequence, and didn't really notice a problem. Besides,
as you say later 
> The PIC will select the first file number and send the file to a
> player. Once that file is played the PIC will select the next file
> number in the sequence and send it to the player
That time during the playing of the first selection is also available
to the PIC for completing the sequence ? You need only have
the first number to start playing
Martin K wrote 
> there are many novel techniques involving hardware generation
> such as heat patterns, radiation, human interaction intervals, etc.
I've used this noise source method often
http://home.clear.net.nz/pages/joecolquitt/white_noise.html
The attached shift register circuit works well too
part 2 4337 bytes contenttype:image/gif; (decode)
part 3 35 bytes contenttype:text/plain; charset="usascii"
(decoded 7bit)
2006\06\11@193307
by
Zik Saleeba
The Knuth shuffle algorithm is fast and easy. From Wikipedia:
"...the Knuth shuffle or FisherYates shuffle[1], is a lineartime
algorithm (as opposed to the previous O(n log n) algorithm if using
efficient sorting such as mergesort or heapsort) which involves moving
through the pack from top to bottom, swapping each card in turn with
another card from a random position in the part of the pack that has
not yet been passed through (including itself). Providing that the
random numbers are unbiased, this will always generate a random
permutation.
"Notice that great care needs to be taken in implementing the Knuth
shuffle; even slight deviations from the correct algorithm will
produce biased shuffles. For example, working your way through the
pack swapping each card in turn with a random card from any part of
the pack is an algorithm with nn different possible execution paths,
yet there are only n! permutations. A counting argument based on the
pigeonhole principle will clearly show that this algorithm cannot
produce an unbiased shuffle, unlike the true Knuth shuffle, which has
n! execution paths which match up onetoone with the possible
permutations."
http://en.wikipedia.org/wiki/Shuffle#Shuffling_algorithms
Cheers,
Zik
On 12/06/06, Phil Keller <spam_OUTPhilTakeThisOuTpkeller.net> wrote:
{Quote hidden}> All,
>
> I have an application that I need to generate a random number sequence
> for. Not just a random number, I know how to do that, but an entire
> pseudo random sequence. The sledgehammer approach would be to generate
> a random number, see if it is already in the sequence and store it if it
> is new, then generate a new random number. Early in the process this
> would work OK, but when I need the last four numbers the time required
> to generate the numbers could be excessive to say the least.
>
> The details:
>  The user will have a random number of sound files (2 to 127) on a
> memory card.
>  The PIC will count the number of available files and create a
> random number sequence that is nonrepeating and inclusive of all file
> numbers. (Each file is assigned a number so that I don't need to
> 'shuffle' the file names, just the numbers.) I can skip files numbers
> that are greater than the number available but a sequence that stops at
> the maximum would be nice.
>  The PIC will select the first file number and send the file to a
> player.
>  Once that file is played the PIC will select the next file number
> in the sequence and send it to the player.
>  Once all songs have been played once, the PIC will generate a new
> random sequence and start over.
>
> Suggestions or pointers are greatly appreciated.
>
> Phil
>
>
> 
2006\06\11@234717
by
Phil Keller

Thanks that looks like exactly what I wanted. I'll play with it tomorrow.
Thanks again,
Phil
William Chops Westfield wrote:
{Quote hidden}>
> On Jun 11, 2006, at 2:22 PM, Phil Keller wrote:
>
>>
>> I have an application that I need to generate a random number
>> sequence for. Not just a random number, I know how to do that,
>> but an entire pseudo random sequence.
>
>
> You want a "shuffle" algorithm. With a similar problem some time
> ago, I came up with this framework (in C):
>
> The enclosed code in shuffle_lib.c will return a shuffled sequence of any
> number of items up to 65535, using only 6 bytes or less of storage. A
> pseudorandom number generator (PRNG) can be used to produce a
> nonrepeating
> sequence of numbers, but the usual implementation will generate only a
> sequence of length 2^N1 (for an N bit number.) That's not a problem,
> you
> can just filter out all the numbers that are outside the range of
> interest.
> The other problem with a PRN is that the sequence itself repeats; 12
> always
> follows 232, or whatever. Since our PRNG is generating a larger range
> than
> we want anyway, this can be fixed by permuting the number somehow before
> filtering, using a separate permutation constant. This means that our
> final
> algorithm is something like:
>
> shufflednum(max) = filter(max, permute(prng(randreg), permuteconst));
>
> The code example enclosed uses a standard shiftwithxorfeedback
> scheme for
> the PRNG, simple subtraction for the permutation, and a test against the
> maximum as the filter, making it quite fast. (however, it needs to be
> fast
> if the number of items to be shuffled is much smaller than the size of
> the
> PRNG. to get 10 items with a 16 bit PRN, you may end up filtering out
> 65525
> numbers. This can be optimized by using a shorter PRN, of course.) Note
> that by changing the PRNG seed, you change the starting position of the
> shuffled list, but not the list itself, while changing the permutation
> constant results in dramatically different sequences.
>
> Enclosed files:
>
> shuffle_lib.c: library functions in hopefully machineindependent C code
> shuffle_test.c: demonstration program, written for unix, tested on
> Solaris
> shuffle_log.c: sample run, demonstrating effects of seed vs permutation
> constant changes
>
>


Long ago when men cursed and beat the
ground with sticks, it was called witchcraft..
Today, it's called golf.
More... (looser matching)
 Last day of these posts
 In 2006
, 2007 only
 Today
 New search...