libzahl

commit 8dc182ff87cafe3337490bc8db90a67449b9c837
parent ff185ae276b4f27b1650b03afdd56d2ecdfddd18
Author: Mattias Andrée <maandree@kth.se>
Date:   Fri, 25 Mar 2016 13:21:19 +0100

zrand: add MODUNIFORM and add tests for QUASIUNIFORM and MODUNIFORM

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

Diffstat:
M
man/zrand.3
 | 
19
+++++++++++++++++++
M
src/zrand.c
 | 
8
++++++++
M
test.c
 | 
28
++++++++++++++++++++++++++++
M
zahl.h
 | 
3
++-

4 files changed, 57 insertions(+), 1 deletion(-)
diff --git 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
@@ -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
@@ -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
@@ -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 {