How non-random was QB's RND

General FreeBASIC programming questions.
deltarho[1859]
Posts: 2092
Joined: Jan 02, 2017 0:34
Location: UK

Re: How non-random was QB's RND

Postby deltarho[1859] » Nov 23, 2017 7:28

xlucas wrote:The formula still looks to me like a LCG

You are right, it is.' And &hFFFFFF' will give the same result as 'Mod 2^24'.

Interestingly, Microsoft Visual Basic 6 and earlier uses 43FD43FD and C39EC3 for the multiplier and increment respectively in it's 24 bit generator. counting_pine's multiplier is FD43FD but he did say "something like".

However, I cannot get the VB6 formula to work, yet.

"By the way, is 4294967296 a power of two?"
Yes, 2^32. I was just giving the CPU less work to do.<laugh> So, we could use 'And 4294967295' rather than 'Mod 4294967296'. We cannot use &hFFFFFFFF because that is interpreted as -1.
lizard
Posts: 440
Joined: Oct 17, 2017 11:35
Location: Germany

Re: How non-random was QB's RND

Postby lizard » Nov 23, 2017 10:29

Have you tried this?

Code: Select all

Dim As Short x, y, c, r

Screen 12

Randomize , 4

Do
   c = Int(Rnd * 16)
   r = Int(Rnd * 16)
   x = Int(Rnd * 4000)
   y = Int(Rnd * 3000)
 
   PSet (x, y),  c ^ r

Loop Until Len(InKey)


Really funny. :-)
deltarho[1859]
Posts: 2092
Joined: Jan 02, 2017 0:34
Location: UK

Re: How non-random was QB's RND

Postby deltarho[1859] » Nov 23, 2017 11:32

I'd like to know the actual formula being used as this QBASIC equivalent seems to be fundamentally flawed.
Yours truly wrote:We cannot use &hFFFFFFFF because that is interpreted as -1.

In this case we should use &hFFFFFFFFul and force it to be unsigned.
counting_pine
Site Admin
Posts: 6173
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Re: How non-random was QB's RND

Postby counting_pine » Nov 23, 2017 14:09

deltarho[1859] wrote:Interestingly, Microsoft Visual Basic 6 and earlier uses 43FD43FD and C39EC3 for the multiplier and increment respectively in it's 24 bit generator. counting_pine's multiplier is FD43FD but he did say "something like".

Doing the math modulo 2^24 effectively just chops off the high '43' anyway.
dodicat
Posts: 5991
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: How non-random was QB's RND

Postby dodicat » Nov 23, 2017 14:15

Here is the code from C

Code: Select all


#macro Here_is_the_Ccode
static double hRnd_QB ( float n )
{
   union {
      float f;
      uint32_t i;
   } ftoi;

   if( n != 0.0 ) {
      if( n < 0.0 ) {
         ftoi.f = n;
         uint32_t s = ftoi.i;
         iseed = s + ( s >> 24 );
      }
      iseed = ( ( iseed * 0xFD43FD ) + 0xC39EC3 ) & 0xFFFFFF;
   }
   return (float)iseed / (float)0x1000000;
}
#endmacro



function rnd_QB(n as single) as double
    union z
        as single f
        as ulong i
    end union
    dim as Z ftoi
    dim as ulong s
    static as ulong iseed=327680
    if( n <> 0.0 ) then
      if( n < 0.0 ) then
         ftoi.f = n
          s = ftoi.i
         iseed = s + ( s shr 24 )
      end if
      iseed = ( ( iseed * &hFD43FD ) + &hC39EC3 ) and &hFFFFFF
   end if
    return cdbl(iseed )/ cdbl(&h1000000)
end function







Dim As Short x, y, c, r

Screen 12

Randomize , 4

Do
   x = Int(Rnd_qb(4) * 640)
   y = Int(Rnd_qb(4) * 480)
   c = Int(Rnd_qb(4) * 16)
   r = Rnd_qb(4)
   PSet (x, y), c
Loop Until Len(InKey)

A non optimised straight translate.
jj2007
Posts: 1259
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: How non-random was QB's RND

Postby jj2007 » Nov 23, 2017 15:14

dodicat wrote:Here is the code from C
Diagonal patterns as well...

Here is one with a switch: useMb=1 uses the MasmBasic Rand() algo. For useMb=0, you get QB. The result is pretty clear but have a closer look...

Code: Select all

const maxloops=   20000000
const useMb=   1
Static Shared As Long MasmBasicSeed=&h6f616943
Function MbRnd naked cdecl(byval xmul as long) As double
  Asm   ' copyright Antariy, see http://www.masmforum.com/board/index.php?topic=11679.msg123276
   mov eax, MasmBasicSeed
   imul eax, eax, -127
   add eax, -124
   bswap eax
   mov MasmBasicSeed, eax
   fild dword ptr [esp+4]
   push 0
   push eax
   fild qword ptr [esp]
   push 796917760
   fld dword ptr [esp]
   fmulp
   fmulp
   pop eax
   pop eax
   pop eax
   ret
  End Asm
