Uneven distribution of numbers when range is not evenly divisible by/into 16

[shitchell]

To save on network calls, qrng.js requests a block of hexadecimal numbers from ANU. Converting this base-16 number to an arbitrary range results in an uneven distribution of random numbers depending on that range. The steps are:

1. determine the range required (e.g.: getInteger(200, 250) will have a range of 50)
2. determine how many hexadecimal characters we need to cover that range (from the above example, 2 hexadecimal characters are required to cover a range of 50)
3. get that many hex characters from the qrng cache
4. convert those hex characters to a base-10 number
5. add that base-10 number to the minimum range (from the above example, 200)
6. if the resulting number is greater than the maximum range (from the above example, 250) then subtract to find the excess and add that to the minimum

So suppose we call getInteger(0, 10) to generate a random character between 0 and 9 inclusive. This will extract a single hexadecimal character with a possible value of 0 to 15 inclusive. If the random hexadecimal character has a value of 10-15, then we shift that up such that the value becomes 0-5. This means that for a random base-10 integer between 0 and 9 (generated from a random base-16 number from ANU), you have the following possible outcomes:

base-16 from ANU	generated base-10
0	0
1	1
2	2
3	3
4	4
5	5
6	6
7	7
8	8
9	9
A	0
B	1
C	2
D	3
E	4
F	5

Note that there is a 2/16 chance of selecting a 0-5 vs a 1/16 chance of selecting 6-9

This problem basically resembles this stackoverflow question. We're trying to fit a random number from the bin [1, 16] into an [a, b] bin where b - a might not equal 16. I'm not sure if there's some math or bit magic we can use to make this work, but I think we might simply have to resort to caching base-10 integers.

[shitchell]

Per a chat with ChatGPT, I've updated the _getRandom() function to include the following changes:

	_getRandom(rangeSize)
	{
		// If rangeSize is 1, we can just return 0
		if (rangeSize == 1) {
			return 0;
		}

		// Verify that we have enough in the cache to satisfy the range size
		var hexLength = this._rangeToHexLength(rangeSize);
		this._verifyCache(hexLength);

-		var num = this._cachePop(hexLength);
+		var num = this._cachePop(hexLength + 1);

		// Check to see if we got the last number in the cache
		if (this._cache.length == 0)
		{
			this.onCacheEmpty();
			this._isReady = false;
			this._fillCache();
		}

		return num;
	}

This seems to fix the distribution issue in some testing, but I'm not super mathy and can't validate for certain if this is a good fix off the top of my head. I need to do some actual work, but I'll come back to this over the next few days. If this doesn't work, I'm going to explore some possible approaches playing with bits, but I suspect that I'll end up just utilizing a different endpoint for either base-10 numbers or a random stream of bits if ANU offers that.

[shitchell]

Some testing indicates that the above fix does seem to have resolved the distribution issue. All ranges return evenly distributed values. I still want to reach out to the math stackexchange to confirm with people who math more than I can math that this is true, but I've got high high hopes

[shitchell]

So I reached out to math.stackexchange.com with the following notes:

• Adding hex numbers can reduce the bias to negligible amounts, but it doesn't remove it
• In order to 100% remove the bias, we'll essentially need to pull a random hexadecimal number, see if it fits a given range, and try again if it doesn't. Repeat until we get a hex number that fits.
• We can reduce the odds that a random hexadecimal doesn't fit the range by increasing the number of hexadecimal numbers pulled each time, although this comes with the caveat that we'll be unnecessarily using up extra data some percentage of the time. Will need to do some testing and maths to see what the optimum number of hexadecimal characters to pull is (minimum, minimum + 1, minimum + 2, etc...)