[javascript] 자바 스크립트에서 난수 생성기 시드

평범한 JavaScript로 PRNG ( Pseudorandom Number Generator ) 기능 을 훌륭하고 짧고 빠르게 구현했습니다 . 그들 모두는 파종 될 수 있고 양질의 숫자를 제공합니다.

우선, PRNG를 올바르게 초기화하십시오. 아래의 대부분의 생성기는 기본 제공 시드 생성 절차가 없지만 (단순화를 위해) PRNG 의 초기 상태 로 하나 이상의 32 비트 값을 허용합니다 . 유사한 시드 (예 : 1과 2의 간단한 시드)는 약한 PRNG에서 상관 관계를 유발할 수 있으며 결과적으로 출력이 비슷한 특성을 갖습니다 (예 : 무작위로 생성 된 레벨이 유사 함). 이를 피하려면, 잘 분산 된 시드로 PRNG를 초기화하는 것이 가장 좋습니다.

고맙게도 해시 함수는 짧은 문자열에서 PRNG에 대한 시드를 생성하는 데 매우 유용합니다. 좋은 해시 함수는 두 문자열이 비슷한 경우에도 매우 다른 결과를 생성합니다. MurmurHash3의 믹싱 기능을 기반으로 한 예는 다음과 같습니다.

function xmur3(str) {
    for(var i = 0, h = 1779033703 ^ str.length; i < str.length; i++)
        h = Math.imul(h ^ str.charCodeAt(i), 3432918353),
        h = h << 13 | h >>> 19;
    return function() {
        h = Math.imul(h ^ h >>> 16, 2246822507);
        h = Math.imul(h ^ h >>> 13, 3266489909);
        return (h ^= h >>> 16) >>> 0;
    }
}

리턴 함수 의 각 후속 호출 xmur3은 PRNG에서 시드로 사용되는 새로운 “임의”32 비트 해시 값을 생성합니다. 사용 방법은 다음과 같습니다.

// Create xmur3 state:
var seed = xmur3("apples");
// Output four 32-bit hashes to provide the seed for sfc32.
var rand = sfc32(seed(), seed(), seed(), seed());

// Output one 32-bit hash to provide the seed for mulberry32.
var rand = mulberry32(seed());

// Obtain sequential random numbers like so:
rand();
rand();

또는 시드를 채울 더미 데이터를 선택하고 초기 상태를 완전히 혼합하기 위해 생성기를 몇 번 (12-20 회 반복) 진행시킵니다. 이것은 종종 PRNG의 참조 구현에서 볼 수 있지만 초기 상태 수를 제한합니다.

var seed = 1337 ^ 0xDEADBEEF; // 32-bit seed with optional XOR value
// Pad seed with Phi, Pi and E.
// https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number
var rand = sfc32(0x9E3779B9, 0x243F6A88, 0xB7E15162, seed);
for (var i = 0; i < 15; i++) rand();

이러한 PRNG 함수의 출력은 32 비트 양의 번호 (0 ~ 2 제조 ³² 에 상당 후 0-1 (0 포함 1 명 제외) 사이의 부동 소수점 수로 변환된다 -1) Math.random()는 난수를 원한다면 특정 범위의 MDN에 대한이 기사를 읽으십시오 . 원시 비트 만 원하면 최종 분할 연산을 제거하십시오.

주목해야 할 또 다른 사항은 JS의 한계입니다. 숫자는 최대 53 비트 해상도의 전체 정수만 나타낼 수 있습니다. 비트 단위 연산을 사용할 때는 32로 줄어 듭니다. 이로 인해 64 비트 숫자를 사용하는 C 또는 C ++로 작성된 알고리즘을 구현하기가 어렵습니다. 64 비트 코드를 포팅하려면 성능 이 크게 저하 될 수있는 심이 필요합니다 . 따라서 단순성과 효율성을 위해 32 비트 수학을 사용하는 알고리즘 만 고려했습니다. JS와 직접 호환되기 때문입니다.

이제 발전기로 넘어갑니다. (나는 여기 를 참조하여 전체 목록을 유지합니다 )

sfc32 (간이 고속 카운터)

sfc32 는 PractRand 난수 테스트 스위트 (물론 통과)의 일부입니다. sfc32는 128 비트 상태이며 JS에서 매우 빠릅니다.

function sfc32(a, b, c, d) {
    return function() {
      a >>>= 0; b >>>= 0; c >>>= 0; d >>>= 0;
      var t = (a + b) | 0;
      a = b ^ b >>> 9;
      b = c + (c << 3) | 0;
      c = (c << 21 | c >>> 11);
      d = d + 1 | 0;
      t = t + d | 0;
      c = c + t | 0;
      return (t >>> 0) / 4294967296;
    }
}

멀 베리 32

Mulberry32는 32 비트 상태의 간단한 생성기이지만 매우 빠르며 좋은 품질을 제공합니다 (저자 gjrand 테스트 스위트 의 모든 테스트를 통과 하고 전체 2 ³² 기간이 있지만 검증되지 않았습니다).

function mulberry32(a) {
    return function() {
      var t = a += 0x6D2B79F5;
      t = Math.imul(t ^ t >>> 15, t | 1);
      t ^= t + Math.imul(t ^ t >>> 7, t | 61);
      return ((t ^ t >>> 14) >>> 0) / 4294967296;
    }
}