End Function

Dim As ulong x, y, c, r
Dim As ulong ct
Screen 12
asm mov eax, MasmBasicSeed

Randomize, 4
ct=0
Do
  if useMb then
    x = MbRnd(640)
    y = MbRnd(480)
    c = MbRnd(16)
    r = MbRnd(1000)
  else
    x = Int(Rnd() * 640)
    y = Int(Rnd() * 480)
    c = Int(Rnd() * 16)
    r = Rnd()*1000
  endif
  ' print x, y, c, r
   PSet (x, y), c and 3
   ct=ct+1
Loop Until Len(InKey) or ct>maxloops
Sleep
dodicat
Posts: 5991
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: How non-random was QB's RND

Postby dodicat » Nov 23, 2017 16:20

Thanks jj2007
I notice that every even call to the function produces an even seed.
The other calls produce even or odd seeds.
It doesn't need to be four calls in a loop to produce a pattern, any even number of calls produces a pattern, but calls mod four are more easily seen.
You can check this in my previous but one code snippet.
'
Anyway, at the top of this snippet change the modnumber.
Even modnumbers --> even seed
Odd modnumbers --> even or odd seed.

So I deduce that the algo is efficient only at odd number calls.
This runs for 1.25 seconds only to keep the output string from bloating.

Code: Select all



dim shared as ulong modnum=12
dim shared as string acc

function rnd_QB(n as single) as double
    union z
        as single f
        as ulong i
    end union
    dim as Z ftoi
    dim as ulong s
    static as ulong iseed=327680
    if( n <> 0.0 ) then
      if( n < 0.0 ) then
         ftoi.f = n
          s = ftoi.i
         iseed = s + ( s shr 24 )
      end if
      iseed = ( ( iseed * &hFD43FD ) + &hC39EC3 ) and &hFFFFFF
     if iseed mod modnum=0 then acc+=right(str(iseed),1) + " "
   end if
    return cdbl(iseed )/ cdbl(&h1000000)
end function

dim as long w=loword(width) 'initial console width


Dim As Short x, y, c, r

Screen 12
dim as double t=timer
Do
   x = Int(Rnd_qb(4) * 640)
   y = Int(Rnd_qb(4) * 480)
   c = Int(Rnd_qb(4) * 16)
   r = Rnd_qb(4)
   
   
  ' r=Rnd_qb(4)
   'r=Rnd_qb(4)
   
   
   PSet (x, y), c
   if timer-t>1.25 then exit do
Loop Until Len(InKey)

screen 0
width w,30000
print "start"
print acc
sleep
 
deltarho[1859]
Posts: 2092
Joined: Jan 02, 2017 0:34
Location: UK

Re: How non-random was QB's RND

Postby deltarho[1859] » Nov 23, 2017 16:58

I should have used &hfffffful and not &hffffff

Code: Select all

Dim Shared Rand As Double

Function RandQB() As Double
  Rand = (16598013*Rand + 12820163) and &hfffffful
  Return Rand/16777216 ' Normalise
End Function

Rand = 123456 ' Seed the generator
deltarho[1859]
Posts: 2092
Joined: Jan 02, 2017 0:34
Location: UK

Re: How non-random was QB's RND

Postby deltarho[1859] » Nov 23, 2017 18:10

If we don't normalise my RandQB and use 'Return Rand' I get 'even Rand => odd Rand' and 'odd Rand => even Rand',

So, if we seed the generator with an even number the first number 'out of the trap' is odd and vice versa.

We get exactly the same behaviour with the Numerical Recipes RandNR but no striping.
deltarho[1859]
Posts: 2092
Joined: Jan 02, 2017 0:34
Location: UK

Re: How non-random was QB's RND

Postby deltarho[1859] » Nov 23, 2017 19:10

If I reduce RandNR to 24 bit from 32 bit no striping occurs.

However, if I go further and reduce RandNR to 16 bit then I get striping but only if I keep 'r'. If I comment 'r' then no striping.

So, QBASIC's generator, whilst supposedly being a 24 bit generator, may not be giving us the 'full monty'. In other words some of those 24 bits may not be as random as they should be.
xlucas wrote:I don't think the people who made QB chose random coefficients.

I don't either but they may not have been sufficiently robust in their choice of the multiplier when the increment is not zero.

QBASIC's generator may simply be a bad LCG.
dodicat
Posts: 5991
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: How non-random was QB's RND

Postby dodicat » Nov 23, 2017 19:50

Here is a workaround repair to the qb generator.
(I have discarded useless bits of the C code sample)

Code: Select all



function rnd_QB() as double
    static as ulong n:n+=1
    static as ulong iseed=327680
    iseed = ( ( iseed * &hFD43FD ) + &hC39EC3 ) and &hFFFFFF
    if  (n and 1)  =0 then  iseed = ( ( iseed * &hFD43FD ) + &hC39EC3 ) and &hFFFFFF 'only use an odd seed
    if  (n and 255)=0 then n=0 'reset after a while
    return iseed /&h1000000
