Shuffling a portion of a ring buffer

[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)'

[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.

[Arlet]

Quote:

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.

[chitselb]

BigEd wrote:

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

[barrym95838]

chitselb wrote:

... 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.

[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

[chitselb]

BigEd wrote:

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

[theGSman]

chitselb wrote:

How would you do it?

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

Code: Select all

x = rnd(n-pos)+pos

* 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.

[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!

[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.

[theGSman]

chitselb wrote:

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