Swordfish Wiki | SwordfishUser / PseudoRandomNumberGenerator diff

PseudoRandomNumberGenerator

SwordfishUser.PseudoRandomNumberGenerator History

Hide minor edits - Show changes to markup

April 11, 2023, at 03:11 PM by swordfish -

Added lines 33-34:

UPDATE NOTE Apr 2023 - There's a simpler single file implementation of this code at PseudoRandomNumberGeneratorV2

Restore

July 22, 2011, at 02:20 AM by David Eather -

Changed lines 38-43 from:

InitializeRND(pValue)

With pValue set to a valid seed.

GetRND()

to:

InitializeRND(pValue) With pValue set to a valid seed.

Calling GetRND() returns the next pseudo random number

Restore

July 22, 2011, at 02:05 AM by swordfish -

Changed lines 3-4 from:

The modules below implement Pseudo Random Number Generators for 8-bit, 16-bit, and floating-point word sizes. The most common type of pseudo random number generator is a Linear Congruence Generator which is implemented here. Due to the small sized state of the LCGs I have combined their output with the output of another simple generator called a Galois Linear Feedback Shift Register. The period of the GLFSR is 2^N – 1 which, when combined with the LCG gives a total period of (2^N) x (2^N – 1). The output of this combination has much better statistical properties than even the largest LCG.

to:

The modules below implement Pseudo Random Number Generators for 8-bit, 16-bit, and floating-point word sizes. The most common type of pseudo random number generator is a Linear Congruence Generator which is implemented here. Due to the small sized state of the LCGs I have combined their output with the output of another simple generator called a Galois Linear Feedback Shift Register. The period of the GLFSR is 2^^N – 1 which, when combined with the LCG gives a total period of (2^^N) x (2^^N – 1). The output of this combination has much better statistical properties than even the largest LCG.

Restore

July 22, 2011, at 02:03 AM by swordfish -

Changed lines 32-33 from:

Usage

to:

Usage

Changed lines 44-51 from:

Usage example for floating point

Call the RandGen.Initialize(pInitialValue) one time with the initial value (value read from an analog floating PIC pin for example).

Call the RandGen.Rand() function to get a new random value.

to:

Usage example for Byte values

Call the RndByte.InitializeRND(pInitialValue) one time with the initial value if you require a different pseudo random number sequence.

Call the RndByte.GetRND() function to get a new random value.

Changed line 56 from:

Name : floating point PRNG test harness.BAS *

to:

Name : rnd.BAS *

Changed line 70 from:

Include "RNDfloat.bas" 'RNDWord.bas or RNDFloat.bas

to:

Include "RNDByte.bas"

Changed lines 73-77 from:

Dim Y As Float Dim X As LongInt Dim lowest, highest As LongInt

to:

Dim Y As Byte

Changed line 76 from:

 SetBaudrate(sbr19200)

to:

 SetBaudrate(sbr300)

Changed lines 81-88 from:

 'InitializeRND(4)

 main:
 Y=GetRND()* 1000000
 X = Y 
 PORTB  = (X)
 UART.Write (DecToStr(X),13,10)

GoTo main

to:

 InitializeRND(4)'if desired

main:

 Y=GetRND()
 PORTB  = (Y)
 UART.Write (DecToStr(Y)," ")
 GoTo main

Changed lines 94-95 from:

Just copy and paste into the Swordfish IDE and save in you UserLibrary folder as "RNDfloat.bas"...

to:

Just copy and paste into the Swordfish IDE and save in you UserLibrary folder as "RNDByte.bas"...

Changed line 99 from:

Name : RndFloat.BAS *

to:

Name : RndByte.BAS *

Changed lines 105-106 from:

Notes : call InitializeRND(pValue) with a value between 0-16777215 *
: call GetRND() to get a floating point PRNumber 0 to .999999 *

to:

