인수 종속 PRNG

Question

기능에 관심이 있어요 rand(x, y, seed) 다음 속성을 사용하여 인수를 기반으로 (의사) 난수를 반환합니다.

1. 반환되는 값은 3개의 인수에 따라 달라져야 합니다. ~ 아니다 횟수에 따라 달라집니다 rand 지금까지 불려왔습니다.예를 들어 다음 호출을 다음 순서로 가정합니다.

   rand(0, 0, 123) = 1
   rand(0, 1, 123) = 2
   rand(0, 2, 123) = 3
   

   그런 다음 전화 rand 동일한 인수를 사용하지만 순서가 다르면 동일한 값을 얻어야 합니다.예를 들어:

   rand(0, 1, 123) = 2
   rand(0, 2, 123) = 3
   rand(0, 0, 123) = 1
   

2. 이 함수는 상품의 일반적인 속성을 가져야 합니다(괜찮습니다. 별로 멋진 것은 필요하지 않습니다). PRNG:큰 기간, 균일한 분포 등부호 있는 int에 맞는 양의 정수를 반환하는 것은 괜찮습니다.원한다면 더 높아질 수도 있습니다.

3. 이 숫자가 행렬을 생성하는 데 사용된다고 가정합니다.그런 다음 시드를 변경하면 생성된 행렬이 다른 시드에서 생성된 행렬과 최대한 다르게 보이도록 해야 합니다.이는 가능한 한 많은 수의 시드에 대해 발생해야 합니다.나는 행렬이 반복되는 것을 원하지 않습니다.

도움이 된다면 내 시드는 항상 밀리초 단위의 유닉스 타임스탬프가 될 것입니다(어쨌든 더 쉽게 만들 수 있다면 초 단위일 수도 있습니다).모든 인수는 32비트 부호 있는 정수까지 가능하지만 함수 내에서 64비트 값으로 작업하는 것은 문제가 되지 않습니다.

어떤 기능을 사용할 수 있나요?

내가 생각한 것 :

펄린 노이즈 내가 원하는 것 중 일부를 수행하는 것 같지만 PRNG, 특히 배포 측면에서 실제로 얼마나 적합한지 모르겠습니다.또한 그것이 얼마나 효율적인지는 잘 모르겠습니다. (x, y) 매개변수는 다소 무작위적이므로 모든 매개변수에 대해 미리 계산할 수는 없습니다.

또한 다음 기능도 살펴보았습니다.

p = 1400328593
rand(x, y, seed) = (x * x * seed + y * seed * seed + seed * x * y + seed) mod p
                 = (seed * (x * x + y * seed + x * y + 1)) mod p

이것 것 같다 충분히 좋은 숫자를 생성합니다.내 (매우 약한) 테스트에 따르면 분산도 매우 잘 된 것 같습니다.하지만 기간을 테스트하는 것이 더 어렵습니다. 저는 그렇게 하지 않았습니다.

업데이트:

다음은 엔트 위의 기능에 대해 time(NULL) C에서 시드로 생성된 값 (x, y) in {0 ... 999} x {0 ... 999}:

엔트로피 = 바이트당 3.312850비트.

최적의 압축은이 9207076 바이트 파일의 크기를 58 % 줄입니다.

9207076 샘플의 카이 제곱 분포는 229710872.43이며, 무작위 로이 값이 0.01 % 미만을 초과합니다.

데이터 바이트의 산술 평균 값은 52.3354(127.5 = 무작위)입니다.PI의 Monte Carlo 값은 4.000000000 (오류 27.32 %)입니다.연속 상관 계수는 0.036131 (완전히 상관되지 않은 = 0.0)입니다.

이것이 실제로는 충분히 좋은가요(이론적으로 위의 테스트에서는 전혀 좋지 않은 것으로 나타났습니다), 아니면 제가 사용해야 하는 잘 알려진 것이 있습니까?

Answer 1

해시 함수를 원하는 것 같습니다.너무 비효율적이지 않다면 SHA1과 같은 안전한 것을 선택하십시오. 좋은 배포 특성이 보장되기 때문입니다.그렇지 않으면 FNV와 같은 일반적인 해시 함수를 사용할 수 있습니다.시드와 좌표를 입력 데이터로 사용하고 해시를 임의의 값으로 사용하기만 하면 됩니다.

Answer 2

당신은 사용해 볼 수 있습니다 블룸 블룸 슈브.계열의 n번째 값을 직접 계산할 수 있는 속성이 있는데, 이는 상황에 적합해 보입니다.p, q, x0의 세 가지 매개변수를 사용합니다.p와 q는 소수이고 x0은 p와 q 모두에 대해 상대적으로 소수입니다.따라서 인수 x와 y를 사용하여 x'번째 소수와 y'번째 소수를 찾을 수 있으며, 그런 다음 p와 q에 적합하고 세 번째 매개변수를 사용하여 x0에 적합한 값을 찾을 수 있습니다.이것은 약간 지루하고 Blum Blum Shub은 암호화 RNG이므로 느리지만 실제로 속도가 필요하지 않으면 작동하고 구현하기가 크게 어렵지 않습니다.

이를 수행하는 또 다른 방법은 다음과 같은 RNG를 취하는 것입니다. CMWC 생성기의 i번째 위치를 x + y^i + Seed^(2i)와 같은 것으로 채우고 생성기를 잠시 동안 실행한 다음(아마도 저장된 값의 수와 같은 횟수) 그것의 가치.

CMWC를 사용하려면 github에 있는 구현을 살펴보세요. 여기, 및 알려진 주기를 사용하여 생성기를 구성하기 위한 값 여기.