# # Galois linear feedback shift register (LFSR) (Python) # # Copyright (c) 2021 Project Nayuki # All rights reserved. Contact Nayuki for licensing. # https://www.nayuki.io/page/galois-linear-feedback-shift-register # import random # Random number generator class (implements most functionality of random.Random) class LfsrRandom(random.Random): def __new__(cls, *args, **kwargs): # Magic because the superclass doesn't cooperate return random.Random.__new__(cls, random.random()) def __init__(self, charis: int, state: int): assert isinstance(charis, int) assert isinstance(state, int) if charis < 0: raise ValueError("Invalid characteristic polynomial - negative") if charis.bit_length() < 2: raise ValueError("Invalid characteristic polynomial - degree too low") if state == 0: raise ValueError("Invalid state polynomial - all zero") if state.bit_length() >= charis.bit_length(): raise ValueError("Invalid state polynomial - degree >= char poly degree") self.characteristic = charis self.degree = charis.bit_length() - 1 self.state = state def randbit(self) -> int: result: int = self.state & 1 # Use bit 0 in the LFSR state as the result self.state = self.state << 1 # Multiply by x if (self.state >> self.degree) & 1 != 0: # If degree of state polynomial matches degree of characteristic polynomial self.state ^= self.characteristic # Then subtract the characteristic polynomial from the state polynomial return result def getrandbits(self, k: int) -> int: result: int = 0 for i in range(k): result = (result << 1) | self.randbit() return result def random(self) -> float: return self.getrandbits(52) / (1 << 52) # Demo main program if __name__ == "__main__": # Polynomial: x^16 + x^14 + x^13 + x^11 + x^0 rand = LfsrRandom(0b10110100000000001, 1) for i in range(10): print(rand.random()) for i in range(20): print(rand.randbit())