summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--lib/rnd.h2
-rw-r--r--lib/src/mt19937ar.c20
-rw-r--r--lib/test/rnd/src/test_rnd.c42
3 files changed, 62 insertions, 2 deletions
diff --git a/lib/rnd.h b/lib/rnd.h
index 007b4b44c3..11aa937d30 100644
--- a/lib/rnd.h
+++ b/lib/rnd.h
@@ -28,5 +28,7 @@ void
lib_rnd_init_by_array (lib_rnd_t *ctx, const u32 init_key[], int key_length);
u32
lib_rnd32 (lib_rnd_t *ctx);
+uint
+lib_rnd_uniform (lib_rnd_t *ctx, uint bound);
#endif /* rnd_h */
diff --git a/lib/src/mt19937ar.c b/lib/src/mt19937ar.c
index 7ecbfe1cef..cf7b2103da 100644
--- a/lib/src/mt19937ar.c
+++ b/lib/src/mt19937ar.c
@@ -191,3 +191,23 @@ lib_rnd32 (lib_rnd_t *ctx)
return y;
}
+/**
+ * Generates a random number on [0,bound-1]-interval.
+ * \param ctx the rnd context.
+ * \param bound upper bound.
+ * \return the random number.
+ */
+uint
+lib_rnd_uniform (lib_rnd_t *ctx, uint bound)
+{
+ uint up;
+ uint n;
+ /* This is not optimal if bound is a power of two, but it is harder to
+ * divide 2^32. */
+ up = 0xffffffff - (0xffffffff % bound);
+ do {
+ n = lib_rnd32 (ctx);
+ } while (n > up);
+ return n % bound;
+}
+
diff --git a/lib/test/rnd/src/test_rnd.c b/lib/test/rnd/src/test_rnd.c
index e5a12b5b42..98bc84323b 100644
--- a/lib/test/rnd/src/test_rnd.c
+++ b/lib/test/rnd/src/test_rnd.c
@@ -24,18 +24,56 @@ main (void)
{
uint i;
u32 r;
- static const u32 init[4] = { 0x123, 0x234, 0x345, 0x456 };
lib_rnd_t ctx;
+ static const u32 init[4] = { 0x123, 0x234, 0x345, 0x456 };
+ /* Initialise. */
lib_rnd_init_by_array (&ctx, init, COUNT (init));
+ /* Compare with original Mersenne Twister code. */
for (i = 0; i < COUNT (data); i++)
{
r = lib_rnd32 (&ctx);
if (r != data[i])
{
- fprintf (stderr, "FAIL at %u\n", i);
+ fprintf (stderr, "FAIL rnd32 i=%u\n", i);
+ return 1;
+ }
+ }
+ /* Check lib_rnd_uniform bound. */
+ bool ub, ut;
+ ub = ut = false;
+ for (i = 0; i < 100000; i++)
+ {
+ r = lib_rnd_uniform (&ctx, 1000);
+ if (r >= 1000)
+ {
+ fprintf (stderr, "FAIL bound overflow i=%u\n", i);
return 1;
}
+ if (r == 0) ub = true;
+ if (r == 999) ut = true;
+ }
+ if (!ub || !ut)
+ {
+ fprintf (stderr, "FAIL bound not hit\n");
+ return 1;
+ }
+ /* Check lib_rnd_uniform uniformity. */
+ int less, more;
+ less = more = 0;
+ for (i = 0; i < 100000; i++)
+ {
+ r = lib_rnd_uniform (&ctx, 0xc0000000);
+ if (r > 0xc0000000 / 2)
+ more++;
+ else
+ less++;
+ }
+ if (ABS (more - less) > 1000)
+ {
+ fprintf (stderr, "FAIL not uniform more=%d, less=%d\n", more, less);
+ return 1;
}
+ /* Great. */
fprintf (stderr, "PASS\n");
return 0;
}