Soru C / C ++ 'da normal dağılımı takip eden rasgele sayılar üret


C / C ++ 'da normal bir dağılımı takiben rasgele sayıları kolayca nasıl oluşturabileceğimi bilen var mı?

http://www.mathworks.com/access/helpdesk/help/toolbox/stats/normrnd.html

Boost'u kullanmak istemiyorum.

Knuth'un bunun hakkında konuştuğunu biliyorum ama şu anda kitaplarını elimde bulundurmadım.


102
2018-02-24 11:16


Menşei


Birinin diğerinin kopyası stackoverflow.com/questions/75677/... ve stackoverflow.com/questions/1109446/... - dmckee


Cevaplar:


Box-Muller dönüşüm yaygın olarak kullanılan şeydir. Bu, normal dağılıma sahip değerler üretir.

http://en.wikipedia.org/wiki/Normal_distribution#Generating_values_from_normal_distribution

http://en.wikipedia.org/wiki/Box_Muller_transform

Matematik kolaydır. İki eşit sayı üretirsiniz ve bunlardan normal olarak dağıtılmış iki sayı elde edersiniz. Biri döndür, bir sonraki rasgele sayının talebi için diğerini sakla.


82
2018-02-24 11:24



Hıza ihtiyacınız varsa, o zaman polar yöntem daha hızlıdır. Ve Ziggurat algoritması daha da fazla (yazmak için çok daha karmaşık olsa da). - Joey
Ziggurat'ın bir uygulamasını burada buldu people.sc.fsu.edu/~jburkardt/c_src/ziggurat/ziggurat.html Oldukça dolu. - dwbrito
Not, C ++ 11 ekliyor std::normal_distribution matematiksel ayrıntılara girmeden tam olarak ne istediğini yapar.
std :: normal_distribution tüm platformlarda tutarlı olacak şekilde garanti edilmez. Şimdi testleri yapıyorum ve MSVC, örneğin Clang'dan farklı bir değerler seti sunuyor. C ++ 11 motorları aynı dizileri üretiyor gibi görünüyor (aynı tohum verildiğinde), fakat C ++ 11 dağılımları farklı platformlarda farklı algoritmalar kullanılarak uygulanıyor gibi görünüyor. - Arno Duvenhage


DÜZENLE: 12 Ağustos 2011'den beri C ++ 11 doğrudan teklifler std::normal_distribution, bugün gitme şeklim.

İşte orijinal cevap:

İşte artan karmaşıklıkla sipariş edilen bazı çözümler.

  1. 12 üniforma numarası ekle 0 ila 1 ve 6 çıkarır. Bu, normal bir değişkenin ortalama ve standart sapmasıyla eşleşir. Açık bir dezavantaj, gerçek bir normal dağılımın aksine, aralığın +/- 6 ile sınırlı olmasıdır.

  2. Box-Muller dönüşümü - Yukarıda listelenmiştir ve uygulanması nispeten basittir. Bununla birlikte, çok kesin örneklere ihtiyacınız varsa, bazı Tekdüzen jeneratörler ile birleştirilmiş Box-Muller dönüşümünün, Neave Effect adlı bir anomaliden muzdarip olduğunu unutmayın.

    H. R. Neave, “Çarpıcı eşdeğer pseudorandom sayısı jeneratörü ile Box-Muller dönüşümünü kullanmak üzerine,” Applied Statistics, 22, 92-97, 1973

  3. İçin en iyi hassasiyet öneririm üniforma çizim ve ters kümülatif normal dağılımı uygulama normal olarak dağıtılmış değişkenlere ulaşmak için. Ters kümülatif normal dağılım için çok iyi bir algoritma bulabilirsiniz.

https://web.archive.org/web/20151030215612/http://home.online.no/~pjacklam/notes/invnorm/

umarım yardımcı olur

Peter


40
2018-02-24 12:29



