Very simple random generator (VERY simple).

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
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
    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)
   mov   eax,[a]
   rol   eax,b
   mov   [a],eax
End Asm

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.

   For y=0 To 255
      For x=0 To 255
' Core algorithm. d and z can be used as 32 bit seeds.
' This part visualizes the PRND numbers.
         a=d And q

' Distribution part.

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

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

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.
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?
Posts: 1401
Joined: Jul 29, 2006 3:00
Location: US

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

var ti = timer
var l = deadbeef_rand

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

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!
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
    j = 0
    for i = 0 to 255
       j = (j + S(i) + seed[i] mod Len(seed)) mod 256
      Swap S(i), S(j)
    i = 0
    j = 0
    'cycle the generator to harden weak seeds
    For k = 1 To 768
  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
For count = 1 To 100
   Print rc4rnd(""),
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_ )
        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)

Return to “Tips and Tricks”

Who is online

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