tl;dr How do you construct arbitrarily long random BigInt numbers which are between a min and max (and which can be way larger than 2 ** 64 which JavaScript will support in a fairly straightforward way)? The range could be really small (0+) to very large (googol+).
I recently stumbled upon some interesting facts about JavaScript numbers when trying to generate a random BigInt:
How to generate random BigInt within a range in plain JavaScript (not Node.js)?
That works generally speaking for numbers up to 2 ** 64. But how can we have a generic algorithm to randomly generate a BigInt of any size, way larger than 2 ** 64? What follows is my current attempt.
(Thinking out loud) It would be something like, perhaps, first check the bounds of each the min and max to determine the scale of the number we are approaching. For practical purposes, let's say the number won't be larger than 65536 (2^16) digits. Then once we have this scale, that tells us how many random numbers to generate somehow. I am having a hard time visualizing how that might work. But anyways, then we generate the potentially several random numbers, using the BigInt formula linked above, and concatenate the result as the answer comment suggested, into a big string and pass that to the BigInt(string) function/constructor.
This starts to get tricky, you can't just pass in BigInts as the ranges, because Math.random() must be multiplied by regular numbers, not BigInts. So it's confusing.
Some examples to solve for:
// small
randomBigIntBetween(0n, 10n)
// normal but bigger than 65536
randomBigIntBetween(0n, 100000n)
// pretty big but still within JS 2 ** 64
randomBigIntBetween(0n, 100000100000100000100000n)
// big, outside of 2 ** 64
randomBigIntBetween(0n, 100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000n)
// huge, way outside 2 ** 64
randomBigIntBetween(0n, 100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000n)
// between normal and pretty big
randomBigIntBetween(100000n, 100000100000100000100000n)
// between pretty big and big
randomBigIntBetween(100000100000100000100000n, 100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000n)
Here is my attempt so far:
// small
logBetween(0n, 10n)
// normal but bigger than 65536
logBetween(0n, 100000n)
// pretty big but still within JS 2 ** 64
logBetween(0n, 100000100000100000100000n)
// big, outside of 2 ** 64
logBetween(0n, 100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000n)
// huge, way outside 2 ** 64
logBetween(0n, 100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000n)
// between normal and pretty big
logBetween(100000n, 100000100000100000100000n)
// between pretty big and big
logBetween(100000100000100000100000n, 100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000n)
function logBetween(a, b) {
console.log(randomBigIntBetween(a, b), `${a} <=> ${b}`)
}
function randomBigIntBetween(a, b) {
const startIntegers = convertBigIntToSmallIntegerArray(a)
const endIntegers = convertBigIntToSmallIntegerArray(b)
const integers = startIntegers.concat(endIntegers)
// get to at least the minimum
const string = integers
.map(i => randomIntFromInterval(0, Number(i)))
.filter(x => x)
.map(x => String(x))
.join('')
// this only gives us a rough approximation of the min,
// so we will miss out on values close to the min... unfortunately, bug 1.
const minLength = String(a).length + 1
// this is bug 2, for same reason, we miss out on values close to the max.
const maxLength = String(b).length - 1
if (string.length < minLength) {
console.log('Bug 3: we got even the first part wrong, building the string')
}
if (string.length > minLength) {
console.log('Bug 4: somehow the math didnt work out on mental string length calculations')
}
// if we made it this far, we at least have a random length string of the right size.
// now we can just randomly select a substring.
const endIndex = randomIntFromInterval(minLength, string.length)
return string.slice(0, endIndex)
}
// HT @trincot (on SO) for similar function
function convertBigIntToSmallIntegerArray(n, mod = 4294967296n /* 2^32 */) {
if (!n) return [0]
const integers = []
while (n) {
integers.push(Number(n % mod))
n /= mod
}
return integers
}
function randomIntFromInterval(min, max) {
return Math.floor(Math.random() * (max - min + 1) + min)
}That outputs something like:
10 0 <=> 10
Bug 4: somehow the math didnt work out on mental string length calculations
323 0 <=> 100000
Bug 4: somehow the math didnt work out on mental string length calculations
187748 0 <=> 100000100000100000100000
Bug 4: somehow the math didnt work out on mental string length calculations
7488008031035416161116583158125647758213653175196571552799813752520677561023876102581 0 <=> 100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000
Bug 4: somehow the math didnt work out on mental string length calculations
596431717281625308116466022882589339106190467537819772952419576420529268054792468522313797492282590143651702183212213872522407289033698622436610124342872091921136180390192 0 <=> 100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000
Bug 4: somehow the math didnt work out on mental string length calculations
7541624715269284249 100000 <=> 100000100000100000100000
Bug 4: somehow the math didnt work out on mental string length calculations
74900957124663882227641805255668908641334512242118204066019699 100000100000100000100000 <=> 100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000100000
We are tangentially on the right track (strings are getting longer, and seem roughly in between), but there is probably a dozen things wrong with my approach so far. It's tricky to describe exactly what I might be getting wrong (I am not sure what it is exactly yet, which knowing would help me get past this current roadblock).
How to construct an algorithm to generate arbitrarily long BigInt values, between a min and a max, in JavaScript, where the range could be tiny (small ints) or huge (way beyond 2 ** 64 in size), or anywhere in between, like with the sample function calls above?
