Linear Feedback Shift Register LFSR pseudorandom number gen

Share your advanced PureBasic knowledge/code with the community.
User avatar
Keya
Addict
Addict
Posts: 1891
Joined: Thu Jun 04, 2015 7:10 am

Linear Feedback Shift Register LFSR pseudorandom number gen

Post by Keya »

The Linear Feedback Shift Register (LFSR) is a Pseudo-Random Number Generator (PRNG) that has a very interesting property -- it uses every number within its range, but only once.
Wiki: https://en.wikipedia.org/wiki/Linear-fe ... t_register

For example, consider a PRNG that generates 5 random numbers ...
Most PRNG's might produce output like: 1,4,3,2,4 (note it has two 4's, and never used the number 5)
However, the LFSR would produce something like: 1,4,3,2,5 (no duplicate numbers, and every number used once, and once only)

However, it only has this property (what's considered a "maximal LFSR") if it has a valid maximal mask to start with.
It has a fixed period.
Interestingly, the number 0 is never output, because that would break it (it would then continually output 0).

Please note this is not a cryptographic random number generator (it is quite clearly deterministic!), but can be combined with a CRNG.

______________________________________________

Code: Select all

;LINEAR FEEDBACK SHIFT REGISTER (LFSR)
; '// Based on source: https://github.com/23ars/projects/blob/master/assembly/nasm/lfsr/lfsr.asm
; '// Sample bitmasks: http://www.maximintegrated.com/en/app-notes/index.mvp/id/4400
; '// Ultimate bitmasks: https://users.ece.cmu.edu/~koopman/lfsr/index.html
; // Supports x86 + x64
SOME MAXIMAL BITMASKS:
(I've only provided one maximal mask for each bit-depth/degrees, but there are many others)

Code: Select all

; '//           MASK         DEGREES    NUMBERS
; '#LFSR_MASK = $5           ;3 bit      7
; '#LFSR_MASK = $9           ;4 bit      15
; '#LFSR_MASK = $1D          ;5 bit      31
; '#LFSR_MASK = $36          ;6 bit      63
; '#LFSR_MASK = $69          ;7 bit      127
; '#LFSR_MASK = $A6          ;8 bit      255
; '#LFSR_MASK = $17C         ;9 bit      511
; '#LFSR_MASK = $32D         ;10 bit     1023
; '#LFSR_MASK = $4F2         ;11 bit     2047
; '#LFSR_MASK = $D34         ;12 bit     4095
; '#LFSR_MASK = $1349        ;13 bit     8191
; '#LFSR_MASK = $2532        ;14 bit     16383
; '#LFSR_MASK = $6699        ;15 bit     32767
; '#LFSR_MASK = $8016        ;16 bit     65535
; '#LFSR_MASK = $12933       ;17 bit     131071
; '#LFSR_MASK = $2C93E       ;18 bit     262143
; '#LFSR_MASK = $593CA       ;19 bit     524287
; '#LFSR_MASK = $AFF95       ;20 bit     1048575
; '#LFSR_MASK = $12B6BC      ;21 bit     2097151
; '#LFSR_MASK = $2E652E      ;22 bit     4194303
; '#LFSR_MASK = $5373D6      ;23 bit     8388607
; '#LFSR_MASK = $9CCDAE      ;24 bit     16777215   i7-4790K @4GHz:
; '#LFSR_MASK = $12BA74D     ;25 bit     33554431     0.27secs
; '#LFSR_MASK = $36CD5A7     ;26 bit     67108863     0.54secs
; '#LFSR_MASK = $4E5D793     ;27 bit     134217727    1.01secs
; '#LFSR_MASK = $F5CDE95     ;28 bit     268435455    2.15secs
; '#LFSR_MASK = $1A4E6FF2    ;29 bit     536870911    4.30secs       equiv to (pixels)...
; '#LFSR_MASK = $29D1E9EB    ;30 bit     1073741823   8.66secs       32767x32767
; '#LFSR_MASK = $7A5BC2E3    ;31 bit     2147483647   17.25secs      46340x46340
; '#LFSR_MASK = $B4BCD35C    ;32 bit     4294967295   34.45secs      65535x65535
;32-64bit:
; '#LFSR_MASK = $800000001C        ;40bit
; '#LFSR_MASK = $80000000005B      ;48bit
; '#LFSR_MASK = $800000000000000D  ;64bit

Code: Select all

DisableDebugger

#LFSR_MASK = $9  ;4 bit  (15 numbers to keep it simple for the demo)

Procedure.l LFSR(seed.l, mask.l)  ;note this declaration is only compatible for 32bit, but easy enough to modify for 64
 ! mov eax, [p.v_seed]
 ! mov ecx, eax
 ! and ecx, 1
 ! shr eax, 1
 ! cmp ecx, 1
 ! jne end_lfsr
 ! mov ecx, [p.v_mask]
 ! xor eax, ecx
 !end_lfsr:
 ;! and eax, $00FFFFFF     ;Use this instruction to only return the last 8 bits (al). Comment-out to return the full 32bit result.
 ;_BUT_ the caller can't then use that as the next seed, so really the caller should be the one extracting the 8bits, not this func
 ProcedureReturn
EndProcedure

seed.l = 1  ;you can set this to any valid value within the range of the bitmask, but not 0

For i = 1 To (15*2)  ;to demonstrate 2 runs of our 15-number demo
  seed = LFSR(seed, #LFSR_MASK)   ;the seed is updated with each call
  Debug Str(seed)
Next i
BarryG
Addict
Addict
Posts: 3296
Joined: Thu Apr 18, 2019 8:17 am

Re: Linear Feedback Shift Register LFSR pseudorandom number

Post by BarryG »

Keya wrote:Most PRNG's might produce output like: 1,4,3,2,4 (note it has two 4's, and never used the number 5)
However, the LFSR would produce something like: 1,4,3,2,5 (no duplicate numbers, and every number used once, and once only)
So LFSR is a shuffle (mixing a deck of cards), and not a randomiser (rolling a dice).
User avatar
Keya
Addict
Addict
Posts: 1891
Joined: Thu Jun 04, 2015 7:10 am

Re: Linear Feedback Shift Register LFSR pseudorandom number

Post by Keya »

BarryG wrote:
Keya wrote:Most PRNG's might produce output like: 1,4,3,2,4 (note it has two 4's, and never used the number 5)
However, the LFSR would produce something like: 1,4,3,2,5 (no duplicate numbers, and every number used once, and once only)
So LFSR is a shuffle (mixing a deck of cards), and not a randomiser (rolling a dice).
Yes I'd say that's a very good analogy! :) (but again, only when used with a maximal bitmask) You get to decide how big the deck of cards is by selecting the bitmask.
Post Reply