end function



Dim As Short x, y, c, r

 
Screen 12
dim as double t=timer
Do
   
   x = Int(Rnd_qb() * 640)
   y = Int(Rnd_qb() * 480)
   c = Int(Rnd_qb() * 16)
   r = Int(Rnd_qb())
   
   
  'r=Rnd_qb()
   'r=Rnd_qb(4)
   
   
   PSet (x, y), c
 
Loop Until Len(InKey)


 
deltarho[1859]
Posts: 2092
Joined: Jan 02, 2017 0:34
Location: UK

Re: How non-random was QB's RND

Postby deltarho[1859] » Nov 23, 2017 20:14

Very crafty, dodicat.
deltarho[1859]
Posts: 2092
Joined: Jan 02, 2017 0:34
Location: UK

Re: How non-random was QB's RND

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

Thought I'd give RandNR and RandQB a look over with PractRand. RandNR was reduced to a 24 bit generator. I had to do a rewrite of the program to feed PractRand because I normally push 32 bits through and not 24 bits.

PractRand is lethal, with xoroshiro128+ choking at 64GB and Mersenne Twister coming unstuck at 256GB. It took exception to RandNR and RandQB at the first hurdle. PractRand does not mess about with MB dumps and needs GB dumps.

Since we are dealing with an 'olde worlde' generator I got DieHarder out of hibernation and dumped 5MB of 24 bits giving 15MB dumps - Marsaglia recommended between 10MB and 20MB.

Dieharder has 15 tests and RandNR failed some of them. The only saving grace for RandNR was that RandQB did even worse. I thought RandNR would do better.

I think it fair to say, with the work done above, that the answer to this thread's title is 'More than it should be'. Given what is on offer with the other FB algorithm's, and the ones that I have written, 'Randomize ,4' should be given a wide berth. <smile>

I should have gone to Randomness Tests first. 24 bit LCGs do not do very well. Randomize ,2 is MWC.
deltarho[1859]
Posts: 2092
Joined: Jan 02, 2017 0:34
Location: UK

Re: How non-random was QB's RND

Postby deltarho[1859] » Nov 24, 2017 1:55

It is worth mentioning that dodicat's last code, the crafty one, will work equally well if we 'only use an even seed'. As I mentioned earlier both RandNR and RandQB alternate between even and odd. It still begs the question why do we need a workaround for RandQB and not RandNR (in 24 bit mode).
dodicat
Posts: 5991
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: How non-random was QB's RND

Postby dodicat » Nov 24, 2017 20:50

Here are the three variants of QB rnd.

Code: Select all


function rnd_QBO() as double
    static as long n=1:n=-n
    static as ulong iseed=327680
    iseed = ( ( iseed * &hFD43FD ) + &hC39EC3 ) and &hFFFFFF
    if n=1 then  iseed = ( ( iseed * &hFD43FD ) + &hC39EC3 ) and &hFFFFFF 'only use an odd seed
    return iseed /&h1000000
end function

function rnd_QBE() as double
    static as long n=1:n=-n
    static as ulong iseed=327680
    iseed = ( ( iseed * &hFD43FD ) + &hC39EC3 ) and &hFFFFFF
    if n=-1 then  iseed = ( ( iseed * &hFD43FD ) + &hC39EC3 ) and &hFFFFFF 'only use an even seed
    return iseed /&h1000000
end function

function rnd_QBM() as double
    static as ulong iseed=327680
    iseed = ( ( iseed * &hFD43FD ) + &hC39EC3 ) and &hFFFFFF           'original odd and even
    return iseed /&h1000000
end function

Function incircle(cx As long,cy as long,rad as long,a as single,mx as long,my as long) As long
    If (a)<=1 Then
        Return(a)*((cx)-(mx))*(a)*((cx)-(mx)) +((cy)-(my))*((cy)-(my))<= (rad)*(rad)*(a)*(a)
    Else
        Return(a)*((cx)-(mx))*(a)*((cx)-(mx)) +((cy)-(my))*((cy)-(my))<= (rad)*(rad)
    End If
End Function


dim as function() as double f(2)
f(0)= @rnd_QBO
f(1)= @rnd_QBE
f(2)= @rnd_QBM
dim as string s(...)={"ODD","EVEN","ORIGINAL"}

#macro pixel(k)
   x = Int(f(k)() * 640)
   y = Int(f(k)() * 480)
   c = Int(f(k)() * 16)
   r = Int(f(k)())
   if incircle(100+200*k,240,150,1.75,x,y) then PSet(x,y),c
   draw string(100+200*k,440),s(k)
#endmacro


Dim As Short x, y, c, r

Screen 12
dim as long k
Do
    k+=1:k=k mod 3
    pixel(k)
Loop Until len(inkey)


 

 

But I would use the odd distribution as preference.

Return to “General”

Who is online

Users browsing this forum: No registered users and 2 guests