간단하지만 괜찮은 PRNG가 필요하고 수십억 개의 임의의 숫자가 필요하지 않은 경우이 방법을 권장 합니다 ( 생일 문제 참조 ).

xoshiro128 **

2018 년 5 월 현재, xoshiro128 ** 는 Vigna / Blackman (Choro에서 사용되는 xoroshiro도 작성 함) 의 Xorshift 제품군 의 새로운 멤버입니다 . 128 비트 상태를 제공하는 가장 빠른 생성기입니다.

function xoshiro128ss(a, b, c, d) {
    return function() {
        var t = b << 9, r = a * 5; r = (r << 7 | r >>> 25) * 9;
        c ^= a; d ^= b;
        b ^= c; a ^= d; c ^= t;
        d = d << 11 | d >>> 21;
        return (r >>> 0) / 4294967296;
    }
}

저자는 무작위 테스트를 잘 통과한다고 주장합니다 ( 주의 사항에도 불구하고 ). 다른 연구자들은 TestU01 (특히 LinearComp 및 BinaryRank)의 일부 테스트에 실패한다고 지적했습니다. 실제로 플로트를 사용할 때 (이러한 구현과 같은) 문제를 일으키지 않아야하고 로우 로우 비트에 의존하는 경우 문제를 일으킬 수 있습니다.

JSF (젠킨스 스몰 패스트)

이것은 ISAAC 와 SpookyHash 를 만든 Bob Jenkins (2007)의 JSF 또는 ‘smallprng’ 입니다. 그것은 통과 아니지만 빠른 SFC로, PractRand 테스트를 꽤 빨리해야합니다.

function jsf32(a, b, c, d) {
    return function() {
        a |= 0; b |= 0; c |= 0; d |= 0;
        var t = a - (b << 27 | b >>> 5) | 0;
        a = b ^ (c << 17 | c >>> 15);
        b = c + d | 0;
        c = d + t | 0;
        d = a + t | 0;
        return (d >>> 0) / 4294967296;
    }
}

LCG (일명 Lehmer / Park-Miller RNG 또는 MCG)

LCG는 매우 빠르고 간단하지만 임의의 품질이 너무 낮아서 잘못 사용하면 실제로 프로그램에 버그가 발생할 수 있습니다! 그럼에도 불구하고 Math.sin또는 사용을 제안하는 일부 답변보다 훨씬 낫습니다 Math.PI! 그래도 하나의 라이너입니다. :).

var LCG=s=>()=>(2**31-1&(s=Math.imul(48271,s)))/2**31;

이 구현 을 1988 년과 1993 년 에 Park–Miller가 제안한대로 최소 표준 RNG 라고하며 C ++ 11에서로 구현됩니다 . 상태는 31 비트입니다 (31 비트는 20 억 개의 가능한 상태를 제공하고 32 비트는 두 배를 제공함). 이것은 다른 사람들이 대체하려는 PRNG 유형입니다!minstd_rand

작동하지만 속도가 실제로 필요하고 무작위성에 신경 쓰지 않는 한 사용 하지 않을 것입니다 (어쨌든 무작위는 무엇입니까?). 게임 잼이나 데모 또는 무언가를 위해 중대한. LCG는 시드 상관 관계가 있으므로 LCG 의 첫 번째 결과 를 버리는 것이 가장 좋습니다 . LCG 사용을 주장하는 경우 증분 값을 추가하면 결과가 향상 될 수 있지만 훨씬 더 나은 옵션이 존재하는 경우 무용지물이 될 수 있습니다.

32 비트 상태 (상태 공간 증가)를 제공하는 다른 승수가있는 것 같습니다.

var LCG=s=>()=>(s=Math.imul(741103597,s)>>>0)/2**32;
var LCG=s=>()=>(s=Math.imul(1597334677,s)>>>0)/2**32;

이 LCG 값은 다음과 같습니다. P. L’ Ecuyer : 1997 년 4 월 30 일, 크기와 격자 구조가 다른 선형 합동 발생기 표.

답변

var m_w = 123456789;
var m_z = 987654321;
var mask = 0xffffffff;

// Takes any integer
function seed(i) {
    m_w = (123456789 + i) & mask;
    m_z = (987654321 - i) & mask;
}

// Returns number between 0 (inclusive) and 1.0 (exclusive),
// just like Math.random().
function random()
{
    m_z = (36969 * (m_z & 65535) + (m_z >> 16)) & mask;
    m_w = (18000 * (m_w & 65535) + (m_w >> 16)) & mask;
    var result = ((m_z << 16) + (m_w & 65535)) >>> 0;
    result /= 4294967296;
    return result;
}

Math.seed = function(s) {
    return function() {
        s = Math.sin(s) * 10000; return s - Math.floor(s);
    };
};

// usage:
var random1 = Math.seed(42);
var random2 = Math.seed(random1());
Math.random = Math.seed(random2());

Math.seed = function(s) {
    var mask = 0xffffffff;
    var m_w  = (123456789 + s) & mask;
    var m_z  = (987654321 - s) & mask;

    return function() {
      m_z = (36969 * (m_z & 65535) + (m_z >>> 16)) & mask;
      m_w = (18000 * (m_w & 65535) + (m_w >>> 16)) & mask;

      var result = ((m_z << 16) + (m_w & 65535)) >>> 0;
      result /= 4294967296;
      return result;
    }
}

var myRandomFunction = Math.seed(1234);
var randomNumber = myRandomFunction();