## 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]              *
*  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]              *
*  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]              *
*  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
```