Pseudo random number using Xorshift algorithm
The Xorshift algorithm generates the sequence of random numbers using the exclusive OR gate(XOR). These generators are very efficient and fast and were discovered by George Marsaglia. Xorshift generators can generate an extensive sequence of random numbers; for a single number n, it can produce a sequence of 232 - 1 numbers, and if we increase the count to n and m, it can produce a sequence of 264 - 1 numbers.
Xorshift logic
The algorithm works on the logic of the XOR gate. It takes two numbers, applies the XOR gate to their binary form, and generates a new number. It also follows another pattern for single integers; it takes the binary form of an integer, shifts the bits to the left, and adds zeroes on the right end to keep it in 8-bit form. It applies the XOR operator to both numbers and generates a new random number.
Explanation
In the illustration above, we have a single integer 61 with decimal and binary types. The Xorshift algorithm removes the left-most two digits and adds two zeroes on the right to balance it, which gives us a new number, 244. It then applies the XOR operator to both numbers, giving us a unique random number, 201.
Variation of Xorshift
There are different variations of the Xorshift algorithm, and two of them are:
Xorshift*: This generates random numbers using non-linear multiplication.
Xorshift+: This generates random numbers using the linear addition method.
Example
In the code widget below, we have the Xorshift implementation in python.
def random():x = 123456789y = 362436069z = 521288629w = 88675123t = x ^ ((x << 11) & 0xFFFFFFFF) # 32bitx, y, z = y, z, ww = (w ^ (w >> 19)) ^ (t ^ (t >> 8))return wdef main():r = random()print(r)if __name__ == '__main__':main()
Explanation
Lines 4-5: We declared four variables to implement the Xorshift.
Lines 6-9: Show the implementation of Xorshift using the left and right shifts.
Free Resources