How non-random was QB's RND

General FreeBASIC programming questions.
xlucas
Posts: 256
Joined: May 09, 2014 21:19
Location: Argentina

How non-random was QB's RND

Postby xlucas » Nov 22, 2017 1:14

Just wanted to post a slightly modified short BAS program I made in 1994 in QuickBasic. I don't know what I was trying to do and suddenly, I got this result, which made me realise how non-random QB's RND was, so I saved it. Now, when I saw FB is capable of reproducing the same RND function, I wondered if it really would be identical, so I tried it and here it is. This is what I saw on my first computer in 1994, when I was playing with RND:

Code: Select all

Dim As Short x, y, c, r

Screen 12

Randomize , 4

Do
   x = Int(Rnd(4) * 640)
   y = Int(Rnd(4) * 480)
   c = Int(Rnd(4) * 16)
   r = Rnd(4)
   PSet (x, y), c
Loop Until Len(InKey)
counting_pine
Site Admin
Posts: 5815
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Re: How non-random was QB's RND

Postby counting_pine » Nov 22, 2017 14:02

Woah.

Code: Select all

Dim As Short x, y, c, r

Screen 12

Randomize , 4

Do
   x = Int(Rnd() * 640)
   y = Int(Rnd() * 480)
   c = Int(Rnd() * 16)
   r = Rnd()
   PSet (x, y), c and 3
Loop Until Len(InKey)

There is heavy "striping" in the second bit, and a thinner stripe in the first bit.

I guess there is a heavy correlation between int(rnd * 640 - rnd * 480), and (int(rnd * 16) mod 4).

For what it's worth, the 24-bit values are generated with something like: r(i+1) = (r(i) * &hFD43FD + &hC39EC3) and &hFFFFFF.

Each bit pattern repeats with 2^n period, such that r(i) == r(i - 2^n) (mod 2^n).
(Or in other words, the last bit has a period of just 2, the one before has a period of 4, etc.)

But it's still difficult to see how this happens.
jj2007
Posts: 181
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: How non-random was QB's RND

Postby jj2007 » Nov 22, 2017 15:50

If you comment out the r=Rnd(4), it looks a lot more random. What is the role of that line?
Munair
Posts: 358
Joined: Oct 19, 2017 15:00
Location: 't Zand, NL
Contact:

Re: How non-random was QB's RND

Postby Munair » Nov 22, 2017 16:18

jj2007 wrote:If you comment out the r=Rnd(4), it looks a lot more random. What is the role of that line?

It forces the randomizer to stay within the range 0-4.
dodicat
Posts: 4475
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: How non-random was QB's RND

Postby dodicat » Nov 22, 2017 18:23

Rnd * 4 is in range 0 to 4

the rnd(n) is in range 0 to 1
Mathematically [0,1) or thereabouts, not actually getting the full 1, but getting the zero now and then (extremely rarely actually if you test)

See the help file for details.
https://www.freebasic.net/wiki/wikka.php?wakka=KeyPgRnd

Code: Select all

'Randomize , 4
for n as long=1 to 40
    print rnd(4),rnd*4
next
sleep

 
jj2007
Posts: 181
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: How non-random was QB's RND

Postby jj2007 » Nov 22, 2017 19:43

All that is clear so far, and not surprising. But
r = Rnd()
produces non-random stripes, while
'r = Rnd()
looks much better. Same for
r = Rnd()
r = Rnd()
so my best guess is that calling Rnd() four times in a row causes some kind of repetition. Pretty odd anyway...
deltarho[1859]
Posts: 733
Joined: Jan 02, 2017 0:34
Location: UK

Re: How non-random was QB's RND

Postby deltarho[1859] » Nov 22, 2017 21:25

Munair wrote:It forces the randomizer to stay within the range 0-4.

That is not correct. (4) is redundant.

We enter the sequence according to the value of Timer.

x, y and c are determined and the next in the sequence is discarded. New values for x, y and c are determined and the next in the sequence is discarded and so on.

The pattern then is 'use 3, skip 1'.

Here is what we get by placing r = Rnd in different positions.

A: 'skip 1, use 3' => Stripes
B: 'use 1, skip 1, use 2' => No stripes
C: 'use 2, skip 1, use 1' => No stripes
D: 'use 3, skip 1' => Stripes

All of them settle down into a 'use 3' consecutive values.

For the moment I am baffled why A: and D: produce striping.

My guess is that this phenomenon has nothing to do with the random number generator but is to do with graphics and I am now outside of my comfort zone. <smile>

By the way, the reason why we have [0,1) is because of normalising, the upper bound is (2^24-1)/2^24 = 0.9999999404. With the 32 bit generators we have (2^32-1)/2^32 = 0.9999999998
deltarho[1859]
Posts: 733
Joined: Jan 02, 2017 0:34
Location: UK

Re: How non-random was QB's RND

Postby deltarho[1859] » Nov 22, 2017 22:33

Yours truly wrote:My guess is that this phenomenon has nothing to do with the random number generator but is to do with graphics and I am now outside of my comfort zone.

