C/C++의 정규 분포에 따라 난수 생성

C/C++의 정규 분포에 따라 난수 생성

C 또는 C++의 정규 분포에 따라 난수를 쉽게 생성할 수 있는 방법은 무엇입니까?

Boost를 사용하고 싶지 않아요.

나는 Knuth가 이것에 대해 길게 말하는 것을 알지만, 나는 지금 그의 책을 가지고 있지 않다.

일반 RNG에서 가우스 분포 번호를 생성하는 방법은 여러 가지가 있습니다.

일반적으로 Box-Muller 변환이 사용됩니다.정규 분포를 사용하여 값을 올바르게 생성합니다.수학은 쉽다.두 개의 (균일한) 난수를 생성하고 공식을 적용하면 정규 분포 난수 두 개를 얻을 수 있습니다.하나는 반환하고 다른 하나는 랜덤 번호에 대한 다음 요청을 위해 저장합니다.

C++11

C++11은 제가 오늘 선택한 방법입니다.

C 이전 C++

다음은 복잡도 증가순으로 몇 가지 해결 방법입니다.

1. 0부터 1까지 12개의 균일한 난수를 더하고 6을 빼세요.이 값은 정규 변수의 평균 및 표준 편차와 일치합니다.분명한 단점은 실제 정규 분포와 달리 범위가 ±6으로 제한된다는 것입니다.

2. Box-Muller 변환입니다.이는 위에 열거되어 있으며 비교적 구현이 간단합니다.그러나 매우 정밀한 샘플이 필요한 경우에는 일부 균일한 생성기와 결합된 Box-Muller 변환에서 Neave¹ Effect라는 이상 현상이 발생한다는 점에 유의하십시오.

3. 최상의 정밀도를 위해 균일도를 그리고 역 누적 정규 분포를 적용하여 정규 분포 변동에 도달하는 것이 좋습니다.다음은 역 누적 정규 분포에 대한 매우 좋은 알고리즘입니다.

^{1. H. R. Neave, "승수 합동 의사난수 생성기에 의한 박스-뮬러 변환 사용에 대하여", Applied Statistics, 22, 92-97, 1973}

정규 분포 난수 생성 벤치마크를 위한 C++ 오픈 소스 프로젝트를 만들었습니다.

다음과 같은 몇 가지 알고리즘을 비교합니다.

• 중심 한계 정리법
• 박스-뮬러 변환
• 마르사글리아 극지방법
• 지그라트 알고리즘
• 역변환 샘플링 방법.
• cpp11random C++11 을 합니다.std::normal_distributionstd::minstd_rand박스물러

(단정도float ( 6.1, ) : (iMac Corei5-3330S@2.70GHz, clang 6.1, 64비트) :

정확성을 위해 프로그램은 표본의 평균, 표준 편차, 왜도 및 첨도를 검증합니다.4, 8 또는 16개의 균일한 숫자를 합산하는 CLT 방법은 다른 방법보다 첨도가 좋지 않은 것으로 밝혀졌다.

Ziggurat 알고리즘은 다른 알고리즘보다 성능이 우수합니다.그러나 테이블 룩업과 브랜치가 필요하기 때문에 SIMD 병렬 처리에는 적합하지 않습니다.SSE2/AVX 명령 세트를 갖춘 Box-Muller는 SIMD 이외의 버전의 ziggurat 알고리즘보다 훨씬 빠릅니다(x1.79, x2.99).

따라서 SIMD 명령 집합이 있는 아키텍처에 Box-Muller를 사용하는 것이 좋으며, 그렇지 않으면 ziggurat이 될 수 있습니다.

---

추신: 벤치마크는 균일한 분포 난수를 생성하기 위해 가장 단순한 LCG PRNG를 사용합니다.따라서 일부 애플리케이션에서는 충분하지 않을 수 있습니다.그러나 성능 비교는 모든 구현이 동일한 PRNG를 사용하기 때문에 벤치마크에서 주로 변환의 성능을 테스트하기 때문에 공정해야 합니다.

역 누적 정규 분포에는 다양한 알고리즘이 있습니다.양적 금융 분야에서 가장 인기 있는 것은 http://chasethedevil.github.io/post/monte-carlo-inverse-cumulative-normal-distribution/에서 테스트하고 있습니다.

Wichura의 AS241 알고리즘 이외에는 기계 정밀도, 신뢰성, 고속이라는 인센티브가 별로 없다고 생각합니다.병목 현상은 가우스 난수 생성에서는 거의 발생하지 않습니다.

여기에서는 Box-Müler를 옹호하는 답변이 가장 많습니다.Box-Müler는 결함이 있음을 알고 있어야 합니다.https://www.sciencedirect.com/science/article/pii/S0895717710005935을 인용합니다.

문헌에서 Box-Muller는 주로 두 가지 이유로 약간 열등하다고 여겨지기도 한다.첫째, Box-Muller 방법을 불량 선형 합동 발생기의 숫자에 적용할 경우 변환된 숫자는 공간에 대한 커버리지가 매우 낮습니다.나선형 꼬리를 가진 변형된 숫자의 플롯은 많은 책에서 볼 수 있으며, 특히 리플리의 고전 책에서 볼 수 있습니다. 리플리는 아마도 이러한 관찰을 가장 먼저 했을 것입니다."

GSL을 사용할 수 있습니다.사용 방법을 설명하기 위한 완전한 예를 몇 가지 나타냅니다.

comp.lang.c FAQ 목록에는 가우스 분포를 사용하여 난수를 쉽게 생성할 수 있는 세 가지 방법이 나와 있습니다.

http://c-faq.com/lib/gaussian.html 에서 보실 수 있습니다.

다음은 몇 가지 참조를 바탕으로 한 C++의 예입니다.이것은 빠르고 지저분합니다.부스트 라이브러리를 재발명하여 사용하지 않는 것이 좋습니다.

#include "math.h" // for RAND, and rand
double sampleNormal() {
    double u = ((double) rand() / (RAND_MAX)) * 2 - 1;
    double v = ((double) rand() / (RAND_MAX)) * 2 - 1;
    double r = u * u + v * v;
    if (r == 0 || r > 1) return sampleNormal();
    double c = sqrt(-2 * log(r) / r);
    return u * c;
}

Q-Q 그림을 사용하여 결과를 조사하고 실제 정규 분포에 얼마나 근접하는지 확인할 수 있습니다(표본 1..x, 순위를 x의 총 카운트의 비율로 변환).몇 개의 표본을 추출하고 z 값을 플롯합니다.상향 직선이 바람직한 결과입니다).

