태그 보관물: algorithms

algorithms

원유 난수 생성기로 Pi를 사용할 수 있습니까? 의미하지만 (파이는 얼마나 오래

나는 최근 질문을 math.SE에서 보았습니다. 생각이났다 Pi를 원유 난수 생성기로 사용할 수 있습니까? 나는 결과가 잘 알려져 있음을 의미하지만 (파이는 얼마나 오래 계산 되었습니까?)하지만 한 번에 1 자리를 취할 때 Pi는 매우 무작위 인 것처럼 보입니다.

이것은 전혀 의미가 있습니까?



답변

pi의 이진 값을 얻기 위해 http://www.befria.nu/elias/pi/binpi.html 을 파고 (십진수를 사용하지 않고 바이트로 변환하는 것이 더 쉽도록) ent를 통해 실행 바이트의 무작위 분포를 분석하기 위해 다음을 얻습니다.

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

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

4096 개의 표본에 대한 카이 제곱 분포는 253.00이며 임의로이 값의 52.36 %를 초과합니다.

데이터 바이트의 산술 평균값은 126.6736입니다 (127.5 = 임의).

Pi의 Monte Carlo 값은 3.120234604입니다 (오류 0.68 %).

직렬 상관 계수는 0.028195입니다 (총 상관 관계 = 0.0).

따라서 임의의 데이터에 pi를 사용하면 상당히 임의의 데이터를 얻을 수 있습니다. 잘 알려진 임의의 데이터임을 알 수 있습니다.


위의 의견에서 …

당신이하는 일에 따라 임의의 소수의 제곱근을 임의의 숫자 생성기로 사용할 수 있다고 생각합니다. 이들은 최소한 균등하게 분배 된 숫자를 가져야합니다. – Paxinum

그래서 나는 2의 제곱근을 이진수로 계산하여 같은 문제를 제거했습니다. Wolfram의 Iteration을 사용 하여 간단한 펄 스크립트를 작성했습니다.

#!/usr/bin/perl
use strict;
use Math::BigInt;

my $u = Math::BigInt->new("2");
my $v = Math::BigInt->new("0");
my $i = 0;

while(1) {
    my $unew;
    my $vnew;

    if($u->bcmp($v) != 1) { # $u <= $v
        $unew = $u->bmul(4);
        $vnew = $v->bmul(2);
    } else {
        $unew = ($u->bsub($v)->bsub(1))->bmul(4);
        $vnew = ($v->badd(2))->bmul(2);
    }

    $v = $vnew;
    $u = $unew;

    #print $i,"  ",$v,"\n";
    if($i++ > 10000) { last; }
}

open (BITS,"> bits.txt");
print BITS $v->as_bin();
close(BITS);

처음 10 개 일치하는 A095804에 대해 이것을 실행 하면 시퀀스가 ​​있다고 확신했습니다. 이진수가 첫 번째 숫자 다음에 배치 된 이진수로 쓰여질 때 값 v n 은 제곱근 2의 근사값을 나타냅니다.

이 이진 데이터에 대해 ent를 사용하면 다음이 생성됩니다.

Entropy = 7.840501 bits per byte.

Optimum compression would reduce the size
of this 1251 byte file by 1 percent.

Chi square distribution for 1251 samples is 277.84, and randomly
would exceed this value 15.58 percent of the times.

Arithmetic mean value of data bytes is 130.0616 (127.5 = random).
Monte Carlo value for Pi is 3.153846154 (error 0.39 percent).
Serial correlation coefficient is -0.045767 (totally uncorrelated = 0.0).

답변

음, 난수 생성기의 다른 속성 중에서도 아마도 일반 숫자가 되기를 원할 것 입니다. 그리고 당신의 질문에 영감을 준 math.SE 질문에 대한 몇 가지 대답은 현재 pi가 정상적인 것으로 여겨지지만 입증되지 않았다는 것을 지적합니다.


답변

이러한 생성기는 의사 번호 생성기, 즉 동일한 시드가 주어지면 결과는 항상 동일합니다. 대부분의 프레임 워크에서 표준 난수 생성기를 사용할 때 의사 난수와 동일한 문제가 있습니다.

자릿수 분포는 표준 난수 생성기 ¹와 매우 유사한 것으로 보이므로 π의 자릿수는 일반적인 난수 생성 시나리오에 사용할 수 있습니다.

문제는 알고리즘이 일반적인 난수 생성기와 비교할 때 아마도 매우 느릴 것이므로 실제로는 유용하지 않습니다.


¹ 나는 그것이 사실이라고 믿지만 증거가 없습니다. 많은 수의 숫자를 기준으로 비교하는 것이 흥미롭고 복잡하지 않습니다.


답변

파이 (또는 임의의 다른 시퀀스에 대한)의 자릿수 랜덤 성은 소위 ‘배터리 테스트’에 의해 테스트 될 수있다. 인기있는 배터리 테스트 중 하나는 George Marsaglia의 Diehard Battery Test 입니다. 또한 NIST 특별 출판물 800-22 에는 이러한 여러 테스트와 이러한 테스트를 백만 비트 이상에 대해 -lo 및 behold -pi를 포함한 여러 물리적 상수에 적용한 결과가 설명되어 있습니다. pi의 결과는 보고서의 부록 B에 나와 있으며 다음과 같습니다.

Statistical Test                            P-value
Frequency                                   0.578211
Block Frequency (m = 128)                   0.380615
Cusum-Forward                               0.628308
Cusum-Reverse                               0.663369
Runs                                        0.419268
Long Runs of Ones                           0.024390
Rank                                        0.083553
Spectral DFT                                0.010186
Non-overlapping Templates (m = 9, B = 000000001)          0.165757
Overlapping Templates (m = 9)               0.296897
Universal                                   0.669012
Approximate Entropy (m = 10)                0.361595
Random Excursions (x = +1)                  0.844143
Random Excursions Variant (x = -1)          0.760966
Linear Complexity (M = 500)                 0.255475
Serial (m = 16, 2m∇Ψ )                      0.143005

파이는 랜덤 시퀀스 생성기인가요? 위의 결과를 보거나 의미가 무엇인지 모를 경우 왼쪽 열 변수의 의미를 검색하고 필요에 맞는지 확인하십시오.


답변