RND and RANDOMIZE information

[SMcNeill]

For folks who want a little extra information about how RND and RANDOMIZE work in QBASIC (and has been imitated to work the same in QB64), here's a little old documentation I dug up from the old drive on them:

;***
; RANDOM - RANDOM number generator AND RANDOMIZE
;
;        Copyright <C> 1986, Microsoft Corporation
 
;
; Algorithm:
;
; We use the "linear congruential" method FOR RANDOM numnber generation. The
; formula IS:
;
;        x1 = (x0 * a + c) MOD 2^24
;
; where
;
;        x1 = IS a new RANDOM number in the range [0..1^24]
;        x0 = the previous RANDOM number (OR the seed, FOR the first one)
;        a  = 214,013
;        c  = 2,531,011
;
; The RND FUNCTION returns a floating POINT number:
;
;        x1 / (2^24)
;
; which changes the range TO [0..1].
 
;***
;GetNextRnd -- GET NEXT RANDOM number
;MakeFloat -- make the number in [b$RndVar] into a R4
;
;Purpose:
;        GET NEXT RANDOM number in sequence.
;Entry:
;        [b$RndVar] has the seed.
;EXIT:
;        [AX]        = *B$AC which contains the R4 result
;Exceptions:
;        none
;*******************************************************************************
 
cProc        GetNextRnd,<NEAR>       
 
cBegin                               
        PUSH        DI               
        MOV        AX,[WORD PTR b$RndVar]         ;low half of previous number
        MOV        CX,[RndA]        ;low half of A
        MUL        CX
        XCHG        AX,DI                ;save low half in DI
        MOV        BX,DX                ;  high half in BX
        MOV        AX,[WORD PTR b$RndVar+2] ;high half of previous
        MUL        CX
        ADD        BX,AX                ;sum partial products
        MOV        AX,[RndA]
        MUL        [WORD PTR b$RndVar]         
        ADD        BX,AX                ;last partial product (since we're mod 2^24)
        ADD        DI,[RndC]        ;add in constant C
        ADC        BL,BYTE PTR [RndC]
        XOR        BH,BH                ;extended 24-bit number TO 32 bits FOR NORM
        MOV        DX,DI                ;number in BX:DX
        MOV        [WORD PTR b$RndVar],DX         ;save FOR NEXT time
        MOV        [WORD PTR b$RndVar+2],BX
        POP        DI               
MakeFloat:                       
 
        FILD        b$RndVar        ; PUT 24-bit INTEGER ON numeric stack
        FDIV        FP_2T24         ; ST0 = seed/2^24
        MOV        BX,OFFSET DGROUP:B$AC
        FSTP        DWORD PTR [BX]        ; PUT s.p. equivalent into FAC
        XCHG        AX,BX                ; result IS *R4 in AX
        FWAIT                        ; ensure result in RAM prior TO RETURN
 
cEnd                                ; EXIT TO caller
 
;***[6]
;B$RNZP - RANDOMIZE statement
;void B$RNZP (R8 SeedNum)
;
;Purpose:
;        The number IS set into the middle word of the current RANDOM
;        number AS the seed FOR the NEXT one.
;Entry:
;        R8 SeedNum
;EXIT:
;        A new seed IS created in RndVar, based ON the seed value at entry
;        AND the least significant 2-words of the INPUT parameter.
;Exceptions:
;        none
;*******************************************************************************
 
cProc        B$RNZP,<PUBLIC,FAR>       
        ParmQ        SeedNum         ; R8 seed number
cBegin                               
        LEA        BX,SeedNum+4        ; GET MOST significant digits
        MOV        AX,[BX]         ; GET word of D.P. number
        XOR        AX,[BX+2]        ; XOR with the NEXT word
        MOV        [WORD PTR b$RndVar+1],AX ; replace middle word of current s.p. seed
                                ;        with this value - - now we're reseeded.
cEnd                                ; EXIT

As you can see, we don't have any true randomness with RND in QB64.  In fact, our results are calculated on a mathematical formula!  (Which is why we always get the same results if we don't use RANDOMIZE TIMER to jump to some off point in the list of numbers we generate and use.)

