Random Numbers with LFSR (Linear Feedback Shift Register)

I recently watched this video from Computerphile on YouTube (one of my favorite channels). It demonstrates a simple bit-shift operation can generate amazing random strings of numbers. It’s only about 13 minutes and worth the quick watch:

Dr. Pound uses Python for his example, so I thought I’d quickly convert it to Xojo.

Here’s the original Python code:

state = (1 << 127) | 1
while True:
    print(state & 1, end = '')
    newbie = (state ^ (state >> 1) ^ (state >> 2) ^ (state >> 7)) & 1
    state = (state >> 1) | (newbie << 127)

One thing about Python is that its integers are arbitrary precision unlike most other programming languages like Xojo, Java or C#. So we have to tweak the Python code to work with 64-bit integers, which are more commonly available and the maximum supported in Xojo.

If you’ve not used Python before, you might find all the symbols to be a bit cryptic. The Xojo code below ought to help you understand them better.

_{Updated to use correct tap bits for 64-bit numbers (Oct 5, 2021)}

Var state As UInt64 = Bitwise.ShiftLeft(1, 63) Or 1
Var state As UInt64 = Bitwise.ShiftLeft(1, 63) Or 1

While True
  TextArea1.AddText(Bitwise.BitAnd(state, 1).ToBinary(1))
  TextArea1.VerticalScrollPosition = TextArea1.LineNumber(TextArea1.Text.Length) // Scroll to end
  App.DoEvents // Don't do this in a real app!!
  Var newbit As UInt64
  
  newbit = (state Xor _
  Bitwise.ShiftRight(state, 1) Xor _
  Bitwise.ShiftRight(state, 3) Xor _
  Bitwise.ShiftRight(state, 4)) And 1
  
  state = Bitwise.ShiftRight(state, 1) Or Bitwise.ShiftLeft(newbit, 63)
Wend

I also changed this to work in a Desktop app rather than being a Console app so you can ignore the TextArea1.VerticalScrollPosition and the DoEvents (which you should not use in a real app) as they are just there so you can see the value change in realtime.