May be not. We do not get striping with the other algorithms, just algorithm 4; the only 24 bit generator. Perhaps, as thought, it is not the generator, per se, but the fact that is 24 bit.
dodicat
Posts: 4475
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: How non-random was QB's RND

Postby dodicat » Nov 22, 2017 23:11

Every fourth (or multiple of four) calls to rnd, produces less randomness.
Seen graphically, but not so noticeable by frequency of numbers.

Code: Select all

#include "crt.bi"
Dim As Short x, y, c, r

Screen 12

Randomize , 4

dim as long ac(16),ax(640),ay(480)

#macro Rd(n)
for z as long=1 to n+1
    r+=rnd()
    next
#endmacro
   
Do
   x = Int(Rnd() * 640):ax(x)+=1
   y = Int(Rnd() * 480):ay(y)+=1
   c = Int(Rnd() * 16) :ac(c)+=1
   
   Rd(8) '0,4,8, ....
   PSet (x, y), c
Loop Until Len(InKey)
screen 0
width 120,900
print "num"," x","  y","c"
for n as long=0 to 640'16
    print n,ax(n),iif(n<=480,str(ay(n))," "),iif(n<=16,str(ac(n))," ")
next

sleep

 

That's the observation anyway.
The reason is another thought train.
xlucas
Posts: 256
Joined: May 09, 2014 21:19
Location: Argentina

Re: How non-random was QB's RND

Postby xlucas » Nov 23, 2017 0:06

deltarho wrote:That is not correct. (4) is redundant.


Ooops! Actually, that parameter 4 is a mistake I made. It wasn't present in the original code I wrote in the 90s. What happened is that I "misremembered" that FB allowed one to select the PRNG method by changing the parameter in RND, so I started trying different parameters. At 4, I stopped, because I realised I was doing something wrong, so I looked up in the wiki and saw it was with RANDOMIZE, so I added that line, but forgot to remove the (4)'s. So you can just ignore the fours.

And yes, it looks like there's a cycle at four requests. Each band appears to have many possible colours for the pixels there, but it turns out each of the 16 colours necessarily ends either on the "even" or "odd" bands... and my guess is that maybe "odd" colours end up on the "odd" bands, for example. So that means the lower bit in the colour number, which happens to represent red in the default 16 bit colour palette, is present in some bands and not in others, which becomes very noticeable once the screen is almost full.

I remember how puzzled I was when this happened to me back then. I knew very little programming, so I couldn't stand a chance to understand the reason why this was so. I just realised it was a significant finding and I saved it as a BAS.
jj2007
Posts: 181
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: How non-random was QB's RND

Postby jj2007 » Nov 23, 2017 1:26

I am not sure if the random generator is to blame:

Code: Select all

   c = Int(Rnd() * 16)

Try e.g. *4 or *12 or *1000... or see if you can recognise a pattern here:

Code: Select all

Dim As Short x, y, c, r
Dim As long ct

Screen 12

Randomize, 4
ct=0
Do
   x = Int(Rnd() * 640)
   y = Int(Rnd() * 480)
   c = Int(Rnd() * 16)
   r = Rnd()
   PSet (x, y), c and 3
   if ct < 30 Then
   ct=ct+1
      print ct, c, c and 3
      if ct=30 Then Sleep
   endif
Loop Until Len(InKey)
xlucas
Posts: 256
Joined: May 09, 2014 21:19
Location: Argentina

Re: How non-random was QB's RND

Postby xlucas » Nov 23, 2017 3:04

Well, yes and no. The PRNG is very good for most tasks. If you just use a few requests, then it's impossible to notice anything. On the other hand, I found this pattern after only one year of playing with QB, without looking for anything and completely by chance. What I mean is, another person, more experienced and purposedly trying to break a PRNG can surely find correlations very easily. Which is fine... QB's RND wasn't designed for high security, I reckon.

What I observe by zooming in is a series of bands at an angle of roughly 45 degrees and with a with of about 4 pixels each. On each band, only certain colours are present. Starting from the origin, I see:

Band 0 - Colours 1, 9, 5 and 13
Band 1 - Colours 0, 8, 4 and 12
Band 2 - Colours 3, 11, 7 and 15
Band 3 - Colours 2, 10, 6 and 14
Band 4 - Like band 0
(and repeats)

So there are four band sends. Notice that the colours on each band are calculated starting from a number that cycles 3, 2, 1, 0. Call this number n and what we've got is colours n, n + 4, n + 8 and n + 12; that is, all n + 4k with k an integer such that the colour number goes from 0 to 15. The band widths are not exactly 4 and the angle is not exactly 45 degrees. Adjusting the multipliers (640 and 480 in this case) should allow making this more exact. I ignore what the optimal values would be, but it appears that a proportion of 4/3 is quite good at approximating a 45 degree angle. Finding the exact proportion so that the angle is exactly 45 degrees and the exact scale, so that the bands are exactly 1 pixel wide would mean that the bands would be representing x + y. What this suggests is that the PRNG is based on a lineal function with certain fixed coefficients and a fixed modulo. Pretty much like the function counting_pine gave.

Wow! And now look at this:

