PseudoRandomNumberGenerator

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.

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.

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.

  1. A mod 8 must equal 5 or 1
  2. 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.

Calling GetRND() returns the next pseudo random number

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.

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 "RNDByte.bas"  
Include "SUART.bas"
Include "convert.bas"
Dim Y As Byte  

 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 "RNDByte.bas"...

{
*****************************************************************************
*  Name    : RndByte.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-255          *
*          : call GetRND() to get a Byte 0 to 255                           *
*****************************************************************************
}


Module Rand

 Dim LCG,GLFSR As Byte

Public Function GetRND() As Byte
 'LCG
 LCG=(7*LCG+17) 

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

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
  GLFSR=1 
 EndIf
End Sub

 GLFSR=1
 LCG=84
 End

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