절차 내용을위한 빠른 의사 랜덤 번호 생성기

StackOverflow https://stackoverflow.com/questions/167735

  •  03-07-2019
  •  | 
  •  

문제

나는 각 숫자를 생성하기 전에 씨앗이 주어질 때 빨리 작동하도록 전문화되는 의사 임의의 랜덤 숫자 생성기를 찾고 있습니다. 지금까지 본 대부분의 생성기는 씨앗을 한 번 설정 한 다음 긴 숫자를 생성한다고 가정합니다. 내가 지금까지 본 것과 다소 비슷한 것처럼 보이는 유일한 것은 Perlin Noise이지만, 비슷한 입력에 대해서는 비슷한 결과를 얻는 경향이 있습니다.

발전기의 선언은 다음과 같은 것처럼 보일 것입니다.

int RandomNumber1(int seed);

또는:

int RandomNumber3(int seedX, int seedY, int seedZ);

입력을 해시하고 결과를 RandomNumber1로 전달하여 RandomNumber3을 구현할 수 있기 때문에 RandomNumber1이 양호하다고 생각하지만 일부 구현이 독립적 인 입력을 사용할 수있는 경우 2nd 프로토 타입을 작성했습니다.

이 발전기의 의도 된 용도는 그리드에 나무를 배치하고 각 위치에 대한 임의의 나무 종과 임의의 공간 오프셋을 결정하여 숲을 생성하는 것과 같은 절차 컨텐츠 생성기에 사용하는 것입니다.

절차 컨텐츠는 렌더링 중에 실시간으로 대량으로 생성되기 때문에 발전기는 매우 효율적이어야합니다 (500 CPU 사이클 미만).

도움이 되었습니까?

해결책

PRNG보다는 해시 기능을 요구하는 것 같습니다. 인터넷 검색 '빠른 해시 기능'은 몇 가지 유망한 결과를 얻습니다.

예를 들어:

uint32_t hash( uint32_t a)
    a = (a ^ 61) ^ (a >> 16);
    a = a + (a << 3);
    a = a ^ (a >> 4);
    a = a * 0x27d4eb2d;
    a = a ^ (a >> 15);
    return a;
}

편집하다: 그렇습니다. 일부 해시 기능은 다른 해시 기능보다 확실히 더 적합 해 보입니다.

귀하의 목적을 위해, 눈부심을 안구하고 입력의 단일 비트 변경이 많은 출력 비트로 전파되는지 확인하기에 충분해야합니다.

다른 팁

네, PRNG가 아닌 빠른 정수 해시 알고리즘을 찾고 있습니다.

이것 페이지 몇 가지 알고리즘이 있습니다. 이제 올바른 검색어를 알 수 있습니다.

편집하다: 원래 페이지가 제거되었으며 라이브 버전은 Github에서 발견되었습니다.

다음은 George Marsaglia가 개발 한 작은 랜덤 숫자 생성기입니다. 그는 분야의 전문가이므로 발전기에 통계적 특성이 우수하다고 확신 할 수 있습니다.

v = 36969*(v & 65535) + (v >> 16);
u = 18000*(u & 65535) + (u >> 16);
return (v << 16) + u;

여기서 u와 v는 서명되지 않은 int입니다. 0이 아닌 값으로 초기화하십시오. 임의의 숫자를 생성 할 때마다 U와 V를 어딘가에 저장하십시오. 위의 서명과 일치하도록 함수로 이것을 랩핑 할 수 있습니다 (ints가 서명되지 않은 경우를 제외하고).

보다 std::tr1::ranlux3, 표준 C ++ 라이브러리에 TR1 추가의 일부인 다른 랜덤 번호 생성기. 초기 MT19937을 제안했지만 매우 빠르야한다는 메모를 보았습니다. TR1을 사용할 수 있어야합니다 Microsoft VC ++ 그리고 GCC, 그리고 더 많은 컴파일러를 지원하는 Boost 라이브러리에서도 찾을 수 있습니다.

예제로 수정 된 예 문서를 높이십시오: 

#include <random>
#include <iostream>
#include <iterator>
#include <functional>
#include <algorithm>
#include <ctime>
using namespace std;
using namespace std::tr1;
int main(){
    random_device trueRand;
    ranlux3 rng(trueRand);  // produces randomness out of thin air
                            // see pseudo-random number generators
    uniform_int<> six(1,6); // distribution that maps to 1..6
                            // see random number distributions
    variate_generator<ranlux3&, uniform_int<> >
           die(rng, six);   // glues randomness with mapping

    // simulate rolling a die
    generate_n( ostream_iterator<int>(cout, " "), 10, ref(die));
}

예제 출력 :

2 4 4 2 4 5 4 3 6 2

모든 TR1 Random Number Generator는 시드 할 수 있습니다 다른 랜덤 번호 생성기. 더 높은 품질의 결과가 필요한 경우, MT19937의 출력 (느리지 만 품질이 높음)을 MINSTD_RAND 또는 RANDLUX3에 공급하는 것을 고려하십시오.

메모리가 실제로 문제가되지 않고 속도가 가장 중요하다면 많은 임의의 랜덤 배열을 사전 제작하고 런타임에 반복 할 수 있습니다. 예를 들어, 별도의 프로그램에 100,000 랜덤 숫자를 생성하고 자신의 파일과 같은 파일로 저장하십시오.

서명되지 않은 int randarray [] = {1,2,3, ....}

그런 다음 해당 파일을 컴파일에 포함시키고 런타임에 임의 번호 함수는 해당 배열에서 숫자를 가져 와서 끝을 누르면 시작으로 다시 루프하면됩니다.

나는 Java Random Number 라이브러리에서 다음 코드를 사용합니다. 이것은 나에게 잘 작동했습니다. 또한 절차 컨텐츠를 생성하는 데 이것을 사용합니다.

/**
 * State for random number generation
 */
private static volatile long state=xorShift64(System.nanoTime()|0xCAFEBABE);

/**
 * Gets a long random value
 * @return Random long value based on static state
 */
public static long nextLong() {
    long a=state;
    state = xorShift64(a);
    return a;
}

/**
 * XORShift algorithm - credit to George Marsaglia!
 * @param a initial state
 * @return new state
 */
public static final long xorShift64(long a) {
    a ^= (a << 21);
    a ^= (a >>> 35);
    a ^= (a << 4);
    return a;
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top