Herhangi bir şansa göre, Neave etkisindeki pdf'ye başka bir linkiniz var mı? veya orijinal dergi makalesi referansı? teşekkür ederim - pyCthon
@stonybrooknick Özgün referans eklendi. Cool not: referans bulmak için "kutu muller neave" googling ederken, bu çok stackoverflow soru ilk sonuç sayfasında geldi! - Peter G.
evet, bazı küçük topluluklar ve çıkar grupları dışında iyi bilinen her şey değil - pyCthon
@Peter G. Neden kimse cevabınızı reddeder? - Muhtemelen aynı kişi benim de yorumumu da verdi, ki ben de iyiyim, ama cevabın çok iyi olduğunu düşündüm. Eğer SO yapılan oylar gerçek bir yorum yapmaya zorlanırsa iyi olur .. Eski konuların en büyük notlarının şüpheli ve güncel olduğunu sanmıyorum. - Pete855217
"0-1'den 12 tekdüze sayı ekleyin ve 6'yı çıkarın." - Bu değişkenin dağılımı normal dağılıma sahip olacak mı? Türetme ile bir bağlantı sağlayabilir misiniz, çünkü türetme merkezi limit teoremi sırasında, n -> + inf çok fazla varsayım gerektirir. - bruziuz


Hızlı ve kolay bir yöntem, bir dizi eşit dağıtılmış rasgele sayıları toplamak ve ortalamalarını almaktır. Bakın Merkezi Limit Teoremi Bunun neden işe yaradığının tam bir açıklaması için.


26
2018-02-24 11:20



+1 Çok ilginç bir yaklaşım. Daha küçük gruplar için normal olarak dağıtılmış alt topluluklar vermek doğrulandı mı? - Morlock
@Morlock Bir Gauss dağılımına yaklaştığınız ortalama örnek sayısı artar. Uygulamanızın dağıtımın doğruluğu için kesin gereksinimleri varsa, Box-Muller gibi daha titiz bir şey kullanmaktan daha iyi olabilirsiniz, ancak birçok uygulama için, örn. Ses uygulamaları için beyaz gürültü oluştururken, çok az sayıda ortalama örnekle (örn. 16) uzaklaşabilirsiniz. - Paul R
Ayrıca, belirli bir varyans miktarını elde etmek için bunu nasıl parametrize ediyorsunuz, standart sapması 1 olan ortalama 10 mu demek istiyorsunuz? - Morlock
@Morlock: Belirli bir ortalama ve SD almak için alttaki örnekleri doğru şekilde ölçeklendirirsiniz. Genel olarak, alttaki örnekler u, 0 ile 1 arasında eşittirler. Onları -1'den + 1'e eşit hale getirin (2 hesapla) u 1). Ardından istenen ortalama sapmayı ekleyebilir ve istenen standart sapmayı elde etmek için çarpabilirsiniz. - S.Lott
@Morlock Eğer PRNG'nizi -1.0 ila +1.0 aralığındaki rastgele sayıları verecek şekilde ölçeklendirirseniz, yeterince büyük bir ortalama aldığınız zaman ortalama 0,0 değerini ve 0.5'lik bir varyansı elde edersiniz. İhtiyacınız ne olursa olsun ortalama ve varyansı elde etmek için giriş sayılarını veya çıktı ortalamasını doğrusal olarak kaydırıp ölçekleyebilirsiniz. - Paul R


Ben oluşturdum Normalde dağıtılmış rasgele sayı üretimi için C ++ açık kaynak projesi.

Dahil olmak üzere çeşitli algoritmaları karşılaştırır

  • Merkezi limit teoremi yöntemi
  • Box-Muller dönüşümü
  • Marsaglia polar metodu
  • Ziggurat algoritması
  • Ters dönüşüm örnekleme yöntemi.
  • cpp11random C ++ 11 kullanır std::normal_distribution ile std::minstd_rand (aslında Box-Muller dönüşümüdür).

Tek hassasiyetin sonuçları (float) iMac Corei5-3330S@2.70GHz, clang 6.1, 64-bit sürümü:

normaldistf

Doğruluk için program, numunelerin ortalama, standart sapmasını, çarpıklığını ve basıklığını doğrular. CLT yönteminin 4, 8 ya da 16 tekdüze sayılarla toplanması, diğer yöntemlerle iyi kurtoza sahip olmadığı bulunmuştur.

