zrand: add MODUNIFORM and add tests for QUASIUNIFORM and MODUNIFORM

Signed-off-by: Mattias Andrée <maandree@kth.se>

4 files changed, 57 insertions, 1 deletions

diff --git a/man/zrand.3 b/man/zrand.3
index c7858a1..97100bc 100644
--- a/man/zrand.3
+++ b/man/zrand.3
@@ -48,6 +48,25 @@ range [0,
 Generate a integer in the range [0,
 .IR max ]
 uniformally random.
+.TP
+.B MODUNIFORM
+Slightly faster alternative to
+.BR UNIFORM .
+
+It is not truly uniform. It is biased
+to the lower numbers, but the probably
+if any number is either
+.I p
+or
+.I 2p
+for some parameter-dependent number
+.IR p .
+
+It uses the naïve approach of generating
+a random number and modulation with the maximum
+number. However, this implementation this
+modulation by subtracting with the maximum number
+if the generated number is greater.
 .P
 It is safe to call
 .B zrand
diff --git a/src/zrand.c b/src/zrand.c
index 1bb1a90..17968af 100644
--- a/src/zrand.c
+++ b/src/zrand.c
@@ -94,6 +94,14 @@ zrand(z_t r, enum zranddev dev, enum zranddist dist, z_t n)
 		while (unlikely(zcmpmag(r, n) > 0));
 		break;
 
+	case MODUNIFORM:
+		if (unlikely(znegative(n)))
+			libzahl_failure(-ZERROR_NEGATIVE);
+		zrand_get_random_bits(r, zbits(n), fd);
+		if (unlikely(zcmpmag(r, n) > 0))
+		        zsub(r, r, n);
+		break;
+
 	default:
 		libzahl_failure(EINVAL);
 	}
diff --git a/test.c b/test.c
index 5517d9e..de92ccb 100644
--- a/test.c
+++ b/test.c
@@ -738,6 +738,34 @@ main(void)
 	assert(zcmp(a, c), != 0);
 	assert(zcmp(b, c), != 0);
 
+	zsetu(d, 100000UL);
+	zrand(a, FAST_RANDOM, QUASIUNIFORM, d);
+	assert(zcmp(a, _0), >= 0);
+	assert(zcmp(a, d), <= 0);
+	zrand(b, FAST_RANDOM, QUASIUNIFORM, d);
+	assert(zcmp(b, _0), >= 0);
+	assert(zcmp(b, d), <= 0);
+	zrand(c, FAST_RANDOM, QUASIUNIFORM, d);
+	assert(zcmp(c, _0), >= 0);
+	assert(zcmp(c, d), <= 0);
+	assert(zcmp(a, b), != 0);
+	assert(zcmp(a, c), != 0);
+	assert(zcmp(b, c), != 0);
+
+	zsetu(d, 100000UL);
+	zrand(a, FAST_RANDOM, MODUNIFORM, d);
+	assert(zcmp(a, _0), >= 0);
+	assert(zcmp(a, d), <= 0);
+	zrand(b, FAST_RANDOM, MODUNIFORM, d);
+	assert(zcmp(b, _0), >= 0);
+	assert(zcmp(b, d), <= 0);
+	zrand(c, FAST_RANDOM, MODUNIFORM, d);
+	assert(zcmp(c, _0), >= 0);
+	assert(zcmp(c, d), <= 0);
+	assert(zcmp(a, b), != 0);
+	assert(zcmp(a, c), != 0);
+	assert(zcmp(b, c), != 0);
+
 	assert((zseti(a, -5), zptest(0, a, 100)), == NONPRIME);
 	assert((zseti(a, -4), zptest(0, a, 100)), == NONPRIME);
 	assert((zseti(a, -3), zptest(0, a, 100)), == NONPRIME);
diff --git a/zahl.h b/zahl.h
index cd41b7b..1ac6237 100644
--- a/zahl.h
+++ b/zahl.h
@@ -53,7 +53,8 @@ enum zranddev {
 
 enum zranddist {
 	QUASIUNIFORM = 0,               /* Almost uniformly random, per the usual recommendation. */
-	UNIFORM                         /* Actually uniformly random. */
+	UNIFORM,                        /* Actually uniformly random. */
+	MODUNIFORM                      /* Almost uniformly random, using the naïve approach of modulation. */
 };
 
 enum zerror {