I once had a need to generate seemingly random floating-point numbers in a C program running on the Texas Instruments MPS430 microcontroller. I had insufficient resources in the MSP430 to include the C math library, so I had to come up with a way to generate the numbers by moving bits around. 

 

I found an interesting algorithm to solve the problem using an Additive Congruential Generator, also called a Linear Feedback Shift Register.

 

Here is a C++ program showing how it works for an 8-bit integer.

  

The C++ program (see below) demonstrates an 8-bit Linear Feedback Shift Register, which produces non-sequential numbers across the full range of eight bits. Every bit pattern, except for all zeros, is generated.

 

Each new number is generated by a bit shifted into it as the exclusive or of four tap bits in the existing number. This generates, given enough iterations, all possible non-zero bit patterns, providing differing numbers with wide distances between successive numbers.

 

The generator cycles back to 1, with a cycle length of (2 raised to the nth power)-1, where n is the word size. The cycle length is 255 iterations for an 8-bit register.

 

This only works, however, when using the correct tap bits. Bits 0, 2, 3, and 4 are the tap bits for an 8 bit register.

 

For more information with C code for more word sizes (11, 16, 23, 32, 52, and 64 bits) visit:

 

https://github.com/Michael-Jablonski/Simple-Number-Generators.

To see how this works, copy and paste the following program into the online complier at www.onlinegdb.com, choose C++ 17 as the compiler and run the program listed below.

  

#include <iostream>

 

#define BIT_0 0x01

#define BIT_1 0x02

#define BIT_2 0x04

#define BIT_3 0x08

#define BIT_4 0x10

#define BIT_5 0x20

#define BIT_6 0x40

#define BIT_7 0x80

 

unsigned char shift_8_bit_feedback_register(void);

void print_new_line(int);

 

int main()

{
  unsigned char r8 = 0;

  std::cout << "8 bit linear shift register";

  print_new_line(2);

 

  while (r8 != 1)  // when 1 is reached, the cycle ends

  {

    r8 = shift_8_bit_feedback_register();

    printf("%u", r8);

    print_new_line(1);

  }

 

  print_new_line(1);

  std::cout << "done";

  print_new_line(2);

}

 

/*------------------------------------------------------------------*/

unsigned char shift_8_bit_feedback_register()

{

  // tap bits:  0, 2, 3, 4

 

  static unsigned char register_8 = 1;

 

  unsigned char new_bit;

 

  new_bit = (register_8 & BIT_0) ^ ((register_8 & BIT_2) >> 2) ^ ((register_8 & BIT_3) >> 3) ^ ((register_8 & BIT_4) >> 4);

 

  register_8 = register_8 >> 1;

  register_8 = register_8 | (new_bit << 7);

 

  return(register_8);

}

 

/*------------------------------------------------------------------*/

 

void print_new_line(int count)

{

  int i;

  for (i = 0; i <= count - 1; i++)

  {

    std::cout << std::endl;

  }

}