Unique Random Integers

For example in my Memorable Ladies games it is the case that I needed a method that gives a random integer for example between 0…31 so that any integer that has once been drawn, doesn’t get drawn anymore.

One way to handle this (how I didn’t do it) could be for example to use Rand-function (depending on programming language one is using) that gives an integer between nm (m > n) and make a list of numbers that are already drawn and use Rand-function again between nm, if the integer given by Rand has already been drawn.

But in the worst case this could lead to infinite loop… In practice probably not, though. In order to avoid the infinite loop (the case where Rand function gives repeatedly a number that has already been drawn), one could for example increase the drawn number by 1 until unused number is found or go on to m and if needed start from n and increase the value by 1 until unused number is found.

In Memorable Ladies games speed isn’t critical factor, when the numbers are drawn, so in this particular case the routine doesn’t necessarily need to be fast. In addition the amount of data can be considered very small.

What I came up, was something where every random number is (in practice) necessarily unique and without possibility to get stuck on infinite loop.

The idea goes like this:

  • Let us assume that we need n integers between 0….n – 1

  • Make a list of numbers with type ”number” where type ”number” has as a member an integer between 0…n – 1 (the numbers can be in increasing order)

Loop

  • Draw an integer between 0…n – 1. Let this be i.

  • Get from the list ith ”number” element and get the integer that is in that ”number” element as a member and then delete that element from the list

  • Decrease n by 1

  • Repeat until list is empty

Even if in the original list of type ”number” the integers are ordered from 0 to n – 1, one would get this way an unique random integer each time (except if Rand gives zero (0) n times).

There are more sophisticated ways to do this, especially if the set of needed integers is large.

id-100271132

Image courtesy of Stuart Miles at FreeDigitalPhotos.net

For the sake of nostalgia… Let be mentioned what kind of random number generator I have used with Amiga with MC68040’s built-in FPU in assembly. As such this doesn’t give an unique random number, though.

(In the source code of my old Quest of Love demo you can see this in practice)

Let us assume, that we need an integer between 0…n.

The idea:

  • Get the vertical beam value from $dff006

  • ”Scale” the previous value with desired integer in order to get it big enough

  • Use FPU’s fsin instruction (sine function) to that value

  • Use FPU’s fabs instruction (absolute value) to the value we got in the previous step

    Now we have a floating point value between 0…1

  • Multiply that value by n

  • Convert the value of previous step to integer

That’s it!

If we would like to have an integer between n…m (0 < n < m) the additional steps would be

  • Let z = mn

  • Add z to the integer we got in the last step earlier

The two steps above are only the idea to get the value to the desired interval; in assembly there are not variables at all as we know them in programming languages of higher level.

This idea probably gives you a good idea how to get random integers with Monkey X’s Rnd() that gives a random value between 0…1. 🙂

Probably the most common way is to do something like following:

value = Rnd() * 100 Mod n

This gives a random integer between 0…n – 1 (0 < n <= 100 above). Notice that in the sentence above there are two possibilities to get zero: 1) Rnd() gives 0, 2) Rnd() gives 1 and n = 100.