random numbers

Unique Random Integers part II

Markus

Last year I wrote about my clumsy implementation of unique random integers system, I’ve used in my Memorable Ladies games. In those the speed isn’t a critical factor. It’s sufficient that the idea works. 🙂

In this post the idea behind unique random integers is the same, but implemented in a faster way.

In the implementation I have used an array that consists of all desired integers and each is drawn in a way that the same integer doesn’t get drawn again. Let’s take a look at the code (I have used Monkey2 programming language in the example):

Namespace myapp

#Import "<std>"

Using std..

Function Main()

	Local index:Int
	Local amountNumbers:Int
	Local randomNumber:Int
	Local numbers:=New Int[](1,3,5,7,9,11,13,15,17,19,21,23)

	While (numbers.Length <> 0)
		
		amountNumbers = numbers.Length	
		index = Int(amountNumbers * Rnd(0,1)) Mod amountNumbers
		randomNumber = numbers[index]
		
		For Local i:Int = index To amountNumbers - 2
			numbers[i] = numbers[i+1]
		Next
		
		amountNumbers = amountNumbers - 1
		numbers = numbers.Resize(amountNumbers)	
				
		Print "Random number:" + randomNumber

	End While
	
End

Image courtesy of nonicknamephoto at FreeDigitalPhotos.net

First an array is initialized with desired integers. Then an random integer from the array is fetched using random index inside the array.  After that the numbers after the drawn number are moved to “left”. For the end the amount of integers is decreased by 1 and the array is resized by the new amount of integers. That’s it.

This way one gets always different random integer from the set of desired integers.

Furthermore, if one would like to get, for example, number four (4) to be drawn three times, one could just include 4 three times in the array.

Depending on what one is doing, one could keep a copy of the original array for future usage.

Although I have used Monkey2 as example programming language, it should be easy to implement similar implementation to many other programming languages quite straight forwardly.

 

 

Unique Random Integers

Markus

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 n…m (m > n) and make a list of numbers that are already drawn and use Rand-function again between n…m, 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 = m – n

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