Page 1 of 1
Shuffling a portion of a ring buffer
Posted: Tue Oct 13, 2015 1:09 pm
by chitselb
The minimal set of
Ring Buffer operators is probably Read, Write, Empty?, and Full? But suppose you had a ring buffer with 52 elements (representing cards) and you wanted to shuffle the discard pile (a contiguous set between two points in the buffer). Suppose it's the next 22 cards starting at position 40. How would you do it?
Code: Select all
n=51
for i = 0 to n
list(i) = i
next i
for i = 0 to n
x = rnd(n) ; choose a random element between 0..n
t = list(i)
list(i) = list(x)
list(x) = t ; swap element 'x' with element 'i'
next i
Shuffling a list is pretty easy. On average, each element gets exchanged twice and every element is exchanged at least once. But this approach breaks down when the list wraps around.
Maybe something like a function INRANGE? that returns a boolean of whether the index is contained between elements start and start+size
'flag = INRANGE? (index, start, size)'
Re: Shuffling a portion of a ring buffer
Posted: Tue Oct 13, 2015 1:25 pm
by BigEd
I think your shuffle might be broken. See
here.
But to answer your question, I think I'd write a shuffle which runs over j to j+k-1, with all accesses made modulo n.
Re: Shuffling a portion of a ring buffer
Posted: Tue Oct 13, 2015 1:29 pm
by Arlet
Suppose it's the next 22 cards starting at position 40. How would you do it?
If index i is picked between 0 and 22, first calculate absolute position p = i + 40, and then check for wrap: if p >= 52 then p = p - 52.
Re: Shuffling a portion of a ring buffer
Posted: Tue Oct 13, 2015 1:56 pm
by chitselb
I think your shuffle might be broken. See
here.
But to answer your question, I think I'd write a shuffle which runs over j to j+k-1, with all accesses made modulo n.
I've been using a broken shuffle algorithm for 38 years?!! I enjoyed this question and will spend a little more time in the different answers trying to understand the reason why.
For what it's worth, my random number generator is RAND from Butterfield's "First Book of Kim", probably one of the most broken random number generators of all time, but also short, fast, and "random enough"
Code: Select all
RAND
SEC
LDA RND+1
ADC RND+4
ADC RND+5
STA RND
LDX #4
RLP
LDA RND,X
STA RND+1, X
DEX
BPL RLP
RND
.byt $12,$34,$56,$78,9A,$BC
Re: Shuffling a portion of a ring buffer
Posted: Tue Oct 13, 2015 3:25 pm
by barrym95838
... For what it's worth, my random number generator is RAND from Butterfield's "First Book of Kim", probably one of the most broken random number generators of all time, but also short, fast, and "random enough" ...
Well, my VTL02 pseudo-randomizer might be slightly worse, depending on the operand mix. It tries to stay compact with an add/swap/rotate that can get trapped in certain short patterns from time to time. Oh well, ...
Code: Select all
[ ... ]
lda arg+2
[ ... ]
exec3:
ldy #0
sta (arg),y
adc tick+1 ; store arg[{1}] in the left-side
rol ; variable
tax
iny
lda arg+3
sta (arg),y
adc tick ; pseudo-randomize {'}
rol
sta tick+1
stx tick
execrts:
rts
Mike B.
Re: Shuffling a portion of a ring buffer
Posted: Tue Oct 13, 2015 4:16 pm
by BigEd
For reference, I see two versions of Acorn's BBC Basic have two different pseudo random number generators - the newer one is much faster, but both are slower than those mentioned so far.
Newer:
http://8bs.com/basic/basic4-831e.htm#831E
Older:
See AF87 in
http://acorn.huininga.nl/pub/docs/sourc ... BASIC2.asm
I have a book of 6502 machine code routines with a chapter which deals with PRNGs. There's a 16bit one taking about 100 cycles and some 30+ bit ones taking about 200 cycles. I could scan some pages if there's interest.
http://www.devili.iki.fi/library/publication/41.en.html
Re: Shuffling a portion of a ring buffer
Posted: Tue Oct 13, 2015 5:03 pm
by chitselb
I think your shuffle might be broken. See
here.
But to answer your question, I think I'd write a shuffle which runs over j to j+k-1, with all accesses made modulo n.
Thank you! I had some myopia on how to do this, but
here's working code (at the bottom of the file)
I left the broken shuffle alone, because this works well enough and RAM is at a premium.
Code: Select all
: deck.
cr deck 36 dump ;
newdeck deck.
1E01 00 00 01 01 02 02 03 03 ........
1E09 04 04 05 05 08 08 09 09 ........
1E11 0A 0A 0B 0B 0C 0C 0D 0D ........
1E19 10 10 11 11 12 12 13 13 ........
1E21 14 14 15 15 OK
deck 26 12 shuffle deck.
1E01 12 13 01 01 02 02 03 03 ........
1E09 04 04 05 05 08 08 09 09 ........
1E11 0A 0A 0B 0B 0C 0C 0D 0D ........
1E19 10 10 00 12 00 14 11 15 ........
1E21 15 13 11 14 OK
Re: Shuffling a portion of a ring buffer
Posted: Wed Oct 14, 2015 3:11 am
by theGSman
It's easy if you run it from the top:
Code: Select all
for i = n to pos+1 step -1
x = rnd(i-pos)+pos ; choose a random element between pos..i *
t = list(i)
list(i) = list(x)
list(x) = t ; swap element 'x' with element 'i'
next i
A common mistake is to code the random number generator as
* I'm having a mental block about whether the +1 is required. I will double check later.
ETA I have cleared the +1 from the code. The rnd(n) function in this code already generates a number between 0 and n (which is one of n+1 numbers). This is not the norm. Usually, in BASIC, the function
int(rnd(n)) will generate a number between 0 and
n-1.
Re: Shuffling a portion of a ring buffer
Posted: Fri Nov 13, 2015 7:02 pm
by richard.broadhurst
Here is what I use "in-game"
Code: Select all
.rand
LDA seed
ASL A
ASL A
CLC
ADC seed
CLC
ADC #&45
STA seed
RTS
This is about the fastest random number generator you can get although it is really just a sequence of 256 unique numbers using 14 bytes (code and data if seed is in ZP).
Each call of rand will return A with the next of a 256 number long sequence of random numbers.
You can change the multiplier (5) and the addition (&45) to many different pairs and get different sequences.
One drawback of this method is that the lsb toggles each call.
RichTW suggested EORing with the low byte of a hardware timer before returning, but sometimes I NOP this out in "debug" to make the sequences reproducible.
PS I'm sure I have posted this here before!
Re: Shuffling a portion of a ring buffer
Posted: Sat Nov 14, 2015 10:13 am
by Snial
Let's say you have a list of 52 cards and you want to in-place shuffle cards n to m-1 inclusive. Array index is assumed to be from 0
Code: Select all
limit=m-n
for l=0 to limit-1
s=rnd(limit-l)+l+n:rem dest is always at l+n
if s>=52 then s=s-52:rem wrap.
d=l+n
if d>=52 then d=d-52:rem wrap.
c=card[s]
card[s]=card[d]
card[d]=s
next l
The important thing about this shuffling algorithm is that the same card never gets shuffled twice. On the first pass, a card from the entire range is picked and swapped into position n, then a card from the range n+1 to m-1 is picked and swapped into position n+1 etc, until the loop ends.
Re: Shuffling a portion of a ring buffer
Posted: Sun Nov 15, 2015 6:35 am
by theGSman
Suppose it's the next 22 cards starting at position 40. How would you do it?
I see that I originally misinterpreted this as sorting the remainder of the deck starting at position 40 and didn't allow for wrapping.
Here is my code for sorting k cards in a deck of size n starting at position p (again assuming rnd(n) returns a value in the range [0..n]):
Code: Select all
if k > n then k = n ; sort at most n cards
for i = k to 1 step -1
j = (i+p) mod n
x = (rnd(i)+p) mod n ; choose a random element between p..n or 0..j
t = list(j)
list(j) = list(x)
list(x) = t ; swap element 'x' with element 'i'
next i