Random-list generator code

[Yulquen74]

In short, the use case is to randomize a list of mod and other music files, before playback in that random order.

I initially though of generating a random number list, which could be used to index a file-list,
and while this perhaps is over the top for this use case, I want it to be able to handle a list
of tens of thousands of entries if needed.

What I want is this:

Produce a random sequence of numbers within a given range, without any duplicate numbers.

If this can be done without generating a list (just one-shot call the rng for each new file),
and the sequence can be continued from session to session by saving the internal state of the rng for each session,
I am fine with that.

If however a random number sequence file needs to be generated to ensure no duplicates,
the routine should be as efficient as possible, I do not need the rng to be perfect.

Considering the 32 bit xorshift in post #6, if called enough times after the seed has been initialized,
it will return all the numbers from 1 to 4.294.967.295 without any duplicates?

Suppose you only want numbers from 1 to 10000, without any duplicates?
Can you do that with some math tricks, or do you need to use a predefined table and Fisher/Yates shuffle it?

For shuffle you can always re-call the rng if the given number is a duplicate due to limiting.

[Thorham]

Originally Posted by meynaf

This is a property of LCG, i don't think xorshift is affected.

Also, LCGs need big multiplies (96+ bits) to be really good.

[Thomas Richter]

Originally Posted by Yulquen74

In short, the use case is to randomize a list of mod and other music files, before playback in that random order.

IOWs, the random generator needs neither to be very good, nor does it need to be very fast. The rand implementation in your C library, or even the one from amiga.lib might be good enough for something simple. It is "by tradition" not a very good generator, but for this it should really be sufficient. To get every time a new sequence, just provide a good seed to it, e.g. the current date should do it.


Don't create problems were there are none.

[Don_Adan]

Originally Posted by Yulquen74

In short, the use case is to randomize a list of mod and other music files, before playback in that random order.

I initially though of generating a random number list, which could be used to index a file-list,
and while this perhaps is over the top for this use case, I want it to be able to handle a list
of tens of thousands of entries if needed.

What I want is this:

Produce a random sequence of numbers within a given range, without any duplicate numbers.

If this can be done without generating a list (just one-shot call the rng for each new file),
and the sequence can be continued from session to session by saving the internal state of the rng for each session,
I am fine with that.

If however a random number sequence file needs to be generated to ensure no duplicates,
the routine should be as efficient as possible, I do not need the rng to be perfect.

Considering the 32 bit xorshift in post #6, if called enough times after the seed has been initialized,
it will return all the numbers from 1 to 4.294.967.295 without any duplicates?

Suppose you only want numbers from 1 to 10000, without any duplicates?
Can you do that with some math tricks, or do you need to use a predefined table and Fisher/Yates shuffle it?

For shuffle you can always re-call the rng if the given number is a duplicate due to limiting.

Im not expert, but for me random generator without duplicates is not random, but linear.
For your case, I will create empty 10000 bytes long file.
And with and.l or/and lsr.l I will get any number up to 10000.

Later I will check if this numbered byte in this file/memory is empty.
If empty then this is new value/module.
And addq.b #1,(A0,D0.L) (if you need any stats) or st (A0,D0.L) used (if you dont need stats)
If not empty then addq.l #1,D0 and repeat check.
Of course you must remember about loop if D0=10000 then clear D0.

Edit. And if I remember right some file systems dont like too many files in same directory.

[Thomas Richter]

Originally Posted by Don_Adan

Im not expert, but for me random generator without duplicates is not random, but linear.

