Strange Rnd() behavior

Monkey Forums/Monkey Programming/Strange Rnd() behavior

Midimaster

(Posted 2013) [#1]

(sorry double post)

Midimaster

(Posted 2013) [#2]

I want to inform you about a strange Rnd() behavior I observed.

What I detected:

Rnd() returns always the same random number, if the Seed is closed to the Seed before (Distance <32). And there is no real equal distribution on seed "distances" below 1000.

Where I detected it:

My idea was to offer the free game user a game feature of the full version. But it should be always the same during the same day. On the next day he should see a different feature.

So I took the "days" date%[2] of the GetDate() function as the base for the Seed. I thought I would get a different first random number every day as the seed runs from "1" to "31".

But in fact the random number was the same during a the month!

What is my experience:

During test of the Rnd() function I detected, that only a step of 1000 guarantees a real random distribution.

So now the seed is still based on the days, but "1000", "2000", ... "31000"

See this test code:

Key "R" shows a real random number

Key "D" shows a start seed between 1...31

Key "B" multipies the seed base by 10

 Strict
Import mojo

Class Game Extends App
	
	
	Field Base%, Value%[]=New Int[11], locSeed%, BaseFaktor%
	
	Method OnCreate%()
		SetUpdateRate 10
        Local date:= GetDate()
        ' Base is: days
		Base= 1'date[2]
		BaseFaktor=1
		BaseReset
		Return 0
	End	

	Method OnUpdate%()
		If KeyHit(KEY_ESCAPE) Then Error ""

		If KeyHit(KEY_R) Then 
 	       Local date:= GetDate()
 	       ' Seed a real millisecs() value:
			Base= date[5]*1000+date[6]
			BaseFaktor=1
			BaseReset
		Endif

		If KeyHit(KEY_B) Then 
			BaseFaktor=BaseFaktor*10
			BaseReset
		Endif

		If KeyHit(KEY_D) Then 
 	       Local date:= GetDate()
 	       ' Seed a DAY value:
			Base= 1'date[2]
			BaseFaktor=1
			BaseReset
		Endif
		Return 0

	End	


	Method BaseReset:Void()
		Print "R"
			'reset all
			For Local j%= 0 To 10
				Value[j]=0
			Next
			
			' test random distribution
			For Local i%=0 To 30
				' simulation of the following 30 days:
				locSeed =(Base+i)*BaseFaktor
				Seed=locSeed
				
				' first random number of this day:
				Local FirstRandom%=Rnd(1,10)
				Value[FirstRandom]+=1
			Next
	End
	

	Method OnRender%()
		Cls 
		DrawText "[R]...Random or [D]...Day   Base (during 100 days) = " + Base + " to " + (Base+30 ),20,20
		DrawText "[B]...Base-Step-Faktor=" + BaseFaktor ,20,50
		Local result$=((Base+0)*BaseFaktor) + " " + + ((Base+1)*BaseFaktor) + " " +  ((Base+2)*BaseFaktor) 
		DrawText "resulting Seeds = " + result+ " ... " +  ((Base+30)*BaseFaktor) ,20,80
		DrawText "Random numbers of a Rnd(1,10) during the next 30 days:",20,120
		SetColor 255,255,255
			For Local j %=0 To 10
				For Local k%=0 To Value[j]
					DrawRect j*50+50,400-k*4,25,2
				Next
				DrawText j,j*50+50,450
			Next
   		Return 0
	End	
	
End

Function Main%()
	New Game
	Return 0
End

this means too, that a Rnd() seeded on only the Millisecs() value

Gerry Quinn

(Posted 2013) [#3]

It's a common enough quirk of many random number generation algorithms. When you start with two similar numbers, the internal seed moves further apart with every call to Rnd(), but for the first few steps the close seeds can result in the same random number being given. You'll often see this if you seed with Millisecs() too [at least the original Millisecs function, not sure if Mark changed it].

One solution is to call Rnd() three times or so after seeding but before using it for anything. Your solution of making the seed values more different works too.

Midimaster

(Posted 2013) [#4]

If Rnd() has produced the same number as the last day it makes no sense to do it three times, Because this will also produce the same row of random numbers as the day before!

Floyd

(Posted 2013) [#5]

He means call Rnd three times without reseeding between calls.

				  Seed=locSeed
				
				  ' first random number of this day:
				  Local FirstRandom%=Rnd(1,10)
					FirstRandom=Rnd(1,10)				
					FirstRandom=Rnd(1,10)
				  Value[FirstRandom]+=1

But since the problem is the seeds being close together I would use your technique. Spread them out by multiplying by a thousand.

ElectricBoogaloo

(Posted 2013) [#6]

Think of it like a plant..
You put the seed in the ground. The ground is always at 1.
Tomorrow (rnd) you check, and all the seeds are at 2
The next day, some are 3, some are 8, and some are 64
The more you leave the seed, the more varied the plants become.

If you need flowers, plant the seed, then leave it a week or so.
Seed=64;For n=1 to 100;r=Rnd(64);Next

Stick that into a Seedrnd() function, or something, and you'll be sorted.

Gerry Quinn

(Posted 2013) [#7]

I did a bit of experimentation, setting the seed to the sequence 0..9 and calling Rnd( 1000 ) ten times in a row. I also tried it with my own rand() function, which is a clone of the integer LCG used by MSVC (it can be found in the code forum). You can see the results below.

As you can see, the results after several calls seem relatively varied, but they are always a linear function of the seed. This is an issue with LCGs, which apparently Monkey's Rnd() is a floating point version of. The version with rand() looks a bit better, but I think that's the result of using Mod, which is theoretically bad for distribution but in this instance seems to be beneficial as it adds a periodic 'jolt' to the sequence!

This can be problematic. If you seed with N, 2N, 3N etc. there is a chance that there will be little variation in the results. And if there is variation, it will be linear, i.e. you may as well generate random levels based on a series of numbers, rather than calling Rnd() at all. A more sophisticated generator such as the Mersenne Twister, or the one that was posted recently in the code forum might work better.

/TLDR; Pseudo-random number generation is tricky.

Print "Using Rnd()"	
For Local s:Int = 0 Until 10
	Seed = s
	Local str:String = "Seed: " + s + " --- "
	For Local i:Int = 0 Until 10
		str += "  " + Int( Rnd( 1000 ) )
	Next
	Print str
Next
Print ""
	
Print "Using rand()"
For Local s:Int = 0 Until 10
	srand( s )
	Local str:String = "Seed: " + s + " --- "
	For Local i:Int = 0 Until 10
		str += "  " + rand() Mod 1000
	Next
	Print str
Next
Print ""

Using Rnd()
Seed: 0 --- 236 278 819 667 384 621 343 640 507 581
Seed: 1 --- 236 369 504 704 50 369 774 556 16 639
Seed: 2 --- 236 459 188 741 717 117 205 472 525 696
Seed: 3 --- 237 550 873 778 383 864 636 388 33 754
Seed: 4 --- 237 641 558 815 49 612 67 304 542 811
Seed: 5 --- 238 732 243 852 716 360 498 220 51 869
Seed: 6 --- 238 822 927 889 382 108 929 136 560 926
Seed: 7 --- 238 913 612 926 49 855 360 53 68 983
Seed: 8 --- 239 4 297 963 715 603 792 969 577 41
Seed: 9 --- 239 94 981 1 382 351 223 885 86 98

Using rand()
Seed: 0 --- 38 719 238 437 855 797 365 285 450 612
Seed: 1 --- 41 467 334 500 169 724 478 358 962 464
Seed: 2 --- 45 216 198 795 484 650 590 431 705 316
Seed: 3 --- 48 196 294 91 31 577 702 503 217 168
Seed: 4 --- 51 945 159 386 345 504 815 576 960 20
Seed: 5 --- 54 693 255 449 660 430 927 649 472 640
Seed: 6 --- 58 673 119 745 206 589 40 722 216 492
Seed: 7 --- 61 422 215 40 521 516 152 794 727 344
Seed: 8 --- 64 170 311 103 835 443 497 867 471 195
Seed: 9 --- 68 151 175 398 382 369 609 940 982 47