If you're interested in this stuff, then here it is.  If not, then just ignore this topic and trust that RND isn't truly random -- which is why we call it pseduo-random, at best.  ;)

[Qwerkey]

Yes, it's always best to put RANDOMIZE(TIMER) so that this is performed regularly in your running program.

[SMcNeill]

Apparently either the documentation I found is old and didn't apply to QBASIC RND (maybe it was the formula used with some other version Microsoft produced?), or else QB64 uses a different RND formula.

What we actually use is this one (as taken from libqb.cpp):

Code: [Select]

float func_rnd(float n,int32 passed){
    if (new_error) return 0;
   
    static uint32 m;
    if (!passed) n=1.0f;
    if (n!=0.0){
        if (n<0.0){
            m=*((uint32*)&n);
            rnd_seed=(m&0xFFFFFF)+((m&0xFF000000)>>24);
        }
        rnd_seed=(rnd_seed*16598013+12820163)&0xFFFFFF;
    }     
    return (double)rnd_seed/0x1000000;
}
Instead of a formula where Seed = (Seed * 214013 + 2531011) MOD 2 ^ 24, we use one where rnd_seed=(rnd_seed*16598013+12820163)&0xFFFFFF;

Basically the concept is the same, but the formula for the calculations are different in the two versions. 

I wonder how QB64's formula compares against QB45's. If anyone has a version of QB45 they can run, can you kindly tell me what the output might be for the following:

Code: [Select]

FOR i = 1 TO 20
    PRINT RND, Rand
NEXT

FUNCTION Rand
    STATIC Seed
    x1 = (Seed * 214013 + 2531011) MOD 2 ^ 24
    Seed = x1
    Rand = x1 / 2 ^ 24
END FUNCTION

[bplus]

MOD 2^24 puts a limit on the numbers generated to 16+ million but does the rest of the formula even cover that amount?

Hmm... how many times 2^24 should that range be mostly covered? (for normal distribution).
 

[SMcNeill]

MOD 2^24 puts a limit on the numbers generated to 16+ million but does the rest of the formula even cover that amount?

Hmm... how many times 2^24 should that range be mostly covered? (for normal distribution).

The MOD, I think, is mostly there to make certain that we generate a value from 0 to 1.

x1 = (x0 * 214,013 + 2,531,011) MOD 2^24
x0 = the previous RANDOM number (OR the seed, FOR the first one)

So, in the case of the first number, what happens if someone plants a seed which results in a return value greater than 2 ^ 24?

We'd end up with a value which, in the end, would fall outside the 0 to 1 range which the function is built to generate.  The MOD makes certain we never fall outside that boundary. (Such as a RND(2^24) would generate without it.)

[bplus]

The MOD, I think, is mostly there to make certain that we generate a value from 0 to 1.

Yes! I see that.

Do you see that there are only 16+ million actual values that can be generated by this function assuming MOD only generates Whole numbers and not Reals. No matter the seed, MOD will reduce it to < 2^24 or 16+ million values and that is only if all those values can be covered by the rest of the formula. It is possible the rest of the formula will only cycle through some fraction of 16+ million before repeating over and over again.

[xra7en]

Yes, it's always best to put RANDOMIZE(TIMER) so that this is performed regularly in your running program.

I don't remember where I saw this, but for years, I always used

Code: QB64: [Select]

1. RANDOMIZE(-TIMER)

SEEMS to work well.

[MWheatley]

I wonder how QB64's formula compares against QB45's. If anyone has a version of QB45 they can run, can you kindly tell me what the output might be for the following:

Code: [Select]

FOR i = 1 TO 20
    PRINT RND, Rand
NEXT

FUNCTION Rand
    STATIC Seed
    x1 = (Seed * 214013 + 2531011) MOD 2 ^ 24
    Seed = x1
    Rand = x1 / 2 ^ 24
END FUNCTION

The result is an overflow error, as per the attached image.

Malcolm

[Jack002]

I love how subjective computer random generators are. The idea of randomness is so hard to define. Shuffle some cards, now they're random, no, not yet, do it more.

