代码之家 › 专栏 › 技术社区 › Xotic750

randomInt函数,可统一处理MIN和MAX_SAFE_INTEGER的全部范围

limit integer random algorithm javascript

Xotic750 · 技术社区 · 10 年前

要求和背景

我想要一个普通的 randomInt 可以处理一系列值的函数,包括 Number.MIN_SAFE_INTEGER 到 Number.MAX_SAFE_INTEGER 并且返回的值为 uniformly distributed .

所以,我从MDN开始 Math.random 页他们举了一个例子,似乎是均匀分布的。

// Returns a random integer between min (included) and max (excluded)
// Using Math.round() will give you a non-uniform distribution!
function getRandomInt(min, max) {
  return Math.floor(Math.random() * (max - min)) + min;
}

但它附带以下注释。

注意,JavaScript中的数字是IEEE 754浮点数对于四舍五入的偶数行为下面的函数(不包括Math.random()本身的函数)不是准确的如果选择了非常大的边界(2^53或更高) 在极少数情况下可以计算通常排除的上限。

我想使用范围-(2^53-1)和2^53-1,因此我认为此注释不适用。然后我注意到 max - min :对于我指定的较大范围,这将是一个问题:

示例-最大范围

Number.MAX_SAFE_INTEGER - Number.MIN_SAFE_INTEGER > Number.MAX_SAFE_INTEGER

解决方案1-不是解决方案

接下来,我根据MDN示例和我的需求,进行了一次小游戏,并编写了以下代码。

Number.MAX_SAFE_INTEGER = Number.MAX_SAFE_INTEGER || 9007199254740991;

Number.MIN_SAFE_INTEGER = Number.MIN_SAFE_INTEGER || -Number.MAX_SAFE_INTEGER;

Number.toInteger = Number.toInteger || function (inputArg) {
    var number = +inputArg,
        val = 0;

    if (number === number) {
        if (!number || number === Infinity || number === -Infinity) {
            val = number;
        } else {
            val = (number > 0 || -1) * Math.floor(Math.abs(number));
        }
    }

    return val;
};

function clampSafeInt(number) {
    return Math.min(Math.max(Number.toInteger(number), Number.MIN_SAFE_INTEGER), Number.MAX_SAFE_INTEGER);
}

// Returns a random integer between min (included) and max (included)
// Using Math.round() will give you a non-uniform distribution!
function randomInt(min, max) {
    var tmp,
        val;

    if (arguments.length === 1) {
        max = min;
        min = 0;
    }

    min = clampSafeInt(min);
    max = clampSafeInt(max);
    if (min > max) {
        tmp = min;
        min = max;
        max = tmp;
    }

    tmp = max - min + 1;
    if (tmp > Number.MAX_SAFE_INTEGER) {
        throw new RangeError('Difference of max and min is greater than Number.MAX_SAFE_INTEGER: ' + tmp);
    } else {
        val = Math.floor(Math.random() * tmp) + min;
    }
    
    return val;
}

console.log(randomInt(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER));

但正如你所看到的,这将在我需要的更大范围之前抛出一个错误。

解决方案2-解决了数学问题,但似乎打破了一致性

所以我有一把小提琴,并提出了以下建议。

Number.MAX_SAFE_INTEGER = Number.MAX_SAFE_INTEGER || 9007199254740991;

Number.MIN_SAFE_INTEGER = Number.MIN_SAFE_INTEGER || -Number.MAX_SAFE_INTEGER;

Number.toInteger = Number.toInteger || function (inputArg) {
    var number = +inputArg,
        val = 0;

    if (number === number) {
        if (!number || number === Infinity || number === -Infinity) {
            val = number;
        } else {
            val = (number > 0 || -1) * Math.floor(Math.abs(number));
        }
    }

    return val;
};

function clampSafeInt(number) {
    return Math.min(Math.max(Number.toInteger(number), Number.MIN_SAFE_INTEGER), Number.MAX_SAFE_INTEGER);
}

// Returns a random integer between min (included) and max (included)
// Using Math.round() will give you a non-uniform distribution!
function randomInt(min, max) {
    var tmp,
        val;

    if (arguments.length === 1) {
        max = min;
        min = 0;
    }

    min = clampSafeInt(min);
    max = clampSafeInt(max);
    if (min > max) {
        tmp = min;
        min = max;
        max = tmp;
    }

    tmp = max - min + 1;
    if (tmp > Number.MAX_SAFE_INTEGER) {
        if (Math.floor(Math.random() * 2)) {
            val = Math.floor(Math.random() * (max - 0 + 1)) + 0;
        } else {
            val = Math.floor(Math.random() * (0 - min + 1)) + min;
        }
    } else {
        val = Math.floor(Math.random() * tmp) + min;
    }
    
    return val;
}

