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.
- 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
UPDATE NOTE Apr 2023 - There's a simpler single file implementation of this code at PseudoRandomNumberGeneratorV2
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