Box-Muller 구현:

#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
using namespace std;
 // return a uniformly distributed random number
double RandomGenerator()
{
  return ( (double)(rand()) + 1. )/( (double)(RAND_MAX) + 1. );
}
 // return a normally distributed random number
double normalRandom()
{
  double y1=RandomGenerator();
  double y2=RandomGenerator();
  return cos(2*3.14*y2)*sqrt(-2.*log(y1));
}

int main(){
double sigma = 82.;
double Mi = 40.;
  for(int i=0;i<100;i++){
double x = normalRandom()*sigma+Mi;
    cout << " x = " << x << endl;
  }
  return 0;
}

이것이 최신 C++ 컴파일러에서 샘플을 생성하는 방법입니다.

#include <random>
...
std::mt19937 generator;
double mean = 0.0;
double stddev  = 1.0;
std::normal_distribution<double> normal(mean, stddev);
cerr << "Normal: " << normal(generator) << endl;

C++11 을 사용하고 있는 경우는, 다음을 사용할 수 있습니다.

#include <random>

std::default_random_engine generator;
std::normal_distribution<double> distribution(/*mean=*/0.0, /*stddev=*/1.0);

double randomNumber = distribution(generator);

난수 엔진의 출력을 변환하는 데 사용할 수 있는 다른 많은 분포가 있습니다.

std::tr1::normal_distribution.

std::tr1 네임스페이스는 부스트의 일부가 아닙니다.이 네임스페이스는 C++ Technical Report 1에서 추가된 라이브러리를 포함하고 있으며 부스트와는 별도로 최신 Microsoft 컴파일러 및 gcc에서 사용할 수 있습니다.

빠르고 쉬운 방법은 균등하게 분포된 난수들의 수를 합산하여 평균을 구하는 것입니다.이것이 작동하는 이유에 대한 자세한 설명은 중앙 한계 정리를 참조하십시오.

컴퓨터는 결정론적인 장치이다.계산에는 무작위성이 없습니다.게다가 CPU의 산술 디바이스는, 몇개의 유한한 정수 집합(유한 필드에서의 평가 실행)과 유한한 실수 집합의 합계를 평가할 수 있습니다.또한 비트 연산도 수행했습니다.수학은 [0.0, 1.0]과 같은 더 많은 수의 점으로 처리됩니다.

컨트롤러로 컴퓨터 내부의 몇 개의 와이어를 들을 수 있지만, 균일한 분배가 될까요?몰라.그러나 이 신호가 엄청난 양의 독립 랜덤 변수 값이 누적된 결과라고 가정하면 근사 정규 분포 랜덤 변수를 받게 됩니다(확률 이론에서 증명됨).

의사 랜덤 생성기라는 알고리즘이 있습니다.내가 느꼈듯이 의사 랜덤 발생기의 목적은 무작위성을 모방하는 것이다.그리고 좋은 것의 기준은 - 경험적 분포가 이론적인 의미(어떤 의미에서는 점적으로 균일하고 L2)로 수렴됨 - 랜덤 생성기로부터 받는 값은 종속되지 않는 것으로 보입니다.물론 '진정한 관점'에서는 그렇지 않지만, 우리는 그것이 사실이라고 가정합니다.