console.log(randomInt(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER));

虽然我们不再抛出错误,并且数学似乎在最大安全整数值范围内,但我不确定这是如何影响原始MDN示例的均匀分布的(如果它是均匀分布的)?

我的测试似乎表明这打破了均匀分布。

分布图

function getData() {
  var x = {},
    c = 1000000,
    min = -20,
    max = 20,
    q,
    i;

  for (i = 0; i < c; i += 1) {
    if (Math.floor(Math.random() * 2)) {
      q = Math.floor(Math.random() * (max - 0 + 1)) + 0;
    } else {
      q = Math.floor(Math.random() * (1 - min + 1)) + min;
    }

    if (!x[q]) {
      x[q] = 1;
    } else {
      x[q] += 1;
    }
  };

  return Object.keys(x).sort(function(x, y) {
    return x - y;
  }).map(function(key, index) {
    return {
      'q': +key,
      'p': (x[key] / c) * 100
    };
  });
}

var data = getData(),
  margin = {
    top: 20,
    right: 20,
    bottom: 30,
    left: 50
  },
  width = 960 - margin.left - margin.right,
  height = 500 - margin.top - margin.bottom,
  x = d3.scale.linear().range([0, width]),
  y = d3.scale.linear().range([height, 0]),
  xAxis = d3.svg.axis().scale(x).orient("bottom"),
  yAxis = d3.svg.axis().scale(y).orient("left"),
  line = d3.svg.line().x(function(d) {
    return x(d.q);
  }).y(function(d) {
    return y(d.p);
  }),
  svg = d3.select("body").append("svg")
  .attr("width", width + margin.left + margin.right)
  .attr("height", height + margin.top + margin.bottom)
  .append("g")
  .attr("transform", "translate(" + margin.left + "," + margin.top + ")");

x.domain(d3.extent(data, function(d) {
  return d.q;
}));

y.domain(d3.extent(data, function(d) {
  return d.p;
}));

svg.append("g")
  .attr("class", "x axis")
  .attr("transform", "translate(0," + height + ")")
  .call(xAxis);

svg.append("g")
  .attr("class", "y axis")
  .call(yAxis);

svg.append("path")
  .datum(data)
  .attr("class", "line")
  .attr("d", line);

