[hackers] [libzahl] zrand: add MODUNIFORM and add tests for QUASIUNIFORM and MODUNIFORM || Mattias Andrée

[git]

commit 8dc182ff87cafe3337490bc8db90a67449b9c837
Author:     Mattias Andrée <maand...@kth.se>
AuthorDate: Fri Mar 25 13:21:19 2016 +0100
Commit:     Mattias Andrée <maand...@kth.se>
CommitDate: Fri Mar 25 13:21:19 2016 +0100

    zrand: add MODUNIFORM and add tests for QUASIUNIFORM and MODUNIFORM
    
    Signed-off-by: Mattias Andrée <maand...@kth.se>

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 {