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

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.

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.

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"

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


Mike B.

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

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.

It's easy if you run it from the top:


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.

Here is what I use "in-game"


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!

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



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.

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]):