Very simple random generator (VERY simple).

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
Thorham
Posts: 73
Joined: Apr 16, 2008 21:25

Very simple random generator (VERY simple).

Postby Thorham » Jul 14, 2010 19:54

Hi coders,

While experimenting with various simple pseudo random number generation methods, I came up with this algorithm (through experimentation).

Here's the pseudo code:

Code: Select all

    rotate left a,7
    a=a+b
    b=b+hex 11111111

And this is the test program:

Code: Select all

'
' Chaos Maker, an extremely simple PRNG.
' Escape quits the program, any other key generates a new set of PRNG numbers.
'
#Macro rol32(a,b)
asm
   mov   eax,[a]
   rol   eax,b
   mov   [a],eax
End Asm
#EndMacro

ScreenRes 400,300,32,,0

Dim As UInteger a,b,d,q,x,y,z,p
Dim As UInteger dist(255)

Dim As Double avrg,div

Dim As UByte Ptr scr=ScreenPtr

q=31   ' AND value for visualizing on screen. Needs to be 2^x-1, where x<9.
Do
   ScreenLock
   p=(400*4*28)+128*4

   For y=0 To 255
      For x=0 To 255
'
' Core algorithm. d and z can be used as 32 bit seeds.
'
         rol32(d,7)
         d=d+z
         z=z+&h11111111
'
' This part visualizes the PRND numbers.
'
         a=d And q
         b=a*(255\q)

         scr[p+0]=b
         scr[p+1]=b
         scr[p+2]=b
         p=p+4
'
' Distribution part.
'
         dist(a)=dist(a)+1
         avrg=avrg+a
      Next
      p=p+(400*4)-(256*4)
   Next

   div=div+65536
'
' Show distribution.
'
   Locate 1,1
   Print "Average:";avrg/div/q   ' 0.5 is ideal.
   Print
   Print "Distribution:"
   Print
   For x=0 To (q And 31) ' Cut off some results if there are too many numbers.
      Print dist(x)
      dist(x)=0
   Next

   ScreenUnLock
   If Input(1)=Chr(27) Then Stop
Loop

Perhaps this is useful to someone.

About the speed:

I needed a very fast one on my Amiga, and this one uses only eight cycles on a 50mhz 68030 (three assembler instructions), so that's quite fast. Such an old CPU (late eighties) can produce megabytes of PRNG data in a second, so on a PC it should be quite ridiculous.

Edit: Corrected two small flaws. 1) Pseudo code had no value for 'rotate left'. 2) Rotate value in the test program was 4, should be 7.
Last edited by Thorham on Jul 16, 2010 2:08, edited 2 times in total.
j_milton
Posts: 458
Joined: Feb 11, 2010 17:35

Postby j_milton » Jul 14, 2010 22:58

so is the idea that "a" is supposed to be random?
sir_mud
Posts: 1401
Joined: Jul 29, 2006 3:00
Location: US
Contact:

Postby sir_mud » Jul 15, 2010 7:03

Just wanted to post my translation of the "famous" 0xDEADBEEF prng I tranaslated from C awhile back.

Code: Select all



function deadbeef_rand( byval seed as uinteger = 0 ) as UInteger

        static deadbeef_seed as uinteger = 0
        static deadbeef_beef as uinteger = &hdeadbeef
       
        if seed <> 0 then deadbeef_seed = seed
       
        deadbeef_seed = (deadbeef_seed shl 7) xor ((deadbeef_seed shr 25) + deadbeef_beef)
        deadbeef_beef = (deadbeef_beef shl 7) xor ((deadbeef_beef shr 25) + &hdeadbeef)
       
        return deadbeef_seed
       
end function

var z = deadbeef_rand(timer)
print bin(z) & " => " & z

for n as integer = 1 to 4
        var x = deadbeef_rand
        print bin(x) & " => " & x
       
next

var ti = timer
var l = deadbeef_rand

while l > 100
        l = deadbeef_rand
wend
var too = timer
print bin(l) & " => " & l
print "Time to <100: " & too-ti
sleep



I don't remember the url I found this at, but creator of this code ran numerous random number tests and it actually is quite random compared to other generators. Enjoy!
j_milton
Posts: 458
Joined: Feb 11, 2010 17:35

Postby j_milton » Jul 15, 2010 15:03

At the other extreme, if you need high quality random bytes, good enough for cryptography etc. you can use something like this. (I wrote the code, but obviously not my algorithm)

Code: Select all

Function rc4rnd(seed As String) As UByte
  'max seed length = 256 chars
  Static As Integer i, j, s(0 To 255)
  Dim As Integer k
  If seed <> "" Then
    'initialize the s box
    for i = 0 to 255
      s(i) = i
    Next
    j = 0
    for i = 0 to 255
       j = (j + S(i) + seed[i] mod Len(seed)) mod 256
      Swap S(i), S(j)
    Next
    i = 0
    j = 0
    'cycle the generator to harden weak seeds
    'ref: http://www.users.zetnet.co.uk/hopwood/crypto/scan/cs.html#RC4-drop
    For k = 1 To 768
      rc4rnd("")
    Next
  EndIf
  i = (i + 1) mod 256
  j = (j + S(i)) mod 256
  Swap S(i), S(j)
  Function = S((S(i) + S(j)) mod 256)
End Function'rc4rnd


Dim As Integer count

'initialize the generator
'if you don't function always returns 0
rc4rnd(Str(Timer))
For count = 1 To 100
   Print rc4rnd(""),
Next
sleep
dafhi
Posts: 1329
Joined: Jun 04, 2005 9:51

Postby dafhi » Sep 24, 2010 4:18

Thor, I applied your technique in one of my graphics projects with spectacular results

Benchmark update: This appears to be at least 2% faster than Rnd!!!

Code: Select all

Dim Shared As UInteger t_rng_z, t_rng_d
#Macro tRNG( g_, multiplier_ )
    Asm
        mov ecx, [t_rng_z]
        mov eax, [t_rng_d]
        rol eax,7
        Add eax,ecx
        mov [t_rng_d],eax
        Add ecx, &H11111111
        mov [t_rng_z], ecx
    End Asm
    g_ = multiplier_* ((t_rng_d And &h7FFFFFFF) / &h7FFFFFFF)
#EndMacro

Return to “Tips and Tricks”

Who is online

Users browsing this forum: Baidu [Spider] and 2 guests