/*  Written in 2021 by Sebastiano Vigna (vigna@acm.org)

To the extent possible under law, the author has dedicated all copyright
and related and neighboring rights to this software to the public domain
worldwide. This software is distributed without any warranty.

See <http://creativecommons.org/publicdomain/zero/1.0/>. */

#include <stdint.h>

/* This is a Goresky-Klapper generalized multiply-with-carry generator
   (see their paper "Efficient Multiply-with-Carry Random Number
   Generators with Maximal Period", ACM Trans. Model. Comput. Simul.,
   13(4), p. 310-321, 2003) with period approximately 2^255. While in
   general slower than a scrambled linear generator, as it uses 128-bit
   operations, it it is an excellent generator based on congruential
   arithmetic.

   As all MWC generators, it simulates a multiplicative LCG with prime
   modulus m = 115414502257413896964950864333521986835826833770103090537364309614338189065303
   (0xff2a4b18846bbee2000000000000000000000000000000000096e36616f07c57)
   and multiplier given by the inverse of 2^64 modulo m. Note that the
   major difference with (C)MWC generators is that the modulus has a more
   general form. This additional freedom in the choice of the modulus
   fixes some of the problems of (C)MWC generators, at the price of one
   128-bit multiplication, one 64-bit multiplication, and one 128-bit sum. */


uint64_t x, y, z, c = 1; /* The state can be seeded with any set of values, not all zeroes. */

uint64_t inline next() {
	const __uint128_t t = 0xff2a4b18846bbee2 * (__uint128_t)x + c;
	x = y;
	y = z;
	z = 0x94d34db4cd59d099 * (uint64_t)t;
	c = (t + 0x96e36616f07c57 * (__uint128_t)z) >> 64;
	return z;
}