Notes : call InitializeRND(pValue) with a value between 0-255 *
: call GetRND() to get a Byte 0 to 255 *

Changed lines 113-114 from:

 Dim LCG, GLFSR As LongInt 'only 24-bits are used
 Dim Temp As Float

to:

 Dim LCG,GLFSR As Byte

Changed line 115 from:

Public Function GetRND() As Float

to:

Public Function GetRND() As Byte

Changed line 117 from:

 LCG = (2047 * LCG + 4091) And $FFFFFF 'and performs the mod function here

to:

 LCG=(7*LCG+17)

Changed lines 121-122 from:

  GLFSR = GLFSR Xor 7679
  GLFSR = (GLFSR >> 1) Or $1000000

to:

  GLFSR = GLFSR Xor 135 '135 is the tap 
  GLFSR = (GLFSR >> 1) Or $80

Changed lines 126-129 from:

    Temp = (LCG Xor GLFSR) And $7FFFFF
    Temp = Temp  / $800000 
    result = Temp

to:

    result = GLFSR Xor LCG

Changed lines 129-132 from:

Public Sub InitializeRND(ByVal ReSeed As LongInt)

 LCG = reseed And $FFFFFF
 GLFSR = LCG Xor  $555555 'just making the start values very different - not realy important
 If GLFSR = 0 Then        'except that GLFSR must not be zero

to:

Public Sub InitializeRND(ByVal ReSeed As Byte)

 LCG = ReSeed
 GLFSR = LCG Xor $55 'just making the start values very different - not realy important
 If GLFSR = 0 Then   'except that GLFSR must not be zero

Changed line 138 from:

 LCG =5592404

to:

 LCG=84

Changed lines 142-350 from:

to:

Usage example for Word values

Call the RndWord.InitializeRND(pInitialValue) one time with the initial value if you require a different pseudo random number sequence.

Call the RndWord.GetRND() function to get a new random value.

The following program gives an example on how to use the pseudo-random number generator.

{
*****************************************************************************
*  Name    : rnd.BAS                                                        *
*  Author  : [select VIEW...EDITOR OPTIONS]                                 *
*  Notice  : Copyright (c) 2011 [select VIEW...EDITOR OPTIONS]              *
*          : All Rights Reserved                                            *
*  Date    : 15/07/2011                                                     *
*  Version : 1.0                                                            *
*  Notes   :                                                                *
*          :                                                                *
*****************************************************************************
}

Device = 18F1320
Clock=20

Include "RNDWord.bas"  
Include "SUART.bas"
Include "convert.bas"
Dim Y As Word  

 SetMode(umInverted)
 SetBaudrate(sbr300)
 SetTX(PORTA.0)

 TRISB=0

 InitializeRND(4)'if desired

main:
 Y=GetRND()
 PORTB  = (Y)
 UART.Write (DecToStr(Y)," ")
 GoTo main

RandGen Module

This is the module code for the above example. Just copy and paste into the Swordfish IDE and save in you UserLibrary folder as "RNDWord.bas"...

{
*****************************************************************************
*  Name    : RndWord.BAS                                                    *
*  Author  : David Eather                                                   *
*  Notice  : This code is placed into the Public Domain                     *
*          :                                                                *
*  Date    : 19/07/2011                                                     *
*  Version : 1.0                                                            *
*  Notes   : call InitializeRND(pValue) with a value between 0-65535        *
*          : call GetRND() to get a Byte 0 to 65535                         *
*****************************************************************************
}


Module Rand

 Dim LCG,GLFSR As Word

Public Function GetRND() As Word
 'LCG
 LCG=(127*LCG+259) 

 'Galios LFSR
 If (GLFSR And 1) = 1 Then
  GLFSR = GLFSR Xor 447 '447 is the tap value
  GLFSR = (GLFSR >> 1) Or $8000
 Else
  GLFSR = (GLFSR >> 1)
 End If
    result = GLFSR Xor LCG 
End Function