Huh, why? Note that something different is asked for, namely not a set of random numbers, but a random permutation of a finite set of objects. That is, for N objects there are N! possible permutations, and each should happen equally likely. So it is random, but on a different probability space (that is, for a random permutation, the likelyness of finding object k at position i is not independent from the likelyness of the populations of the objects at other positions, but this wasn't really asked for.).

[jimshaw]

Generate the numbers 0 to 99 in an array

First iteration:
using your rng, pick a random number N between 0 and 99.
swap the number at location 0 with the number at location N

Second iteration:
using your rng, pick a random number N between 1 and 99.
swap the number at location 1 with the number at location N

Third iteration:
using your rng, pick a random number N between 2 and 99.
swap the number at location 2 with the number at location N

etc

Repeat 100 times

Now your array has the numbers 0-99 in it, permuted in a random order.

[a/b]

Well, the fact that you want a very high rate of non-duplicates chages the things significantly.
Needing only one random every once in a while helps a lot, because that process can be made as complex as needed to meet your requirements as best as possible. You also mentioned shuffling, but the problem is you will be adding new songs, so that complicates it.

So... LGCs is what you normally want, they have already been mentioned by meynaf, but for such a small max_rand (~10k, and even if you add a few bits of depth to that) the math fails and they don't work that well. That's why all the rand() stuff in c libraries is using much larger max, 32 bits or so.

So, I would just use the standard srand()/rand() with a simple extendable bitfield (Don Adan said bytes, but a single bit is sufficient) and a direction flag. You generate a random, take top N bits (for 10k, that's 14 bits, but you can also determine that dynamically), calculate index, and check the bitfield if bit is set. If so, retry up to say 50 times. If that fails and you picked 50 duplicates, pick the first unset bit from either the start or the end (depending on direction flag, so when you append new songs with very few left to play you don't end up playing those in a row) and invert the flag. Or you could do a bisection to make it more non-linear, or...
In a state file you track the last random (unmodified, use it with srand() next time), dir_flag, num_played (to know when to reset, you could even do it earlier because newly added songs probably won't be randomized that good) and a bitfield.

[Don_Adan]

This is not my program.
But if I understand correctly, he want this for 68000.
Then bytes are better/faster than bits for handling.
1. For me bytes are easy changable/expandable for adding/removing favorite mods from list.
2. Addq.b #1,(A0,D0.L) can be used as extra random routine too.
After 256 calls/accesess it will be again 0, and this module can be played again.

[Don_Adan]

Originally Posted by Thomas Richter

Huh, why? Note that something different is asked for, namely not a set of random numbers, but a random permutation of a finite set of objects. That is, for N objects there are N! possible permutations, and each should happen equally likely. So it is random, but on a different probability space (that is, for a random permutation, the likelyness of finding object k at position i is not independent from the likelyness of the populations of the objects at other positions, but this wasn't really asked for.).

This is my point of view.
I told already im not expert.
But calling f.e $ffffffff times random routine and receiving $ffffffff different results is for me similar random like addq.l #1,D0. Only in different rotation.

[koobo]

Originally Posted by a/b

So, I would just use the standard srand()/rand() with a simple extendable bitfield (Don Adan said bytes, but a single bit is sufficient)

This approach is basically what is being used in HippoPlayer for keeping track of randomized modules. The bitfield size is determined by the number of items in the playlist (max size is 16kB). In case of a collision it will retry with a new random value indefinitely, has not end up in a deadlock yet m I guess the randomizer is not that bad.

[a/b]

Originally Posted by Don_Adan

Then bytes are better/faster than bits for handling.

Yeah, but speed is apparently not that important because he needs a single random:
- when song ends,
- when user clicks on next (at most a couple of times a second if they recognize song name and want to skip it immediately).
I think these are all of his use cases.

So, with a bitfield you have 8x lower memory requirement for tracking. And I/O times, well about the same since you can use fseek() and only update what's been changed, which I admit *would be* more straightforward with bytes. But you could just keep it simple and write the whole thing in one go since it would only be a couple of KBs.

[Don_Adan]

Then perhaps I will use different method for handling similar case.
One ascii list (editable) with favourite user mods with full paths (with filename) ready to load.
And second small file (up to 10000 bytes long for this case) with random access handling.
D0 is known, then searching D0 times for new line inside ascii list file.
Of course ascii list can be big, but in old days I never seen favorite mods list greater than 200-300 mods.
And of course I mean about loading mods from different disks/directory etc.
Not only from one directory.

[Yulquen74]

I appreciate all suggestions, I will try and implement some of them to test out.