Ziggurat algoritması diğerlerinden daha iyi bir performansa sahiptir. Ancak, masa arama ve dallara ihtiyaç duyduğu için SIMD paralellik için uygun değildir. SSE2 / AVX komut setli Box-Muller, ziggurat algoritmasının SIMD olmayan versiyonundan çok daha hızlıdır (x1.79, x2.99).

Bu nedenle, SIMD komut setleriyle mimarlık için Box-Muller'ı kullanmanızı öneriyorum ve aksi takdirde ziggurat olabilir.


Not; benchmark, eşit dağılımlı rasgele sayılar oluşturmak için en basit bir LCG PRNG kullanır. Bu yüzden bazı uygulamalar için yeterli olmayabilir. Ancak performans karşılaştırması adil olmalı çünkü tüm uygulamalar aynı PRNG'yi kullanıyor, bu yüzden kıyaslama esas olarak dönüşümün performansını test ediyor.


19
2017-07-10 05:21



“Ama performans karşılaştırması adil olmalı çünkü tüm uygulamalar aynı PRNG kullanıyor.” Her ne kadar MP, çıktı başına bir girdi RN kullanıyorsa, CLT çok daha fazlasını kullanıyor, vb ... böylece tekdüze bir rastgele # mesele üretme zamanı. - greggo


İşte bazı referanslara dayanan bir C ++ örneği. Bu hızlı ve kirli, destek kütüphanesini yeniden icat etmemek ve kullanmaktan daha iyi olursunuz.

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

Sonuçları incelemek ve gerçek bir normal dağılıma ne kadar iyi yaklaştığını görmek için QQ grafiğini kullanabilirsiniz (örneklerinizi 1.sx'e göre sıralayın), sıraları x toplam sayısının oranlarına çevirin, yani kaç tane örnek var, z değerleri elde edin ve bunları çizin. Yukarı doğru düz bir çizgi istenen sonuçtur).


13
2018-05-18 00:04



SampleNormalManual () nedir? - solvingPuzzles
@solvingPuzzles - özür dilerim, kodu düzeltti. Bu özyinelemeli bir çağrı. - Pete855217
Bu, bazı nadir olaylarda çarpışmaya mahkumdur (patronunuza yapılan uygulamayı çantanıza takar mı?). Bu, tekrarlama kullanılmadan bir döngü kullanılarak uygulanmalıdır. Yöntem yabancı görünmüyor. Kaynak nedir / nasıl denir? - the swine
Box-Muller bir java uygulamasından kopyalandı. Söylediğim gibi, hızlı ve kirli, düzeltmek için çekinmeyin. - Pete855217
FWIW, birçok derleyici, o belirli özyinelemeyi 'fonksiyonun tepesine atlamak' haline getirebilecektir. Soru, buna güvenmek isteyip istemediğiniz sorusudur. Ayrıca,> 10 iterasyon alabilme olasılığı 4.8 milyonda 1'dir. p (> 20) bunun karesi, vb. - greggo


kullanım std::tr1::normal_distribution.

Std :: tr1 ad alanı, desteğin bir parçası değildir. Bu, C ++ Teknik Rapor 1'den kütüphane eklemelerini içeren ad ve Microsoft'tan derlenmiş olan derleyiciler ve gcc'de, bağımsız olarak desteklenmektedir.


12
2018-02-24 11:23



TR1 artmıyor. - Joe Gauterin
TR1 de standart değildir.
O standart sormadı, o 'değil güçlendirmek' istedi. - Joe Gauterin
TR1 standartlaştırılmıştır. - Ben Voigt


Modern C ++ derleyicisindeki örnekleri bu şekilde oluşturursunuz.

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

11
2017-08-15 22:02



generator gerçekten tohumlanmalıdır. - Walter
Her zaman tohumlanır. Varsayılan bir tohum var. - Petter


Kullanabilirsiniz GSL. Bazı tam örnekler verilir nasıl kullanılacağını göstermek için.


4
2017-11-05 12:57