절차적인 내용을위한 빠른 의사 난수 생성기

Question

나는 각 숫자를 생성하기 전에 씨앗이 주어 졌을 때 빠르게 작동하는 의사 난수 생성기를 찾고 있습니다. 지금까지 본 대부분의 생성자는 시드를 한 번 설정 한 다음 긴 숫자 시퀀스를 생성한다고 가정합니다. 지금까지 필자가 보아 왔던 것과 비슷한 것은 Perlin Noise 뿐이지 만 유사한 "너무"부드러운 데이터를 생성합니다. 유사한 입력의 경우 유사한 결과를 생성하는 경향이 있습니다.

과 같이 보일 것입니다 발전기의 선언 :

int RandomNumber1(int seed); 

또는 :

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

나는 그것의 입력을 해싱에 의해 RandomNumber3을 구현하기 위해 가능한 한 좋은 RandomNumber1이 충분해야한다 가진 생각을 결과를 RandomNumber1에 전달하지만 일부 구현에서는 독립적 인 입력을 사용할 수 있도록 2 차 프로토 타입을 작성했습니다.

이 생성기의 용도는 그리드에 나무를 놓고 숲을 생성하고 각 위치에 대해 임의의 나무 종과 임의의 공간 오프셋을 결정하는 등의 절차 콘텐츠 생성기에 사용하는 것입니다.

발생기는 렌더링 과정에서 절차 내용이 실시간으로 대량 생성되므로 매우 효율적이어야합니다 (500 CPU주기 미만).

Answer 1

PRNG가 아닌 해시 함수를 요청하는 것처럼 보입니다. 인터넷 검색 '빠른 해시 함수'는 몇 가지 유망한 결과를 산출합니다.

For example

:

는

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; 
} 

편집 : 그래, 일부 해시 함수는 확실히 다른 사람보다 더 적합 보인다.

목적에 따라, 함수를 눈으로보고 입력의 단일 비트 변경이 많은 출력 비트로 전파되는지 확인하는 것으로 충분해야합니다.

Answer 2

그래, 당신은 PRNG가 아닌 빠른 정수 해시 알고리즘을 찾고 있습니다.

이 page에는 몇 가지 알고리즘이 있습니다. 정확한 검색 조건을 더 많이 알게 될 것입니다.

편집 : 원본 페이지가 삭제되었습니다. 라이브 버전은 found on GitHub 일 수 있습니다.

Answer 3

std::tr1::ranlux3 또는 표준 C++ 라이브러리에 TR1 추가의 일부인 다른 난수 생성기를 참조하십시오. 나는 초기에 mt19937을 제안했지만, 매우 빨라야한다는 메모를 보았습니다. TR1은 Microsoft VC++과 GCC에서 사용할 수 있어야하며 더 많은 컴파일러를 지원하는 부스트 라이브러리에서도 찾을 수 있습니다.boost documentation 각색

예 :

#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 난수 발생기는 다른 난수 생성기를 시드 할 수있다. 더 높은 품질의 결과가 필요하면 mt19937의 출력 (더 느리지 만 품질은 더 높음)을 더 빠른 생성기 인 minstd_rand 또는 randlux3에 공급하는 것이 좋습니다.

Answer 4

메모리가 실제로 문제가 아니며 속도가 가장 중요한 경우 난수 배열을 미리 작성하고 런타임시이를 반복 할 수 있습니다. 예를 들어이 같은 자신의 파일의 같은 별도의 프로그램을 10 만 난수를 생성 및 저장이

부호 INT randarray []

다음 해당 파일을에 포함 = {1,2,3, ...} 당신의 컴파일 할 때 런타임에 난수 함수는 해당 배열에서 숫자를 가져와야 만 끝까지 히트 할 때 다시 시작 지점으로 되돌아 가면됩니다.

Answer 5

다음은 George Marsaglia가 개발 한 작은 난수 생성기입니다. 그는 현장 전문가이기 때문에 발전기가 좋은 통계적 특성을 가지고 있음을 확신 할 수 있습니다.

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

여기에서 u와 v는 부호없는 int입니다. 0이 아닌 값으로 초기화하십시오. 난수를 생성 할 때마다 u와 v를 어딘가에 저장하십시오. 위의 서명과 일치하는 함수에서 이것을 감쌀 수 있습니다. (int는 부호가 없다는 것을 제외하고)

Answer 6

자바 임의 번호 라이브러리에서 다음 코드를 사용합니다. 나는 또한 절차적인 내용을 생성하기 위해 이것을 사용한다.

/** 
* 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; 
}