Pseudo random number generator

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
AGS
Posts: 1284
Joined: Sep 25, 2007 0:26
Location: the Netherlands

Pseudo random number generator

Postby AGS » May 08, 2014 0:17

This example is an implementation of a pseudo random number generator.
It was copied and translated by me from
http://www0.cs.ucl.ac.uk/staff/d.jones/ ... iceRNG.pdf
There are more examples of prng implementations in the paper
(and some tips on how to use/write a (p)rng).

The period of the generator is 2 ^ 121.
(FYI: built-in rnd() has a period of (2^219937) - 1)

You must properly seed the generator (JKISS32) for it to generate
random numbers. Seeding it is done by calling initialize at least once before
calling JKISS32 (similar to calling randomize() before using rnd()).

The example uses rnd() to seed JKISS32.
Other ways to seed JKISS32 would be to use the OS provided random number generator.
On win32 you could use function rand_s.
On linux you could use numbers read from either /dev/random or /dev/urandom.

A couple of remarks on the fb code.

I changed the original code of JKISS32 a tiny bit. I removed
the global variables and changed those into procedure parameters. This should
not have any impact on random number generation.
The C version of JKISS32 sometimes generates negative numbers whereas the fb version does not.

Code: Select all

/' Implementation of a 32-bit KISS generator which uses no multiply instructions '/

sub initialize(byref x as uinteger, byref y as uinteger,_
               byref z as uinteger, byref w as uinteger,_
               byref c as uinteger)

  randomize()
  x = cast(uinteger, rnd()*5000000+1)
  y = cast(uinteger, rnd()*5000000+1)
  z = cast(uinteger, rnd()*5000000+1)
  w = cast(uinteger, rnd()*5000000+1)
  c = 0

end sub

function JKISS32(byref x as uinteger, byref y as uinteger,_
                 byref z as uinteger, byref w as uinteger,_
                 byref c as uinteger) as uinteger

  dim t as integer
  y xor= (y shl 5):y xor= (y shr 7):y xor= (y shl 22)
  t = z+w+c:z = w: c = t < 0: w = t and 2147483647
  x += 1411392427
  return x + y + w

end function

sub my_main()
  dim x as uinteger
  dim y as uinteger
  dim z as uinteger
  dim w as uinteger
  dim c as uinteger

  initialize(x,y,z,w,c)

  dim ct as integer = 1
  for i as integer = 0 to 100
    var result = JKISS32(x,y,z,w,c)   
    print using "##############";result;" ";
    if (ct = 6) then
      print
      ct = 1
    else
      ct += 1
    end if
  next i
end sub

my_main()
srvaldez
Posts: 2550
Joined: Sep 25, 2005 21:54

Re: Pseudo random number generator

Postby srvaldez » May 08, 2014 1:51

interesting stuff.
sean_vn
Posts: 283
Joined: Aug 06, 2012 8:26

Re: Pseudo random number generator

Postby sean_vn » Jul 18, 2014 3:16

You could try this one:
http://xorshift.di.unimi.it/

I have an Intel IvyBridge so I should be able to use the RDRAND machine instruction to get a hardware generated random number. But..... Intel goofed up and there is a hardware bug on some of the processors, including mine.
AGS
Posts: 1284
Joined: Sep 25, 2007 0:26
Location: the Netherlands

Re: Pseudo random number generator

Postby AGS » Jul 19, 2014 5:02

sean_vn wrote:You could try this one:
http://xorshift.di.unimi.it/

I have an Intel IvyBridge so I should be able to use the RDRAND machine instruction to get a hardware generated random number. But..... Intel goofed up and there is a hardware bug on some of the processors, including mine.


Thanks for the link. I implemented the fastest PRNG available at xorshift.di.unimit.it and compared it's speed with rnd() and the example code. When I compile the code from xorshift using the asm back end (no error handling) it generates random numbers at half the speed of built - in rnd(). The example code, when compiled using the same options, matches the speed of built - in rnd(). But the example PRNG has a much shorter period than the generator at xorshift.di.unimi.it

It's kinda hard to beat the built-in rnd() function (in terms of performance) using FreeBASIC code. Using -gen gcc -O 2 I can get my example code to do a bit better (or as-good-as) built-in rnd() but it's hardly measurable. Same goes for the code translated from xorshift.di.unimi.it (as-fast-as built-in rnd() when using -gen gcc -O 2).

Return to “Tips and Tricks”

Who is online

Users browsing this forum: dafhi and 8 guests