A good psudorandom works well as far as I know. If you can never get a number _ from it, I'd think that is bad. Any time one number is coming out more/less than others, that is bad. A function to replicate the idea seems doable to me.

There was a test for randomness (there are many) the one I like is one that uses a poker format.
Find a way to assign your random number to one of 52 cards, record them in groups of five, then record when you see a pair, two pair, three of a kind, etc, etc, then gather some number of hands (I think a chi square thing would come into play on that number) and then look at the ratios of what hands came out and what you expect from established card probability. I think a pair is just under 50%, like 0.46 or so?

I did this test for school years back using my commodore 64, it turns out to have a very good random number generator, it passed the test

[Bert22306]

I've written two tests for PRNGs, which are attached.

One draws dots in a 2D space, using every adjacent pair of random numbers from the PRNG as x and y coordinates. Very simple code.

The second one fills 10 bins with the random numbers, as they are created by the PRNG, to see whether the distribution is even over time. It also calculates the max so far, min so far, and the running average.

A random number generator has to generate any given value with the same probability as any other value. So over time, you should notice the screen filling up evenly with dots, even if clusters do form here and there. In other words, an empty area in the screen should eventually fill in, even though, in theory, "eventually" could be a very long time. Similarly, one crowded cluster will eventually be no more crowded than the rest of the screen. And using TIMER as the seed, every iteration should look different, in terms of how the screen fills up with dots.

The test with the bins is more precise, but it's also one that would appear to do well with a non-random sequence. For example, a simple repeating sequence of 0 to 1, step 1, will be nice and evenly distributed. Still, if you run that second program, you can see how each try is giving different results, and how over time, things tend to even out.

The two tests show that QB64's PRNG is pretty good. No obvious biases. And, it's nice to have QB64's RANDOMIZE USING feature, to allow you to re-start the pseudo-random sequence, for a given seed value, from the beginning. Couldn't do that with QBasic. Essential if you're writing some sort of monte carlo simulation, where you need to be sure you're using the same random sequence every time, in testing the results.

[Jack002]

Very cool, Bert. Those are great!

[Raven_Singularity]

I was always fascinated by BASIC's RND and RANDOMIZE.  After I figured out how the seed part worked, I came up with clever uses.

For example, I had a game with a top-down map, and wanted the levels to appear semi-random, for example a dirt path was mostly dirt with a bit of mud, so I would set those tiles to 90% likelihood of dirt, 10% chance of mud.  This produced nice looking paths.  The trick was to store the seed used on each level, then when the character returned to that screen, the semi-randomness was the same.  Mud patches in the same place you remember, but different places after starting a new game.  This really added to the feel of the game.  I used this nearly everywhere, such as the edge of water (land bits randomly jutting out into the water), hedges (bits taken out so it wasn't perfectly rectangular), etc.  It was great because storing a single random seed number was just one variable, but allowed me to produce variations for every screen of the game.  I think I used a variable counter + DATE + TIMER for getting actual random numbers after drawing the screen with the fixed seed.

I never saw anyone else using RANDOMIZE this way, having it produce fixed sets of random numbers that could be reused later via the same seed number.  I'm sure lots of people found clever uses for RANDOMIZE seeds, I just never encountered anyone else utilising this oddity of non-random randomness!

[Raven_Singularity]

And, it's nice to have QB64's RANDOMIZE USING feature, to allow you to re-start the pseudo-random sequence, for a given seed value, from the beginning. Couldn't do that with QBasic. Essential if you're writing some sort of monte carlo simulation, where you need to be sure you're using the same random sequence every time, in testing the results.

Didn't read your post until after I wrote mine.  That's exactly how I used QuickBASIC seeds, resetting them by saving and reusing the seed number I passed to RANDOMIZE.  How does this not work?

[bplus]

I never saw anyone else using RANDOMIZE this way, having it produce fixed sets of random numbers that could be reused later via the same seed number.  I'm sure lots of people found clever uses for RANDOMIZE seeds, I just never encountered anyone else utilising this oddity of non-random randomness!

Never say never no more! :)

see line 194:

Code: QB64: [Select]

