Fastest way to convert U~[0,1) to index of 1000 items-CodePudding

Say I generate a uniform random number [0,1), what is the fastest way to convert that to index of 1000?

One way is to multiply by 1000 and then take the floor:

const u = Math.random();
const index = Math.floor(1000*u);

is there a computationally faster way, perhaps with bitwise operators?

CodePudding user response：

One way to convert a uniform random number between 0 and 1 to an index between 0 and 999 would be to multiply the random number by 1000 and then take the integer part of the result using the Math.floor() function. For example:

    let randomNumber = Math.random(); // generates a random number between 0 and 1
let index = Math.floor(randomNumber * 1000); // scales the number and takes the integer part

This method is fast because it only requires a single multiplication and a single call to Math.floor(), which are both fast operations. However, keep in mind that this method will only work if you want to generate a random index between 0 and 999 (inclusive). If you want to generate a random index between 1 and 1000 (inclusive), you will need to add 1 to the result of the Math.floor() operation

let randomNumber = Math.random(); // generates a random number between 0 and 1
let index = Math.floor(randomNumber * 1000)   1; // scales the number, takes the integer part, and adds 1

Hope this helps! Let me know if you have any other questions.

CodePudding user response：

Don't believe any bitwise OP's will give you any benefit here, mainly because 1000 is not a binary number like 16,32,64 etc..

But one area you could improve performance is in truncating the value, you can force JS to use 16bit integer, this is a hint to the JS engine that allows it to use faster 16bit Maths.

Below is an example.

On my machine I get a slight performance boost using the UInt16Array..

t1: 3.100ms
49950492
t2: 2.200ms
49950492

var U16 = new Uint16Array([0]);

console.time('t1');
let v = 0;
for (let l = 0; l <=1 ;l  = 0.00001) {
  v  = Math.trunc(l*1000);
}
console.timeEnd('t1');
console.log(v);

console.time('t2');
v = 0;
for (let l = 0; l <=1 ;l  = 0.00001) {
  U16[0] = l * 1000;
  v  = U16[0];
}
console.timeEnd('t2');
console.log(v);

CodePudding user response：

One way to convert a uniformly-distributed random number in the range [0,1) to an index in the range [0,1000) would be to multiply the random number by 1000 and take the integer part, as you have shown in your example. This can be done using the Math.trunc() method, which returns the integer part of a number by removing any fractional digits.

Here is an example of how you could use the Math.trunc() method to convert a random number to an index in the range [0,1000):

const u = Math.random();
const index = Math.trunc(1000*u);

Using the Math.trunc() method is generally faster than using the Math.floor() method, because it does not have to round the number down to the nearest integer. However, it's important to note that the difference in performance will likely be very small, and may not be noticeable in most cases.

Another way to convert a random number to an index in the range [0,1000) would be to use a bitwise operator, such as the bitwise AND operator (&), like this:

const u = Math.random();
const index = (u * 1000) & 0b1111111111;

In this example, we first multiply the random number by 1000. Then, we use the bitwise AND operator to perform a bitwise AND operation on the result and the binary number 0b1111111111, which is equivalent to the decimal number 999. This will effectively "mask" the upper bits of the number, so that only the lower 10 bits are retained. This will ensure that the resulting number is in the range [0,1000), because the maximum value of the lower 10 bits is 1023, which is less than 1000.

Using a bitwise operator to convert a random number to an index in the range [0,1000) may be slightly faster than using the Math.trunc() method, because it involves fewer mathematical operations. However, as with the Math.trunc() method, the difference in performance will likely be very small, and may not be noticeable in most cases.

Ultimately, the best approach will depend on your specific use case and requirements. If performance is a critical concern, it may be worth doing some benchmarking to determine which approach is fastest in your particular scenario. Let me know if you have any other questions.