JavaScript random BigInt

Question

Problem: JavaScript does not provide a random BigInt so there is a need to generate a random BigInt within a given range that is evenly distributed.

Solution I have tried many algorithms with a emphasis on speed. The best solution builds an array of random Int32 converted to string and padded with zeros which are then joined converted to a BigInt with the return being BitInt % range

function randBigInt2(range) { // returns BigInt 0 to (range non inclusive)
 var rand = [], digits = range.toString().length / 9 + 2 | 0;
 while (digits--) { 
 rand.push(("" + (Math.random() * 1000000000 | 0)).padStart(9, "0"));
 }
 return BigInt(rand.join("")) % range; // Leading zeros are ignored
}

As Math.log can not be used to get the number of digits in range I am forced to use a hack of converting range to a string and using the string length to get log₁₀

The generated array of digits is at least 9 digits longer than the required range to counter the problem of bias to numbers that end in digits less than the least significant digit. Though the bias still exists, it is so small that I am unable to detect it in any tests.

If the range is a multiple of 10 there is no bias

The alternative function that uses BigInt in the calculation is about 2-4% slower.

function randBigInt(range) {
 var rand = 0n, digits = range.toString().length / 9 + 2 | 0;
 while(digits--) {
 rand *= 1000000000n;
 rand += BigInt(Math.random() * 1000000000 | 0);
 }
 return rand % range;
}

Are there any flaws in my logic?

• woxxom: I'd use the entire meaningful part of Math.random - at least 15 digits are guaranteed by IEEE754 spec.
• Blindman67: @wOxxOm Unfortunately BigInt math in JS is SLOW.. Using rand += BigInt(Math.floor(Math.random() * 1e15)); 40% fewer iterations and will increase performance for small ranges by 50%. Its even at 1e140 and 20% slower at 1e1500. Also tried rand += BigInt(Math.trunc(Math.random() * 1e15)); BigInt will not convert if there is a fractional component. Using the string Math.random().toString() gives 15 digits but will shorten the notation if it can eg 1e-14 so add overhead and thus nit worth it.
• Domino: I haven't done research in that regard, but I wonder if using Crypto.getRandomValues() with a BigUint64Array would be more efficient for very large numbers.

Answer 1

magic numbers

The values \1,000,000,000ドル\$ and \9ドル\$ are not well motivated. At a minimum they deserve comments or helpful identifier names.

I understand we're talking about a value less than four billion (once I've inserted commas), but it's unclear how that value is related to \49,007,199,254,740,991ドル\$. Doesn't Math.random() offer 53 bits of entropy? Though this bit of documentation sounds like it could be Mersenne Twister, making me wonder why we would ever wish to call it:

Note: Math.random() does not provide cryptographically secure random numbers. Do not use them for anything related to security. Use the Web Crypto API instead

When an API says "random", that makes me think "indistinguishable", so I naturally gravitate toward crypto secure implementations.

one-liner

There's no point to compressing this pair of assignments down to a single line.

 var rand = [], digits = range. ...

Use another punch card! Put var digits on a line of its own.

cryptic type conversion

The | 0 hack is pointless. Be explicit; call Math.floor() already.

Similar critique for the Math.random() * 1000000000 | 0 expression. If there's some concern you have in mind, say it, don't be oblique about it.

BigInt is about decimal digits

The whole business of working in nine- or ten-digit chunks seems a little suspect. And there's no need for a BigInt() call within a tight loop.

1. Determine how many digits are necessary; call it \$N\$.
2. Loop to roll \$N\$ random digits, uniformly distributed from \0ドル ~ .. \thinspace 9\$.
3. [optional step]
4. Glue those random digits together.
5. Present the digits to BigInt().
6. Use rejection sampling to perhaps re-roll.

Using an "obvious" approach like this will make it much easier for future maintenance engineers to immediately see that the library routine satisfies its contract. An optional step might re-roll based on just the high order digit, to avoid some (expensive) BigInt() calls.

standard library

Consider calling getRandomValues to produce a bunch of Uint8Array values. Typically you'll win with a single call. Mask them down to four bits, then do rejection sampling to discard values greater than \9ドル\$.

• Blindman67: Bitwise operators (under the hood) do a type conversion from double to int32 (aka int32_t). I see num | 0 in JS I think (std::int32_t)num C++/C. I'm not flooring, I am casting for performance (tc39.es/ecma262/multipage/… Spec returns a Number (double) engines defer cast to double saving significant number of cycles when using the internal int32 (mostly parameter type coercions via abstract operator calls (see; 7 Abstract Operations in spec Draft ECMA-262 Jan9,2025). 1,000,000,000 is < 2**31-1 (max int32 safe to cast)
• J_H: @Blindman67, When I write source code, I do it primarily to convey a technical idea to human collaborators, and only secondarily for the machine to expend cycles upon it. I think I start to see why there's just a subset of languages that I usually express my ideas in. If the compiler can't see through to my intent, then it's not my best medium for expression. // Similarly for tail-call optimization in scheme vs generic Common Lisp, or for the endless endian and bit-length changes in the various C specs. Perhaps TypeScript improves upon such idioms.