Public Sub InitializeRND(ByVal ReSeed As Word)
 LCG = ReSeed
 GLFSR = LCG Xor $5555 'just making the start values very different - not realy important
 If GLFSR = 0 Then     'except that GLFSR must not be zero 
  GLFSR=1 
 EndIf
End Sub

 GLFSR=1
 LCG=21844
 End

Usage example for floating point

Call the RndFloat.InitializeRND(pInitialValue) one time with the initial value if you require a different pseudo random number sequence.

Call the RndFloat.GetRND() function to get a new random value.

The following program gives an example on how to use the pseudo-random number generator.

{
*****************************************************************************
*  Name    : floating point PRNG test harness.BAS                           *
*  Author  : [select VIEW...EDITOR OPTIONS]                                 *
*  Notice  : Copyright (c) 2011 [select VIEW...EDITOR OPTIONS]              *
*          : All Rights Reserved                                            *
*  Date    : 15/07/2011                                                     *
*  Version : 1.0                                                            *
*  Notes   :                                                                *
*          :                                                                *
*****************************************************************************
}

Device = 18F1320
Clock=20

Include "RNDfloat.bas"  'RNDWord.bas or RNDFloat.bas
Include "SUART.bas"
Include "convert.bas"

Dim Y As Float
Dim X As LongInt
Dim lowest, highest As LongInt

 SetMode(umInverted)
 SetBaudrate(sbr19200)
 SetTX(PORTA.0)

 TRISB=0

 InitializeRND(4)

 main:
 Y=GetRND()* 1000000
 X = Y 
 PORTB  = (X)
 UART.Write (DecToStr(X),13,10)
GoTo main

RandGen Module

This is the module code for the above example. Just copy and paste into the Swordfish IDE and save in you UserLibrary folder as "RNDfloat.bas"...

{
*****************************************************************************
*  Name    : RndFloat.BAS                                                   *
*  Author  : David Eather                                                   *
*  Notice  : This code is placed into the Public Domain                     *
*          :                                                                *
*  Date    : 19/07/2011                                                     *
*  Version : 1.0                                                            *
*  Notes   : call InitializeRND(pValue) with a value between 0-16777215     *
*          : call GetRND() to get a floating point PRNumber 0 to .999999    *
*****************************************************************************
}


Module Rand

 Dim LCG, GLFSR As LongInt 'only 24-bits are used
 Dim Temp As Float

Public Function GetRND() As Float
 'LCG
 LCG = (2047 * LCG + 4091) And $FFFFFF 'and performs the mod function here

 'Galios LFSR
 If (GLFSR And 1) = 1 Then
  GLFSR = GLFSR Xor 7679
  GLFSR = (GLFSR >> 1) Or $1000000
 Else
  GLFSR = (GLFSR >> 1)
 End If
    Temp = (LCG Xor GLFSR) And $7FFFFF
    Temp = Temp  / $800000 
    result = Temp

End Function

Public Sub InitializeRND(ByVal ReSeed As LongInt)
 LCG = reseed And $FFFFFF
 GLFSR = LCG Xor  $555555 'just making the start values very different - not realy important
 If GLFSR = 0 Then        'except that GLFSR must not be zero
  GLFSR=1 
 EndIf
End Sub

 GLFSR=1
 LCG =5592404
 End

Restore

July 22, 2011, at 01:30 AM by swordfish -

Changed lines 1-13 from:

This module implements a simple modulo-based PSEUDO Random Number Generator for Swordfish Basic. It's difficult to generate true random numbers from a deterministic machine like PIC. Hopefully, some mathematical methods let us have a series of numbers that seems really random, althought they have all a fixed cycle uppon which they restart to give the same serie of values. this is why they are all called Pseudo random number generators. The cycling behaviour has the advantage to give you the possibility to repeat the same experience despite the fact that it's based on (pseudo) random numbers.

