Change the behavior of irand() slightly

This change was made because it will mean less calls to the PRNG in
general. This was possible because each generated number could fill
*two* limbs, but the irand() implementation used one PRNG call to fill
one limb, not two.

This commit changes that.

Signed-off-by: Gavin D. Howard <gavin@gavinhoward.com>

3 files changed, 77 insertions, 14 deletions

diff --git a/include/num.h b/include/num.h
index 80788092..d24c206c 100644
--- a/include/num.h
+++ b/include/num.h
@@ -71,6 +71,10 @@ typedef BclBigDig BcBigDig;
 /// An alias for portability.
 #define BC_NUM_BIGDIG_C UINT64_C
 
+/// The max number + 1 that two limbs can hold. This is used for generating
+/// numbers because the PRNG can generate a number that will fill two limbs.
+#define BC_BASE_RAND_POW (BC_NUM_BIGDIG_C(1000000000000000000))
+
 /// The actual limb type.
 typedef int_least32_t BcDig;
 
@@ -88,6 +92,10 @@ typedef int_least32_t BcDig;
 /// An alias for portability.
 #define BC_NUM_BIGDIG_C UINT32_C
 
+/// The max number + 1 that two limbs can hold. This is used for generating
+/// numbers because the PRNG can generate a number that will fill two limbs.
+#define BC_BASE_RAND_POW (UINT64_C(100000000))
+
 /// The actual limb type.
 typedef int_least16_t BcDig;
 
diff --git a/src/num.c b/src/num.c
index 8f70c6a4..be0d575e 100644
--- a/src/num.c
+++ b/src/num.c
@@ -3815,7 +3815,7 @@ void
 bc_num_irand(BcNum* restrict a, BcNum* restrict b, BcRNG* restrict rng)
 {
 	BcNum atemp;
-	size_t i, len;
+	size_t i;
 
 	assert(a != b);
 
@@ -3835,24 +3835,76 @@ bc_num_irand(BcNum* restrict a, BcNum* restrict b, BcRNG* restrict rng)
 	assert(atemp.num != NULL);
 	assert(atemp.len);
 
-	len = atemp.len - 1;
+	if (atemp.len > 2)
+	{
+		size_t len;
+
+		len = atemp.len - 2;
 
-	// Just generate a random number for each limb.
-	for (i = 0; i < len; ++i)
+		// Just generate a random number for each limb.
+		for (i = 0; i < len; i += 2)
+		{
+			BcRand dig;
+
+			dig = bc_rand_bounded(rng, BC_BASE_RAND_POW);
+
+			b->num[i] = (BcDig) (dig % BC_BASE_POW);
+			b->num[i + 1] = (BcDig) (dig / BC_BASE_POW);
+		}
+	}
+	else
 	{
-		b->num[i] = (BcDig) bc_rand_bounded(rng, BC_BASE_POW);
+		// We need this set.
+		i = 0;
 	}
 
-	// Do the last digit explicitly because the bound must be right. But only
-	// do it if the limb does not equal 1. If it does, we have already hit the
-	// limit.
-	if (atemp.num[i] != 1)
+	// This will be true if there's one full limb after the two limb groups.
+	if (i == atemp.len - 2)
 	{
-		b->num[i] = (BcDig) bc_rand_bounded(rng, (BcRand) atemp.num[i]);
-		b->len = atemp.len;
+		// Increment this for easy use.
+		i += 1;
+
+		// If the last digit is not one, we need to set a bound for it
+		// explicitly. Since there's still an empty limb, we need to fill that.
+		if (atemp.num[i] != 1)
+		{
+			BcRand dig;
+			BcRand bound;
+
+			// Set the bound to the bound of the last limb times the amount
+			// needed to fill the second-to-last limb as well.
+			bound = ((BcRand) atemp.num[i]) * BC_BASE_POW;
+
+			dig = bc_rand_bounded(rng, bound);
+
+			// Fill the last two.
+			b->num[i - 1] = (BcDig) (dig % BC_BASE_POW);
+			b->num[i] = (BcDig) (dig / BC_BASE_POW);
+
+			// Ensure that the length will be correct. If the last limb is zero,
+			// then the length needs to be one less than the bound.
+			b->len = atemp.len - (b->num[i] == 0);
+		}
+		// Here the last limb *is* one, which means the last limb does *not*
+		// need to be filled. Also, the length needs to be one less because the
+		// last limb is 0.
+		else
+		{
+			b->num[i] = (BcDig) bc_rand_bounded(rng, BC_BASE_POW);
+			b->len = atemp.len - 1;
+		}
+	}
+	// Here, there is only one limb to fill.
+	else
+	{
+		// See above for how this works.
+		if (atemp.num[i] != 1)
+		{
+			b->num[i] = (BcDig) bc_rand_bounded(rng, (BcRand) atemp.num[i]);
+			b->len = atemp.len - (b->num[i] == 0);
+		}
+		else b->len = atemp.len - 1;
 	}
-	// We want 1 less len in the case where we skip the last limb.
-	else b->len = len;
 
 	bc_num_clean(b);
 
diff --git a/src/rand.c b/src/rand.c
index 11c22cd5..560e4942 100644
--- a/src/rand.c
+++ b/src/rand.c
@@ -517,8 +517,11 @@ bc_rand_int(BcRNG* r)
 BcRand
 bc_rand_bounded(BcRNG* r, BcRand bound)
 {
+	BcRand rand;
+	BcRand threshold;
+
 	// Calculate the threshold below which we have to try again.
-	BcRand rand, threshold = (0 - bound) % bound;
+	threshold = (0 - bound) % bound;
 
 	do
 	{