Rand statement Int range

Blitz3D Forums/Blitz3D Programming/Rand statement Int range

Axel Wheeler

(Posted 2013) [#1]

In the docs for the CreateBank() command, the following example is given:

; Bank Commands Example
; ---------------------

bnkTest=CreateBank(12)

PokeByte bnkTest,0,Rand(255)
PokeShort bnkTest,1,Rand(65535)
PokeInt bnkTest,3,Rand(-2147483648,2147483647)
PokeFloat bnkTest,7,0.5

Print PeekByte(bnkTest,0)
Print PeekShort(bnkTest,1)
Print PeekInt(bnkTest,3)
Print PeekFloat(bnkTest,7)

FreeBank bnkTest

I have found that the result of the PokeInt command as stated will always produce the minimum value in the Rand statement, -2147483648, and in fact that same Rand statement by itself produces that result. But that is the range of a four byte int, so why is that the case?

Even stranger, the command

Print Rand(-2147483645,2147483647)

produces -2147483646, which is outside the range given.

Finally, this code:

Graphics3D(1024,768,32,2)

For min=-2147483648 To 0
	val=Rand(min,2147483647)
	Print "Rand("+min+",2147483647): "+val
	While KeyDown(57)
		Delay(1)
	Wend
	If KeyHit(1) Then End
Next

similarly produces results further and further outside the range.

Also, is it just my machine that produces these results?

Thanks.

Rroff

(Posted 2013) [#2]

Mines not producting anything under -2147483645 with that last code snippet.

Floyd

(Posted 2013) [#3]

Also, is it just my machine that produces these results?

It's not just you.

I think the fundamental problem is that Blitz3D runs with the floating point unit set to single precision mode. Internally, the random number generator uses double precision arithmetic. But with the FPU in single precision mode the calculations still have only 24-bit accuracy, about 7 decimal digits.

Print Rand(-2147483648, 2147483647) covers the full range of 32-bit integer values, so it would need 32-bit precision to work correctly.

A much smaller range, such as Rand(-2147483648,-2147400000), should not be a problem.

Axel Wheeler

(Posted 2013) [#4]

Thanks for the responses. I had just never before seen a command specifically listed in the documentation that does not work. Floyd, your analysis may be correct, although that command gave the same result.

I was originally toying with this:

If the Rand() is using an int as a seed, and it produces an int for its result, then there logically should be a one-to-one pairing of a seed to a result. (assuming you use the full Int range of possible results.)

Unless... two seeds sometimes produce the same result. Of course, since it's just a formula that has to be possible.

In which case there must be some results than cannot be generated. Hardly seems fair, really.

Floyd

(Posted 2013) [#5]

Here's a test with a range ( one billion ) which is much too big for 24-bit arithmetic.

; Generate random integers up to 10^9, keep track of the ones up to 10^5.
; Each number has probability 1/10^4 of being that small. So with 10^7
; numbers generated we expect about 10^3 to be small, i.e. up to 10^5.
;
; This test shows about a thousand such results, as expected.
; But they should be randomly scattered among 1 to 100000.
; Instead there are only seven different values.

Dim count(100000)

For n = 1 To 10000000
	r = Rand( 1, 1000000000 )
	If r <= 100000 Then count( r ) = count( r ) + 1
Next

Print
Print "  Rand      count"
Print

; Show the counts only for numbers that actually occurred, meaning count(n) > 0.

For n = 1 To 100000
	If count(n) <> 0
		Print RSet( n, 6 ) + RSet( count( n ), 10 )
	End If
Next

WaitKey

Here is the output with Blitz3D:

  Rand      count
  7630       168
 22889       142
 38147       147
 53406       127
 68665       163
 83924       150
 99183       114

And in BlitzPlus, but only showing numbers up to 1000:

   Rand      count

     8         1
   187         2
   209         1
   299         1
   381         1
   649         1
   776         1
   969         1

This suggests the random number generators in Blitz3D and BlitzPlus are radically different. I have no idea why.

Axel Wheeler

(Posted 2013) [#6]

That's very interesting. For most game purposes at low ranges the randomizer would be fine, but that's a major caveat for doing anything serious. Thanks.

Axel Wheeler

(Posted 2013) [#7]

Here's an update to this.

The following code generates 1 million ints from 0 to 1 million, and keeps track of how many times each is generated in an array.

Exactly 934464 values (93%) do not get picked. It then adds another million values and lo and behold, the exact same 934464 values have still not been picked. It then continues to add a million values to the array at a time and the randomizer only selects from the same 7% of possible values. Note that 1 million is well within the 24 bit range of 16,777,215 ints.

Graphics3D(1024,768,32,2)

Global maxArray=1000000
Global numRuns=1000000
Global sumRuns#

Dim v(maxArray)

Local i

While Not KeyHit(1)
	AddValues()
	Print CountEmpties()+" have not been generated in "+sumRuns+" values.  +"+100.0*CountEmpties()/maxArray+"%"
Wend

WaitKey()
End

Function CountEmpties()
	Local i, count
	For i=0 To maxArray-1
		If v(i)=0 Then count=count+1;:Print i
	Next
	Return count
End Function

Function AddValues()
	;SeedRnd(MilliSecs())
	Local i,value
	For i=0 To numRuns-1
		value=Rand(maxArray)
		v(value)=v(value)+1
	Next
	sumRuns=sumRuns+numRuns
End Function

Floyd

(Posted 2013) [#8]

If 934464 values are not picked then 1000000 - 934464 = 65536 are. So Blitz3D is for some unknown reason using 16-bit values. Maybe it's using the random number generator in C/C++, which I think is 16-bit.

If you know a little calculus and probability you can estimate how many values will be missed. A randomly selected integer 1..N has probably 1/N of being chosen in a single trial. It has probability 1-1/N of not being chosen in one trial, and probability (1-1/N)^N of being missed every time in N trials.

As N becomes very large (1-1/N)^N approaches the limiting value Exp(-1). The expected number of missed values when N is a million is thus about 1000000*Exp(-1), which is 367879.

Sure enough, if I run your test in BlitzPlus I get 367959, very close to the predicted value.

Subirenihil

(Posted 2013) [#9]

I ran into this as well, when attempting to factor "random" int values. The Rand(0, 2147483646) never returns a prime above 16384 aka 2^14. Instead, for any value over 16383 the Rand() function returns pseudorandom number less than 16384 multiplied by a power of 2.

My temporary workaround was:

Function Random%()
	rtn1=Rand%(16383) Shl 18
	rtn2=Rand%(16383) Shl 11
	rtn3=Rand%(16383)
	Return rtn1 Xor rtn2 Xor rtn3
End Function

Axel Wheeler

(Posted 2013) [#10]

Genius. Floyd for the cause, Subirenihil for the solution. Thank you both.

virtlands

(Posted 2013) [#11]

There is this old topic by me (7 months ago) on generating random numbers.
I think in my version there is no repetition until the entire
cycle repeats, and also, all 32 bit unsigned values are represented, (with nothing skipped).

Random Numbers [using CRC logic]
http://www.blitzbasic.com/Community/posts.php?topic=100055

Trinosis included a revision for positive numbers as well.

Using 32 bits allows for 4,294,967,296 unique numbers.
Using 31 bits allows for 2,147,483,648 unique numbers.