💾 Archived View for sdf.org › blippy › rng.gmi captured on 2024-03-21 at 15:48:19. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2023-01-29)
-=-=-=-=-=-=-
Created 2022-11-08
Uses a 16-bit Fibonacci linear feedback shift register (LFSR):
XOR bits 1 and 9, store in bit 16, shift register right
XOR:
A B XOR 0 0 0 0 1 1 1 0 1 1 1 0
#include <stdint.h>
unsigned lfsr_fib(void)
{
uint16_t start_state = 0xACE1u; /* Any nonzero start state will work. */
uint16_t lfsr = start_state;
uint16_t bit; /* Must be 16-bit to allow bit<<15 later in the code */
unsigned period = 0;
do
{ /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) & 1u;
lfsr = (lfsr >> 1) | (bit << 15);
++period;
}
while (lfsr != start_state);
return period;
}
This has a period of 65535, which is maximal. It looks like a good algorithm