body {
  font: 10px sans-serif;
}
.axis path,
.axis line {
  fill: none;
  stroke: #000;
  shape-rendering: crispEdges;
}
.line {
  fill: none;
  stroke: steelblue;
  stroke-width: 1.5px;
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.4.11/d3.min.js"></script>

解决方案3-不是解决方案

因此,我按下并查看创建 Box-Muller Transform 用于创建我认为需要的随机正态分布范围的函数(但我的错误是我希望均匀分布)。我读了一些书,选择了 rejection sampling 作为从分布生成观测值的方法。了解如何在不使用 Math.sqrt :

如果x的值为负值,Math.sqrt()将返回NaN

这就是我想到的。

Number.MAX_SAFE_INTEGER = Number.MAX_SAFE_INTEGER || 9007199254740991;

Number.MIN_SAFE_INTEGER = Number.MIN_SAFE_INTEGER || -Number.MAX_SAFE_INTEGER;

Number.toInteger = Number.toInteger || function (inputArg) {
    var number = +inputArg,
        val = 0;

    if (number === number) {
        if (!number || number === Infinity || number === -Infinity) {
            val = number;
        } else {
            val = (number > 0 || -1) * Math.floor(Math.abs(number));
        }
    }

    return val;
};

function clampSafeInt(number) {
    return Math.min(Math.max(Number.toInteger(number), Number.MIN_SAFE_INTEGER), Number.MAX_SAFE_INTEGER);
}

var boxMullerRandom = (function () {
    var phase = 0,
        RAND_MAX,
        array,
        random,
        x1, x2, w, z;

    if (crypto && crypto.getRandomValues) {
        RAND_MAX = Math.pow(2, 32) - 1;
        array = new Uint32Array(1);
        random = function () {
            crypto.getRandomValues(array);

            return array[0] / RAND_MAX;
        };
    } else {
        random = Math.random;
    }

    return function () {
        if (!phase) {
            do {
                x1 = 2.0 * random() - 1.0;
                x2 = 2.0 * random() - 1.0;
                w = x1 * x1 + x2 * x2;
            } while (w >= 1.0);

            w = Math.sqrt((-2.0 * Math.log(w)) / w);
            z = x1 * w;
        } else {
            z = x2 * w;
        }

        phase ^= 1;

        return z;
    }
}());

function rejectionSample(stdev, mean, from, to) {
    var retVal;
    
    do {
        retVal = (boxMullerRandom() * stdev) + mean;
    } while (retVal < from || to < retVal);

    return retVal;
}

function randomInt(min, max) {
    var tmp,
        val;

    if (arguments.length === 1) {
        max = min;
        min = 0;
    }

    min = clampSafeInt(min);
    max = clampSafeInt(max);
    if (min > max) {
        tmp = min;
        min = max;
        max = tmp;
    }

    tmp = {};
    tmp.mean = (min / 2) + (max / 2);
    tmp.variance = (Math.pow(min - tmp.mean, 2) + Math.pow(max - tmp.mean, 2)) / 2;
    tmp.deviation = Math.sqrt(tmp.variance);
    console.log(tmp);
    return Math.floor(rejectionSample(tmp.deviation, tmp.mean, min, max + 1));
}

console.log(randomInt(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER));

我不确定我做的一切都正确(没有打破正态分布),但在小整数范围内,我看到了生成的随机整数的正确范围。

但当我使用范围的最大极限(或者实际上在这些极限之前)时,仍然存在一个问题。数学仍然超出了 数字.MAX_SAFE_INTEGER 价值从上方输出 console.log(tmp);

{mean: 0, variance: 8.112963841460666e+31, deviation: 9007199254740991}

如您所见 variance 不安全。由于我对分布类型的混淆,可以忽略此算法。

分布图

我把它包括在内,这样你就可以看到,我实际上很接近于将这项工作作为正态分布,尽管这不是我实际需要的。它可能有助于希望执行这种分配的人。

Number.MAX_SAFE_INTEGER = Number.MAX_SAFE_INTEGER || 9007199254740991;

Number.MIN_SAFE_INTEGER = Number.MIN_SAFE_INTEGER || -Number.MAX_SAFE_INTEGER;

Number.toInteger = Number.toInteger || function(inputArg) {
  var number = +inputArg,
    val = 0;

  if (number === number) {
    if (!number || number === Infinity || number === -Infinity) {
      val = number;
    } else {
      val = (number > 0 || -1) * Math.floor(Math.abs(number));
    }
  }

  return val;
};

function clampSafeInt(number) {
  return Math.min(Math.max(Number.toInteger(number), Number.MIN_SAFE_INTEGER), Number.MAX_SAFE_INTEGER);
}

var boxMullerRandom = (function() {
  var phase = 0,
    RAND_MAX,
    array,
    random,
    x1, x2, w, z;

  if (crypto && crypto.getRandomValues) {
    RAND_MAX = Math.pow(2, 32) - 1;
    array = new Uint32Array(1);
    random = function() {
      crypto.getRandomValues(array);

      return array[0] / RAND_MAX;
    };
  } else {
    random = Math.random;
  }

  return function() {
    if (!phase) {
      do {
        x1 = 2.0 * random() - 1.0;
        x2 = 2.0 * random() - 1.0;
        w = x1 * x1 + x2 * x2;
      } while (w >= 1.0);

      w = Math.sqrt((-2.0 * Math.log(w)) / w);
      z = x1 * w;
    } else {
      z = x2 * w;
    }

    phase ^= 1;

    return z;
  }
}());

function rejectionSample(stdev, mean, from, to) {
  var retVal;

  do {
    retVal = (boxMullerRandom() * stdev) + mean;
  } while (retVal < from || to < retVal);

  return retVal;
}

function randomInt(min, max) {
  var tmp,
    val;

  if (arguments.length === 1) {
    max = min;
    min = 0;
  }

  min = clampSafeInt(min);
  max = clampSafeInt(max);
  if (min > max) {
    tmp = min;
    min = max;
    max = tmp;
  }

  tmp = {};
  tmp.mean = (min / 2) + (max / 2);
  tmp.variance = (Math.pow(min - tmp.mean, 2) + Math.pow(max - tmp.mean, 2)) / 2;
  tmp.deviation = Math.sqrt(tmp.variance);

  return Math.floor(rejectionSample(tmp.deviation, tmp.mean, min, max + 1));
}

function getData() {
  var x = {},
    c = 1000000,
    q,
    i;

  for (i = 0; i < c; i += 1) {
    q = randomInt(-9, 3);
    if (!x[q]) {
      x[q] = 1;
    } else {
      x[q] += 1;
    }
  };

  return Object.keys(x).sort(function(x, y) {
    return x - y;
  }).map(function(key) {
    return {
      'q': +key,
      'p': x[key] / c
    };
  });
}

var data = getData(),
  margin = {
    top: 20,
    right: 20,
    bottom: 30,
    left: 50
  },
  width = 960 - margin.left - margin.right,
  height = 500 - margin.top - margin.bottom,
  x = d3.scale.linear().range([0, width]),
  y = d3.scale.linear().range([height, 0]),
  xAxis = d3.svg.axis().scale(x).orient("bottom"),
  yAxis = d3.svg.axis().scale(y).orient("left"),
  line = d3.svg.line().x(function(d) {
    return x(d.q);
  }).y(function(d) {
    return y(d.p);
  }),
  svg = d3.select("body").append("svg")
  .attr("width", width + margin.left + margin.right)
  .attr("height", height + margin.top + margin.bottom)
  .append("g")
  .attr("transform", "translate(" + margin.left + "," + margin.top + ")");

x.domain(d3.extent(data, function(d) {
  return d.q;
}));

y.domain(d3.extent(data, function(d) {
  return d.p;
}));

svg.append("g")
  .attr("class", "x axis")
  .attr("transform", "translate(0," + height + ")")
  .call(xAxis);

svg.append("g")
  .attr("class", "y axis")
  .call(yAxis);

svg.append("path")
  .datum(data)
  .attr("class", "line")
  .attr("d", line);

正文{
字体:10px无衬线;
}
.轴路径,
.轴线{
填充:无;
冲程:#000;
形状渲染:crispEdges;
}
.行{
填充:无;
笔划:钢蓝;
笔划宽度:1.5px;
}

<script src=“https://cdnjs.cloudflare.com/ajax/libs/d3/3.4.11/d3.min.js“></script>

有什么解决方案 ?

那么,我错过了什么?有没有我忽略了的简单方法?我必须使用大号码库作为解决方案吗?如何测试分布:我有一些正在绘制的图表,这对于小范围来说很好,但大范围是不可能的?

请让我在这件事上摆脱痛苦

3 回复 | 直到 10 年前

Lee Daniel Crocker 10 年前

为什么不调用Math.random()两次,每次调用26位?这是相当安全的范围内,它可以产生良好的一致性。

function random53() {
    var hi, lo, sign = 0;

    while (true) {
        hi = Math.floor(67108864 * Math.random());
        lo = Math.floor(67108864 * Math.random());

        if (hi >= 33554432) {
            sign = -1;
            hi -= 33554432;

            // Gotta throw out negative zero!
            if (0 === hi && 0 === lo) { continue; }
        }
        return sign * (hi * 67108864) + lo;
    }
}

Xotic750 10 年前

一个可行的解决方案,我所走的路线是使用BigNumber库。我仍然觉得必须有一个解决这个问题的方法,而不需要依赖BigNumber库,但我还没有找到其他方法。

console.log(window);
Number.MAX_SAFE_INTEGER = Number.MAX_SAFE_INTEGER || 9007199254740991;

Number.MIN_SAFE_INTEGER = Number.MIN_SAFE_INTEGER || -Number.MAX_SAFE_INTEGER;

Number.toInteger = Number.toInteger || function (inputArg) {
    var number = +inputArg,
        val = 0;

    if (number === number) {
        if (!number || number === Infinity || number === -Infinity) {
            val = number;
        } else {
            val = (number > 0 || -1) * Math.floor(Math.abs(number));
        }
    }

    return val;
};

function clampSafeInt(number) {
    return Math.min(Math.max(Number.toInteger(number), Number.MIN_SAFE_INTEGER), Number.MAX_SAFE_INTEGER);
}

// Returns a random integer between min (included) and max (included)
// Using Math.round() will give you a non-uniform distribution!
function randomInt(min, max) {
    var tmp,
    val;

    if (arguments.length === 1) {
        max = min;
        min = 0;
    }

    min = clampSafeInt(min);
    max = clampSafeInt(max);
    if (min > max) {
        tmp = min;
        min = max;
        max = tmp;
    }

    tmp = max - min + 1;
    if (tmp > Number.MAX_SAFE_INTEGER) {
        tmp = new Big(max).minus(min).plus(1);
        val = Math.floor(tmp.times(Math.random())) + min;
    } else {
        val = Math.floor(Math.random() * tmp) + min;
    }

    return val;
}

console.log(randomInt(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER));

<script src="https://rawgithub.com/MikeMcl/big.js/master/big.min.js"></script>

Will 4 年前

对于在这个老问题上犯错误的任何人来说:有一种方法可以完全避开OP描述的数字边界问题,即完全避免解释 Math.random() 作为浮点类型:

const all64RandomBits = Float64Array.of(Math.random()).buffer

上面的行简单地获取了Typed Array类型的二进制缓冲区,该类型具有与JavaScript相同的IEEE 754编码数字类型:a Float64阵列 .

一旦有了这个BufferArray,就可以通过选择适当的整数视图和/或根据需要应用逐位and、or和移位来获得所需的任意数量的随机位。例如,要将所有64个随机位转换为2个数字,每个数字的无符号整数值范围为0-UINT32_MAX?你只需要这个可爱的小内衬:

const [x, y] = new Uint32Array(Float64Array.of(Math.random()).buffer)