1. _TITLE "Happy Trails 2018"
2. ' 2017-12-29 another redesign of fireworks
3. ' 2017-12-28 redesign fireworks
4. ' now with lake refelction 2017-12-27 forget the bouncing sparks
5. ' combine Welcome Plasma Font with landscape
6. '_title "Fireworks 3 translation to QB64 2017-12-26 bplus"
7. 'fireworks 3.bas SmallBASIC 0.12.2 [B+=MGA] 2015-05-09
8. 'fireworks 2.bas 2016-05-05 now with Gravity, Newtonian bounce, smoke debris
9. 'fireworks 3.bas try with map variables make bursts around a central point
10.  
11.  
12. RANDOMIZE TIMER
13. CONST xmax = 1200
14. CONST ymax = 720
15. CONST waterline = 600 ' 600 = ratio 5 to 1 sky to water
16. '                       raise and lower waterline as desired  highest about 400?
17. CONST lTail = 15
18. CONST bluey = 5 * 256 ^ 2 + 256 * 5 + 5
19. CONST debrisMax = 28000
20.  
21. SCREEN _NEWIMAGE(xmax, ymax, 32)
22. _SCREENMOVE 120, 20
23.  
24. TYPE fireWorkType
25.     x AS INTEGER
26.     y AS INTEGER
27.     seed AS INTEGER
28.     age AS INTEGER
29.     life AS INTEGER
30. END TYPE
31.  
32.  
33. TYPE debrisType
34.     x AS SINGLE
35.     y AS SINGLE
36.     c AS LONG
37. END TYPE
38.  
39. COMMON SHARED fw() AS fireWorkType
40. COMMON SHARED debris() AS debrisType
41. COMMON SHARED cN, pR!, pG!, pB!
42.  
43. SCREEN _NEWIMAGE(xmax, ymax, 32)
44.  
45. 'prepare message font
46. mess$ = " Happy New Year 2018"
47. PRINT mess$
48. w = 8 * LEN(mess$): h = 16
49. DIM p(w, h)
50. black&& = POINT(0, 10)
51. FOR y = 0 TO h
52.     FOR x = 0 TO w
53.         IF POINT(x, y) <> black&& THEN
54.             p(x, y) = 1
55.         END IF
56.     NEXT
57. NEXT
58. xo = 0: yo = 15: m = 7.2
59. resetPlasma
60.  
61. 'prepare landscape
62. CLS
63. land& = _NEWIMAGE(xmax, ymax, 32)
64. _DEST land&
65. drawLandscape
66. _DEST 0
67.  
68. 'prepare fire works
69. nFW = 3
70. DIM fw(1 TO 10) AS fireWorkType
71. FOR i = 1 TO nFW
72.     initFireWork (i)
73. NEXT
74.  
75. 'debris feild
76. DIM debris(debrisMax) AS debrisType
77.  
78. 'OK start the show
79. WHILE 1
80.     'cls screen with land image
81.     _PUTIMAGE , land&, 0
82.  
83.     'draw fireworks
84.     FOR f = 1 TO nFW
85.         IF fw(f).age <= fw(f).life THEN drawfw (f) ELSE initFireWork f
86.     NEXT
87.  
88.     'debris
89.     FOR i = 0 TO debrisStack
90.         PSET (debris(i).x, debris(i).y), debris(i).c
91.         debris(i).x = debris(i).x + RND * 3 - 1.5
92.         debris(i).y = debris(i).y + RND * 3.5 - 1.5
93.         IF debris(i).x < 0 OR debris(i).y < 0 OR debris(i).x > xmax OR debris(i).y > waterline + RND * 20 THEN NewDebris (i)
94.     NEXT
95.  
96.     'text message in plasma
97.     FOR y = 0 TO h - 1
98.         FOR x = 0 TO w - 1
99.             IF p(x, y) THEN
100.                 changePlasma
101.             ELSE
102.                 COLOR 0
103.             END IF
104.             LINE (xo + x * m, yo + y * m)-(xo + x * m + m, yo + y * m + m), , BF
105.         NEXT
106.     NEXT
107.     lc = lc + 1
108.     IF lc MOD 200 = 0 THEN resetPlasma
109.  
110.     'reflect sky
111.     skyWaterRatio = waterline / (ymax - waterline) - .05
112.     FOR y = waterline TO ymax
113.         FOR x = 0 TO xmax
114.             c&& = POINT(x, waterline - ((y - waterline - 1) * skyWaterRatio) + RND * 5)
115.             PSET (x, y + 1), c&& + bluey
116.         NEXT
117.     NEXT
118.  
119.     _DISPLAY
120.     _LIMIT 200 'no limit needed on my system!
121.  
122.     'accumulate debris
123.     IF lc MOD 2000 THEN
124.         IF debrisStack < debrisMax THEN
125.             FOR i = 1 TO 2
126.                 NewDebris i + debrisStack
127.             NEXT
128.             debrisStack = debrisStack + 2
129.         END IF
130.     END IF
131. WEND
132.  
133. SUB NewDebris (i)
134.     debris(i).x = RND * xmax
135.     debris(i).y = RND * ymax
136.     c = RND * 155
137.     debris(i).c = _RGB32(c, c, c)
138. END SUB
139.  
140. SUB changePlasma ()
141.     cN = cN + .01
142.     COLOR _RGB(127 + 127 * SIN(pR! * .3 * cN), 127 + 127 * SIN(pG! * .3 * cN), 127 + 127 * SIN(pB! * .3 * cN))
143. END SUB
144.  
145. SUB resetPlasma ()
146.     pR! = RND ^ 2: pG! = RND ^ 2: pB! = RND ^ 2
147. END SUB
148.  
149. SUB drawLandscape
150.     'the sky
151.     FOR i = 0 TO ymax
152.         midInk 0, 0, 0, 78, 28, 68, i / ymax
153.         LINE (0, i)-(xmax, i)
154.     NEXT
155.     'the land
156.     startH = waterline - 80
157.     rr = 10: gg = 20: bb = 15
158.     FOR mountain = 1 TO 6
159.         Xright = 0
160.         y = startH
161.         WHILE Xright < xmax
162.             ' upDown = local up / down over range, change along Y
163.             ' range = how far up / down, along X
164.             upDown = (RND * .8 - .35) * (1 / (1 * mountain))
165.             range = Xright + rand&&(5, 35) * 2.5 / mountain
166.             lastx = Xright - 1
167.             FOR X = Xright TO range
168.                 y = y + upDown
169.                 COLOR _RGB32(rr, gg, bb)
170.                 LINE (lastx, y)-(X, ymax), , BF 'just lines weren't filling right
171.                 lastx = X
172.             NEXT
173.             Xright = range
174.         WEND
175.         rr = rand&&(rr + 5, rr): gg = rand&&(gg + 5, gg): bb = rand&&(bb + 4, bb)
176.         IF rr < 0 THEN rr = 0
177.         IF gg < 0 THEN gg = 0
178.         IF bb < 0 THEN bb = 0
179.         startH = startH + rand&&(1, 10)
180.     NEXT
181.     'LINE (0, waterline)-(xmax, ymax), _RGB32(0, 0, 0), BF
182. END SUB
183.  
184. SUB midInk (r1, g1, b1, r2, g2, b2, fr)
185.     COLOR _RGB(r1 + (r2 - r1) * fr, g1 + (g2 - g1) * fr, b1 + (b2 - b1) * fr)
186. END SUB
187.  
188. FUNCTION rand&& (lo&&, hi&&)
189.     rand&& = INT(RND * (hi&& - lo&& + 1)) + lo&&
190. END FUNCTION
191.  
192. SUB drawfw (i)
193.     'here's how to "save" a bunch of random numbers without data and arrays but tons of redundant calculations
194.     RANDOMIZE USING fw(i).seed 'this repeats all random numbers generated by seed in same sequence
195.     'recreate our firework from scratch!
196.     red = rand&&(200, 255)
197.     green = rand&&(200, 255)
198.     blue = rand&&(200, 255)
199.     x = rand&&(1, 4)
200.     IF x = 1 THEN
201.         red = 0
202.     ELSEIF x = 2 THEN
203.         green = 0
204.     ELSEIF x = 3 THEN
205.         blue = 0
206.     ELSE
207.         x = rand&&(1, 4)
208.         IF x = 1 THEN
209.             red = 0: green = 0
210.         ELSEIF x = 2 THEN
211.             green = 0: blue = 0
212.         ELSEIF x = 3 THEN
213.             blue = 0: red = 0
214.         END IF
215.     END IF
216.     ne = rand&&(80, 300)
217.     DIM embers(ne, 1)
218.     FOR e = 0 TO ne
219.         r = RND * 3
220.         embers(e, 0) = r * COS(e * _PI(2) / 101)
221.         embers(e, 1) = r * SIN(e * _PI(2) / 101)
222.     NEXT
223.     start = fw(i).age - lTail ' don't let tails get longer than lTail const
224.     IF start < 1 THEN start = 1
225.     FOR e = 0 TO ne
226.         cx = fw(i).x: cy = fw(i).y: dx = embers(e, 0): dy = embers(e, 1)
227.         FOR t = 1 TO fw(i).age
228.             cx = cx + dx
229.             cy = cy + dy
230.             IF t >= start THEN
231.                 'too much like a flower?
232.                 midInk 60, 60, 60, red, green, blue, (t - start) / lTail
233.                 'midInk 60, 60, 60, 128, 160, 150, (t - start) / lTail
234.                 fcirc cx, cy, (t - start) / lTail
235.             END IF
236.  
237.             dx = dx * .99 'air resitance
238.             dy = dy + .01 'gravity
239.         NEXT
240.         COLOR _RGB32(255, 255, 255)
241.         'COLOR _RGB32(red, green, blue)
242.         cx = cx + dx: cy = cy + dy
243.         fcirc cx, cy, (t - start) / lTail
244.     NEXT
245.     fw(i).age = fw(i).age + 1
246. END SUB
247.  
248. SUB initFireWork (i)
249.     fw(i).x = rand&&(.1 * xmax, .9 * xmax)
250.     fw(i).y = rand&&(.1 * ymax, .5 * ymax)
251.     fw(i).seed = rand&&(0, 32000)
252.     fw(i).age = 0
253.     fw(i).life = rand&&(20, 120)
254. END SUB
255.  
256. 'Steve McNeil's  copied from his forum   note: Radius is too common a name
257. SUB fcirc (CX AS LONG, CY AS LONG, R AS LONG)
258.     DIM subRadius AS LONG, RadiusError AS LONG
259.     DIM X AS LONG, Y AS LONG
260.  
261.     subRadius = ABS(R)
262.     RadiusError = -subRadius
263.     X = subRadius
264.     Y = 0
265.  
266.     IF subRadius = 0 THEN PSET (CX, CY): EXIT SUB
267.  
268.     ' Draw the middle span here so we don't draw it twice in the main loop,
269.     ' which would be a problem with blending turned on.
270.     LINE (CX - X, CY)-(CX + X, CY), , BF
271.  
272.     WHILE X > Y
273.         RadiusError = RadiusError + Y * 2 + 1
274.         IF RadiusError >= 0 THEN
275.             IF X <> Y + 1 THEN
276.                 LINE (CX - Y, CY - X)-(CX + Y, CY - X), , BF
277.                 LINE (CX - Y, CY + X)-(CX + Y, CY + X), , BF
278.             END IF
279.             X = X - 1
280.             RadiusError = RadiusError - X * 2
281.         END IF
282.         Y = Y + 1
283.         LINE (CX - X, CY - Y)-(CX + X, CY - Y), , BF
284.         LINE (CX - X, CY + Y)-(CX + X, CY + Y), , BF
285.     WEND
286. END SUB
287.  

Another great use of Randomize Using Seed is for encoding messages for cryptography.

[Raven_Singularity]

Fireworks, landscapes, water reflections, and reusing random number sequences?

Sign me up!  I'll check it out once I'm back on Desktop, sounds very cool.

Are you reusing the random sequence to recreate the same firework as a reflection in the water?

Could you not just draw the firework twice at the time of generating the random numbers?