The pseudo random number generator described here is based on a modulo function technique. It's very quick and gives nice random series.

As stated before, each generator has a cycle (period). For the pseudo random number generators to function correctly, they need an initial value (a value where to start in it's cycle). All calculated values are based on last generated value. Thus the initial value let you specify the (pseudo) initial calculated value.

For true random number generation, the best solution is to use physical (natural) events. To get this behaviour on a PIC device, the best solution I have found is to read a floating analog pin of a pic a certain number of times and to take the mean value (the ADC module of Swordfish do that for you automatically). I use this initial value to reinitialize the pseudo random number generator. This gives a nice serie of values on output.

When I'll have time, I'll add other generation algorithms (some are better but slower, and most of the best generators use Float calculations instead of integers). I'll also add a set of OPTIONs to the module to let users select the desired algorithm.

Usage example

to:

This module implements a simple Pseudo Random Number Generator for Swordfish Basic. Seeding the generator is done either by the programmer for a repeatable sequence of numbers or by the user where different seeds will produce different number sequences. The user seed might be directly from an interface (keyboard, USB, RS232 etc) or come from the value of a system clock or real time clock when any unpredictable interrupt event occurs e.g. a key press or powering up. Other useful possibilities are inputs from the real world sensors connected to the PIC.

Technical Aspects of the Generators

Linear Congruence Generators

Linear Congruence Generators have the form:

Staten = (A x Staten-1 + B) mod C

In Swordfish Basic: S = (A * S + B) MOD C

I have implemented only generators that produce maximum length periods. Not only is the period maximum but there are no “bad” seeds. To achieve this, the following conditions must be met.

A mod 8 must equal 5 or 1
A, B and C must not share any common factors other than 1

The modulus function is very computationally expensive but when the modulo function corresponds to a word or byte boundary you can totally ignore it! The extra bits are simply lost as overflow by the processor and it just returns the lower order bits as required.

Galois Linear Feedback Shift Registers

Linear Feedback Shift Registers are marvelous for producing long runs of ones and zeros in complex patterns that show excellent statistical properties while consuming low resources in terms of RAM and ROM.

LFSRs are handicapped in software because they only output one bit at a time. This is too slow. The mathematics of Evariste Galois (1811-1832) allows us to construct an equivalent type of circuit that operates in parallel. It produces 8 bits per iteration and this is what we have used.

A description of the operation of a GLFSR is found at http://en.wikipedia.org/wiki/Linear_feedback_shift_register. Please note that setting a random tap sequence is unlikely to produce an acceptable period. The taps I have chosen combine maximum period with good linear complexity.

You can change the initialization procedure if you like, the only requirement is that the GLFSR will not run if it is set to zero.

Usage

Include the correct PRNG. There are three to choose from; "RNDfloat.bas", ‘RNDWord.bas or RNDFloat.bas. They return floating point, word or byte results respectively.

You can change the starting sequence by initializing the generator by calling

InitializeRND(pValue)

With pValue set to a valid seed.

GetRND()

Usage example for floating point

Changed lines 58-61 from:

Name : RandGenTest.BAS *
Author : Ahmed Lazreg (Octal) *
[email protected] *
Notice : Copyright (c) 2007 *

to:

Name : floating point PRNG test harness.BAS *
Author : [select VIEW...EDITOR OPTIONS] *
Notice : Copyright (c) 2011 [select VIEW...EDITOR OPTIONS] *

Changed line 62 from:

Date : 06/10/2007 *

to:

Date : 15/07/2011 *

Changed lines 64-66 from:

Notes : A little test program for the Pseudo Random Number *
Generator module RandGen.bas *
*

to:

Notes : *
: *

Changed lines 68-72 from:

'device =18F452 Device = 18F4620 Clock = 20

Include "usart.bas"

to:

Device = 18F1320 Clock=20

Include "RNDfloat.bas" 'RNDWord.bas or RNDFloat.bas Include "SUART.bas"

Changed lines 75-93 from:

Include "RandGen.bas"

Dim RandomNumber As Byte

SetBaudrate(br9600)

RandGen.Initialize(2) // initialize the generator Initial Seed Value to 2

                       // for Full Random value you can use an ADC read on 
                       // a floating AN PIC Pin

TRISB = 0 'All output

While true

   RandomNumber = RandGen.Rand() // generates a number 
   Write(DecToStr(RandomNumber),13,10)       // write to RS233
   LATB = RandomNumber // visualise number on PORTB leds (on my EasyPic Board)
   DelayMS(600)

Wend

to:

Dim Y As Float Dim X As LongInt Dim lowest, highest As LongInt

 SetMode(umInverted)
 SetBaudrate(sbr19200)
 SetTX(PORTA.0)

 TRISB=0

 'InitializeRND(4)

 main:
 Y=GetRND()* 1000000
 X = Y 
 PORTB  = (X)
 UART.Write (DecToStr(X),13,10)

GoTo main

Changed lines 96-97 from:

Giving us an output which looks like:

to:

Changed lines 98-100 from:

This is the module code for the above example. I provide two implementations, one using Byte variables and one using LongWord variables (the best one). Just copy and paste into the Swordfish IDE and save in you UserLibrary folder as RandGen.bas...

to:

This is the module code for the above example. Just copy and paste into the Swordfish IDE and save in you UserLibrary folder as "RNDfloat.bas"...

Changed lines 105-110 from:

Name : RandGen.BAS *
Author : Ahmed Lazreg (Octal) *
[email protected] http://www.pocketmt.com *
Date : 06/10/2007 *

to:

Name : RndFloat.BAS *
Author : David Eather *
Notice : This code is placed into the Public Domain *
: *
Date : 19/07/2011 *

Changed lines 111-127 from:

*
Notes : A Rudimentary Pseudo Random Number Generator (Modulo based) *
*
Usage : Call Initialize() to initialize the Initial value of the *
generator. The generator gives better values when the initial *
seed value is a Prime Number. *
For the same Initial Seed, you will get the same serie of *
generated values. This let you repeat some experiences (and *
this is why it's called a PSEUDO-random number generator. *
If you need an automatic different initial value each time you *
start the number generator, you can set the initial value to *
the read of an ADC value on a FLOATING Analog PIN of a PIC. *
Call Rand() to get/generate a new random value *
*
You can try to change the Magic Values to change the *
Pseudo-Random Number Generator Behaviour *
*

to:

Notes : call InitializeRND(pValue) with a value between 0-16777215 *
: call GetRND() to get a floating point PRNumber 0 to .999999 *

Changed lines 116-132 from:

Module RandGen

Const MagicA = 7,

      MagicB = 7,
      MagicC = 255

Private Dim Seed As Byte

{

Name : Rand() *
Purpose : Return a new Pseudo Random Number each time called *

} Public Function Rand() As Byte

    Seed = (MagicA * Seed + MagicB) Mod MagicC
    result = Seed

to:

Module Rand

 Dim LCG, GLFSR As LongInt 'only 24-bits are used
 Dim Temp As Float

Public Function GetRND() As Float

 'LCG
 LCG = (2047 * LCG + 4091) And $FFFFFF 'and performs the mod function here

 'Galios LFSR
 If (GLFSR And 1) = 1 Then
  GLFSR = GLFSR Xor 7679
  GLFSR = (GLFSR >> 1) Or $1000000
 Else
  GLFSR = (GLFSR >> 1)
 End If
    Temp = (LCG Xor GLFSR) And $7FFFFF
    Temp = Temp  / $800000 
    result = Temp

Changed lines 139-149 from:

{

Name : Rand() *
Purpose : Initialize the Random number generator *
The initial value could be a Value read from a Floating Analog *
PIC Pin.

} Public Sub Initialize(ByVal InitialSeed As Byte)

    Seed = InitialSeed
    Seed = Rand()

to:

Public Sub InitializeRND(ByVal ReSeed As LongInt)

 LCG = reseed And $FFFFFF
 GLFSR = LCG Xor  $555555 'just making the start values very different - not realy important
 If GLFSR = 0 Then        'except that GLFSR must not be zero
  GLFSR=1 
 EndIf

Added lines 147-149:

 GLFSR=1
 LCG =5592404
 End

Changed lines 152-234 from:

RandGen Module... a better implementation (using LongWord vars)

This is my favourite implementation. This implementation use LongWord variables ported from an old BSD Linux Kernel random number generator for X86 platforms(this explains the LongWord usage and big Magic constants). I did not found the old link from where I ported it first time (to Fortran) when I needed it at university, but this link describes the backgrounds (based on Free BSD also) http://www.panix.com/~elflord/cpp/random/ and a very nice description can be found here http://computer.howstuffworks.com/question697.htm (the version implemented below) .

This implementation introduces RndMax propertie that you could set in the Initialize subroutine. This values sets the interval in which generated values are constrained (normalized). By default, RandMax is set to 255 (max value for a byte).

This implementation is better than the implementation using Byte variables. It uses two magic constants that makes generated values really fine (seems truly random).

If you really need a nice generator for PIC, use this one (and keep RandMax limited to 255 so that you can assign the result of Rand() function directly to any byte variable (the previous sample program can be reused as is).

{
*****************************************************************************
*  Name    : RandGen.BAS                                                    *
*  Author  : Ahmed Lazreg (Octal)                                           *
*            [email protected]   http://www.pocketmt.com                   *
*  Notice  : Copyright (c) 2007                                             *
*          : All Rights Reserved                                            *
*  Date    : 06/10/2007                                                     *
*  Version : 1.0                                                            *
*                                                                           *
*  Notes   : A Rudimentary Pseudo Random Number Generator (Modulo based)    *
*                                                                           *
*  Usage   : Call Initialize() to initialize the Initial value of the       *
*            generator. The generator gives better values when the initial  *
*            seed value is a Prime Number.                                  *
*            For the same Initial Seed, you will get the same serie of      *
*            generated values. This let you repeat some experiences (and    *
*            this is why it's called a PSEUDO-random number generator.      *
*            If you need an automatic different initial value each time you *
*            start the number generator, you can set the initial value to   *
*            the read of an ADC value on a FLOATING Analog PIN of a PIC.    *
*            Call Rand() to get/generate a new random value                 *
*                                                                           *
*            You can try to change the Magic Values to change the           *
*            Pseudo-Random Number Generator Behaviour                       *
*                                                                           *
*****************************************************************************
}

Module RandGen

Const MagicA = 1103515245,
      MagicB = 12345

Private Dim RndMax As LongWord // Maximum number generated by the generator

Private Dim Seed As LongWord
{
****************************************************************************
* Name    : Rand()                                                         *
* Purpose : Return a new Pseudo Random Number each time called             *
****************************************************************************
}
Public Function rand() As LongWord
   Seed = Seed * MagicA + MagicB
   result = LongWord(Seed >> 16) Mod RndMax
End Function

{
****************************************************************************
* Name    : Rand()                                                         *
* Purpose : Initialize the Random number generator                         *
*           The initial value could be a Value read from a Floating Analog *
*           PIC Pin.
****************************************************************************
}
Public Sub Initialize(ByVal InitialSeed As LongWord, ByVal pRndMax As LongWord = 255)
    RndMax = pRndMax
    Seed = InitialSeed
End Sub

{
****************************************************************************
* Name    : SetRndMax()                                                    *
* Purpose : Sets the Max Value that the Random number gen can generate     *
****************************************************************************
}
public Sub SetRndMax(ByVal pRndMax as LongWord)
    RndMax = pRndMax
End Sub

to:

Restore