일반적인 방법 중 하나로 균일한 분포를 사용하여 12개의 i.r.v를 합할 수 있습니다.그러나 푸리에 변환, Taylor 시리즈를 지원하는 파생 중심 한계 정리 동안 솔직히 말해서, n->+inf 가정이 여러 번 필요합니다.그래서 예를 들어 이론적인 - 나는 개인적으로 사람들이 균일한 분포로 12 I.R.V.의 합계를 어떻게 수행하는지 이해할 수 없다.

나는 대학 때 확률론을 가지고 있었다.그리고 특히 나에게 그것은 단지 수학 문제일 뿐이다.대학에서 본 모델은 다음과 같습니다.

---

double generateUniform(double a, double b)
{
  return uniformGen.generateReal(a, b);
}

double generateRelei(double sigma)
{
  return sigma * sqrt(-2 * log(1.0 - uniformGen.generateReal(0.0, 1.0 -kEps)));
}
double generateNorm(double m, double sigma)
{
  double y2 = generateUniform(0.0, 2 * kPi);
  double y1 = generateRelei(1.0);
  double x1 = y1 * cos(y2);
  return sigma*x1 + m;
}

---

그런 식으로 하는 것은 하나의 예에 불과하기 때문에, 그것을 실행하는 다른 방법이 존재한다고 생각합니다.

그것이 옳다는 증명은 Krishchenco Alexander Petrovich ISBN 5-7038-2485-0의 이 책 "모스크바, BMSTU, 2004: XII 확률론, 예 6.12, 페이지 246-247"에서 찾을 수 있다.

아쉽게도 이 책의 영문 번역 여부는 모르겠습니다.

http://www.cplusplus.com/reference/random/normal_distribution/ 를 참조해 주세요.정규 분포를 생성하는 가장 간단한 방법입니다.

http://www.mathworks.com/help/stats/normal-distribution.html에서 제공되는 PDF의 정의에 따라 다음과 같은 내용을 생각해 냈습니다.

const double DBL_EPS_COMP = 1 - DBL_EPSILON; // DBL_EPSILON is defined in <limits.h>.
inline double RandU() {
    return DBL_EPSILON + ((double) rand()/RAND_MAX);
}
inline double RandN2(double mu, double sigma) {
    return mu + (rand()%2 ? -1.0 : 1.0)*sigma*pow(-log(DBL_EPS_COMP*RandU()), 0.5);
}
inline double RandN() {
    return RandN2(0, 1.0);
}

최선의 방법은 아닐 수도 있지만, 매우 간단합니다.

1) 가우스 난수를 생성할 수 있는 그래픽 직감적인 방법은 몬테카를로법과 유사한 방법을 사용하는 것입니다.C의 의사 난수 발생기를 사용하여 가우스 곡선 주위의 상자에 랜덤 포인트를 생성합니다.분포 방정식을 사용하여 해당 점이 가우스 분포의 내부 또는 아래에 있는지 계산할 수 있습니다.해당 점이 가우스 분포 내에 있으면 가우스 난수를 점의 x 값으로 얻은 것입니다.

이 방법은 완벽하지 않습니다. 왜냐하면 기술적으로 가우스 곡선은 무한대로 진행되며 x차원에서 무한대에 근접하는 상자를 만들 수 없기 때문입니다.하지만 과시안 곡선은 y차원에서 매우 빠르게 0에 접근하기 때문에 나는 그것에 대해 걱정하지 않을 것이다.C에서 변수 크기의 제약 조건이 정확도에 대한 제한 요인이 될 수 있습니다.

2) 다른 방법은 독립 랜덤 변수가 추가되면 정규 분포를 형성한다는 중앙 한계 정리를 사용하는 것입니다.이 정리에 유의하여 독립 랜덤 변수를 다량 추가하여 가우스 난수를 근사할 수 있습니다.

이러한 방법이 가장 실용적이지는 않지만, 이는 기존 라이브러리를 사용하지 않을 때 예상할 수 있는 방법입니다.이 대답은 미적분이나 통계학 경험이 거의 없거나 전혀 없는 사람으로부터 나온다는 것을 기억하십시오.

몬테카를로 방법 이것을 하는 가장 직관적인 방법은 몬테카를로 방법을 사용하는 것이다.적절한 범위 -X, +X를 취합니다. X 값이 클수록 더 정확한 정규 분포를 얻을 수 있지만 수렴하는 데 더 오래 걸립니다. a.-X에서 X 사이의 난수 z를 선택합니다. b. 확률:N(z, mean, variance)은은 은은 은은 은은 은은 은그렇지 않으면 드롭하고 스텝(a)으로 돌아갑니다.

내가 뭘 찾았는지 봐

이 라이브러리는 Ziggurat 알고리즘을 사용합니다.

언급URL : https://stackoverflow.com/questions/2325472/generate-random-numbers-following-a-normal-distribution-in-c-c