Code: Select all

Dim As Short x, y, c, r

Screen 12

Randomize , 4

Do
   x = Int(Rnd * 4000)
   y = Int(Rnd * 3000)
   c = Int(Rnd * 16)
   r = Int(Rnd * 16)
 
   PSet (x, y), c + r
Loop Until Len(InKey)
deltarho[1859]
Posts: 733
Joined: Jan 02, 2017 0:34
Location: UK

Re: How non-random was QB's RND

Postby deltarho[1859] » Nov 23, 2017 3:22

I don't think that the number of requests is an issue. counting_pine's function uses 'r' which confuses with the 'r' used in the code so I have rewritten it as

Code: Select all

f(i+1) = (f(i) * &hFD43FD + &hC39EC3) and &hFFFFFF

So, the 'i+1' random number is a function of the 'i' random number which in turn is a function of the 'i-1' random number and so on.

That 'pattern' is disrupted when we determine 'r' and discard it.

However, it depends upon when we discard 'r'. For some reason with my A, B, C and D above the stripes occur when we discard the random number generated prior to determining x; with A: and D:. Determining 'x' is, of course, determining the next horizontal pixel position.

From the formula 'x' is a function of 'r'. If we comment 'r' then 'x' is a function of 'c'.

We may find this behaviour with any Linear Congruential Generator, as xlucas suggested.

We still have not got the answer, but are we getting any closer?

Added: With xlucas last code we are not discarding now. Have a look at determining 'r' just after 'x'.
deltarho[1859]
Posts: 733
Joined: Jan 02, 2017 0:34
Location: UK

Re: How non-random was QB's RND

Postby deltarho[1859] » Nov 23, 2017 5:21

Yours truly wrote:We may find this behaviour with any Linear Congruential Generator

Nope. <smile>

Strictly speaking counting_pine's formula is not a Linear Congruential Generator.

This is a Linear Congruential Generator (LCG).

Code: Select all

x(n+1) = (a*x(n) + c) Mod m

If we use the LCG from Numerical Recipes (32 bit), which I have called RandNR, and execute the following:

Code: Select all

Dim Shared z As Double
 
Function RandNR() As Double
  z = ((1664525*z + 1013904223) Mod 4294967296)
  Return z/4294967296 ' Normalise
End Function
 
Dim As Short x, y, c, r
 
Screen 12
 
z = 1234 ' Seed the generator
 
Do
  x = Int(RandNR * 640)
  y = Int(RandNR * 480)
  c = Int(RandNR * 16)
  r = RandNR
  PSet (x, y), c
Loop Until Len(InKey)

we don't get any patterns and it makes no odds whether 'r' is discarded or not or where 'r' is placed.
xlucas
Posts: 256
Joined: May 09, 2014 21:19
Location: Argentina

Re: How non-random was QB's RND

Postby xlucas » Nov 23, 2017 6:33

deltarho wrote:We still have not got the answer, but are we getting any closer?


I think we already have like half the answer, ha, ha. I've been thinking about this and testing the code. I haven't been able to make your LCG produce the same results, but I think that makes sense.

deltarho wrote:Strictly speaking counting_pine's formula is not a Linear Congruential Generator.


I considered this, but I still think it is. See. In counting_pine's formula:

Code: Select all

f(i+1) = (f(i) * &hFD43FD + &hC39EC3) and &hFFFFFF

i corresponds to n, f(i) corresponds to x(n) for every i and n, &HFD43FD is our a and &HC39EC3 is our c. Anding this with &HFFFFFF is the same as dropping the most significant bits and keeping the lowest 24 bits, that is, calculating the modulo 2^24. The formula still looks to me like a LCG.

But it still does make sense to me that not just any LCG gives this particular result. I do expect any LCG to produce this kind of correlation, but not this particular correlation. The reason, I reckon, lies in the prime factorings of a and c and, more importantly, in the choice of the modulus. For an optimal LCG, the coefficients should be prime or at least, mutually coprime and definitely coprime with the modulus. In this case, the modulus is a power of two, so as long as the coefficients are both odd and comprime with each other, the cycle length should be very large. I don't think the people who made QB chose random coefficients. They must've known this. But there's still a problem.

If instead of taking a whole sample, you throw away the least significant bits of the sample (exactly what happens when you do [b]Int(Rnd * k)[b] with k a power of two), you're effectively shortening the cycle... a lot (in my code, I used k = 16 for the colour). The cycle might still be pretty large, but who knows... it all depends on the coefficients. For your coefficients, maybe you get similar results if you take 7 RNDs per loop iteration instead of 4. After all, the effect of my code only happens if you take 4. I think that, if the samples were going to be normalised and put in a double, they should've used a modulus that weren't a power of two, say, a power of three, and make sure none of the coefficients were divisible by three. This would have prevented any artifacts caused by people anding the samples.

By the way, is 4294967296 a power of two?
All this sounds like I think I have it all very clear, but it's all a lot of guessing and thinking on the fly, so take me seriously, but not that much, ha, ha.

Return to “General”

Who is online

Users browsing this forum: No registered users and 2 guests