random.c

calc大数库

#include <stdio.h>

#define USL unsigned long int
#define L0 2147483648

USL RANDOMm(USL x);
main()
{
	USL i, n, j;

	printf("enter n > 0\n");
	scanf("%lu", &n);
	j = 63434341;
	for (i = 0; i < n; i++)
	{
		j = RANDOMm(j);
		printf("%lu\n", j);
	}
	return;
}

unsigned long RUSSm(USL a, USL b, USL c, USL p)
/*
 *  input: unsigned long ints a, b, c, p, with p > 0.
 * output: a + b * c (mod p).
 * Russian Peasant multiplication algorithm. Uses the identities
 * RUSSm(a, b, 2 * c, p) = RUSSm(a, 2 * b, c, p),
 * RUSSm(a, b, c + 1, p) = RUSSm(a + b, b, c, p).
 * If a, b, c and p are less than 2^32, * so is RUSSm(a, b, c, p).
 * From H. Luneburg, "On the Rational Normal Form of * Endomorphisms",
 * B.I. WissenSchaftsverlag, Mannheim/Wien/Zurich, 1987, pp 18-19.
 * Luneburg's restriction to 2*p<2^32 removed by krm on 18/4/94.
 */
{
	a = a % p;
	b = b % p;
	c = c % p;
	while (c)
	{
		while (!(c & 1))
		{
			c = c >> 1;
	 		b = (b < p - b) ? (b << 1) % p : (b - (p - b)) % p;
		}
		c--;
		a = (a < p - b) ? a + b : a - (p - b);
	}
	return a;
}

unsigned long RANDOMm(USL x)
/*
 * input: unsigned int x, output:a "random number" a * x + c (mod m).
 * a = 1001, m = R0 = 65536, c = 65;
 * From H. Luneburg, "On the Rational Normal Form of Endomorphisms",
 * B.I. WissenSchaftsverlag, Mannheim/Wien/Zurich, 1987.
 * See Knuth Vol 2, Theorem A, p. 16.
 */
{
	unsigned long a, c, m;
		
	m = L0;
	a = 1001;
	c = 65;
	return RUSSm(c, a, x, m);
}