Random Numbers [using CRC logic]

Blitz3D Forums/Blitz3D Programming/Random Numbers [using CRC logic]

virtlands

(Posted 2013) [#1]

Hi, this is something that I discovered almost by accident.

CRC32 code is great for creating pseudo-random numbers.

The numbers have an excellent range, and with apparently very little repetitions.

This link talks more on the subject of randoms:
http://courses.physics.illinois.edu/phys466/lnotes/random_numbers.html

Eventually all number generators cycle and repeat those numbers.
In the case of using crc32 code the cycle is very long.

All numbers generated here are 32-bit, and can be neg and pos.
The CRC32 function was taken from McCredo's code.
http://www.blitzbasic.com/codearcs/codearcs.php?code=790

Here is the randomness:

;;  This project uses CRC32 methods to generate some 32-bits random numbers
;;  This code was arranged by VirtLands {Feb 25,2013}
;;
;;  The actual CRC32 code was created 9 years ago by author MrCredo
;;  <a href="http://www.blitzbasic.com/codearcs/codearcs.php?code=790" target="_blank">http://www.blitzbasic.com/codearcs/codearcs.php?code=790</a>
;;

 Graphics 800,600,32,2
 
 Dim crc_table(255)
 crc_init()

 Global CRCbank = CreateBank(4)    ;; 4 bytes = 1 INT = 32 bits,  is perfect for crc32 randoms

 Print 
 Print" A program that uses CRC32 logic to create random numbers "
 Print

 ;;--- Display a sampling of 24 random numbers ---
 For z=1 To 24    
          h$ = Hex$(crcRand())
          Print "  "+h$
 Next 

 WaitKey():End  

 ;; END of Program

Function crc_init()  ;; Code donated by "McCredo", thanks.
  Local i,j,value
  For i=0 To 255
    value=i
    For j=0 To 7
      If (value And $1) Then 
             value=(value Shr 1) Xor $EDB88320
      Else
             value=(value Shr 1)
      EndIf
    Next
    crc_table(i)=value
  Next
End Function

Function crc_string(txt$)
  Local byte,crc,i,size
     crc=$FFFFFFFF
     size=Len(txt$)
     For i=1 To size
          byte=Asc(Mid$(txt$,i,1))
          crc=(crc Shr 8) Xor crc_table(byte Xor (crc And $FF))
     Next
     Return ~crc
End Function

Function crc_bank(bank)
     Local byte, crc, i, size

     crc=$FFFFFFFF
     size=BankSize(bank)-1
     For i=0 To size
           byte=PeekByte(bank,i)
           crc=(crc Shr 8) Xor crc_table(byte Xor (crc And $FF))
     Next
     Return ~crc
End Function

Function crc_file(name$)
      Local byte,crc,file

      crc=$FFFFFFFF
      file=ReadFile(name$)
      If file=0 Then Return
      While Not Eof(file)
             byte=ReadByte(file)
             crc=(crc Shr 8) Xor crc_table(byte Xor (crc And $FF))
      Wend
      CloseFile file
      Return ~crc
End Function

;; These last 2 functions here were created by me [VirtLands -------]

Function CRCseedRand(v)  ;; reseeds the random number generator with value "V"
          PokeInt crcbank,0,v
          Return v 
End Function 

Function CRCRand()   ;; returns a 32-bit random integer, (can be positive or neg)
          Local crc
          crc = crc_bank(crcbank)
          PokeInt crcbank,0, crc  ;; poke the crc value back into the bank   
          Return crc
End Function

I created a nifty function that feeds the crc value back into the source, making a sort of recursive routine.

Function CRCRand() ;; returns a 32-bit random integer
Local crc
crc = crc_bank(crcbank)
PokeInt crcbank,0, crc ;; poke the crc value back in...
Return crc
End Function

That's it, it's simple.
I did a good test with this code and discovered that even after generating 2000000 random INTs, there were no repeats. Amazing, huh?

I'm guessing that the period length (periodicity) of this function
is 2^32-1, = 4294967295, which is huge.
(That means that it cycles through that many numbers before the cycle eventually repeats.)

If the 32-bit numbers are too large for your taste, then you can add creative ways of changing the range.

for example:

rnd1 = CRCrand() AND $FF ;; confine the values to 0-255

Trinosis

(Posted 2013) [#2]

Hi VirtLands.

Good job on your random number generator. :)

I've modified the code slightly so that CRCbank() returns a 31 bit number (ignoring the sign bit) which can be used to find a random number within a range specified.

Unless i'm mistaken, Blitz3d only supports 32 bit signed Int's and the unmodified random number generator only returns 32 bit numbers.

Modified CRCbank()

Function crc_bank(bank)
Local byte, crc, i, size

crc=$FFFFFFFF
size=BankSize(bank)-1
For i=0 To size
byte=PeekByte(bank,i)
crc=(crc Shr 8) Xor crc_table(byte Xor (crc And $FF))
Next
Return ~crc And 2147483647 ; Modified : And the lower 31 bits
End Function

and using this code to return a random number within a specified range.
The range can be both signed and unsigned.

range = (max - min)
number# =crcRand() ; return a 31 bit random number and store in a float
number# = number# / 2147483647 ; reduces the random number to the range of 0-1
number# = number# * range
number# = number# + min

Hope that helps. :)

Trinosis

virtlands

(Posted 2013) [#3]

Hi T. Thanks for the vast improvement.
I see you converted it into a signed version as well as FLOATS (0.0 to 1.0)
with optional range, and you allowed for a bank of any size.

I know random numbers can be used for some things, but I haven't figured out what yet.