Ziggurat algorithm (original) (raw)
La méthode ziggourat est un algorithme pour engendrer des nombres aléatoires de loi non uniforme. Il s'agit d'une méthode de rejet et peut être choisie pour simuler une variable aléatoire ayant une densité strictement monotone. Cette méthode peut aussi être appliquée à des lois symétriques unimodales telles que la loi normale en choisissant un point sur l'une des moitiés et en choisissant le côté aléatoirement. Cette méthode a été développée par George Marsaglia et Wai Wan Tang.
| Property | Value |
|---|---|
| dbo:abstract | La méthode ziggourat est un algorithme pour engendrer des nombres aléatoires de loi non uniforme. Il s'agit d'une méthode de rejet et peut être choisie pour simuler une variable aléatoire ayant une densité strictement monotone. Cette méthode peut aussi être appliquée à des lois symétriques unimodales telles que la loi normale en choisissant un point sur l'une des moitiés et en choisissant le côté aléatoirement. Cette méthode a été développée par George Marsaglia et Wai Wan Tang. Comme la plupart des algorithmes de ce type, il suppose que l'on dispose d'un générateur de nombres aléatoires de loi uniforme, en général un générateur pseudo-aléatoire. Dans la plupart des cas, comme la loi normale ou la loi exponentielle, l'algorithme consiste à engendrer un nombre flottant, un index aléatoire de table, faire une recherche dans une table, une multiplication et une comparaison. Cet algorithme est considérablement plus rapide que les autres méthodes pour simuler des variables aléatoires de loi normale, comme la méthode de Box-Muller qui requièrent de calculer une racine carrée ou un logarithme. D'un autre côté, cette méthode est plus complexe à mettre en œuvre et nécessite des tables précalculées, de sorte qu'il vaut mieux l'utiliser lorsque l'on a besoin de nombres aléatoires en grande quantité. Le nom de cette méthode provient du fait qu'elle couvre la densité de la loi avec des segments rectangulaires empilés par ordre de taille décroissant, ce qui ressemble donc à une ziggourat. (fr) L'algoritmo ziggurat è un algoritmo di rejection sampling utilizzato per il campionamento numerico pseudo-casuale. È stato sviluppato negli anni '60 da George Marsaglia e viene utilizzato per generare valori da una distribuzione di probabilità decrescente monotona partendo da una sorgente di numeri casuali uniformemente distribuiti (solitamente un generatore di numeri pseudo-casuali) e da una tabella precalcolata. Può anche essere applicato a distribuzioni unimodali simmetriche, come la distribuzione normale. L'algoritmo ziggurat è più veloce rispetto ad altri metodi di generazione di numeri casuali normalmente distribuiti, come il metodo polare di Marsaglia e la trasformazione di Box-Muller. Tuttavia, poiché questo algoritmo è anche più complesso da implementare, solitamente è utilizzato solo a fronte di una grande richiesta di numeri pseudo-casuali. Il termine ziggurat risale all'articolo scritto da Marsaglia e Wai Wan Tsang nel 2000, che lo chiamarono così per via del modo in cui distribuisce la probabilità, ovvero tramite segmenti rettangolari impilati in ordine decrescente, assomigliando così a una ziggurat. L'algoritmo Ziggurat utilizzato per generare valori campione con una distribuzione normale (solo i valori positivi sono mostrati per semplicità). I punti rosa sono inizialmente numeri casuali distribuiti uniformemente. La funzione di distribuzione desiderata viene prima segmentata in aree uguali "A". Uno strato i è selezionato a caso dalla fonte uniforme a sinistra. Quindi un valore casuale dalla sorgente viene moltiplicato per la larghezza del livello scelto e il risultato viene testato x volte per vedere in quale regione della fenditura cade. I possibili risultati sono: 1) (sinistra, regione nera) il campione è chiaramente sotto la curva e viene passato direttamente all'output, 2) (a destra, regione a strisce verticali) il valore del campione può trovarsi sotto la curva e deve essere ulteriormente testato. In tal caso, viene generato un valore y casuale all'interno del livello scelto e confrontato con f (x) . Se inferiore, il punto è sotto la curva e viene emesso il valore x . In caso contrario, il punto scelto x viene rifiutato e l'algoritmo viene riavviato dall'inizio. (it) The ziggurat algorithm is an algorithm for pseudo-random number sampling. Belonging to the class of rejection sampling algorithms, it relies on an underlying source of uniformly-distributed random numbers, typically from a pseudo-random number generator, as well as precomputed tables. The algorithm is used to generate values from a monotonically decreasing probability distribution. It can also be applied to symmetric unimodal distributions, such as the normal distribution, by choosing a value from one half of the distribution and then randomly choosing which half the value is considered to have been drawn from. It was developed by George Marsaglia and others in the 1960s. A typical value produced by the algorithm only requires the generation of one random floating-point value and one random table index, followed by one table lookup, one multiply operation and one comparison. Sometimes (2.5% of the time, in the case of a normal or exponential distribution when using typical table sizes) more computations are required. Nevertheless, the algorithm is computationally much faster than the two most commonly used methods of generating normally distributed random numbers, the Marsaglia polar method and the Box–Muller transform, which require at least one logarithm and one square root calculation for each pair of generated values. However, since the ziggurat algorithm is more complex to implement it is best used when large quantities of random numbers are required. The term ziggurat algorithm dates from Marsaglia's paper with Wai Wan Tsang in 2000; it is so named because it is conceptually based on covering the probability distribution with rectangular segments stacked in decreasing order of size, resulting in a figure that resembles a ziggurat. (en) Алгоритм «Зиккурат» (англ. Ziggurat Algorithm, Ziggurat Method) — это алгоритм выборки псевдослучайных чисел. Будучи представителем класса алгоритмов выборки с отклонением, он в работе своей опирается на источник равномерно распределённых случайных чисел — обыкновенно это генератор псевдослучайных чисел, либо же предварительно вычисленная таблица. Алгоритм используется для генерации значений на основе монотонно убывающего вероятностного распределения. Также может быть применён по отношению к симметричному унимодальному распределению, такому как нормальное, с помощью выбора значений из одной его половины, а затем, при необходимости, перехода к симметричному значению с помощью операции арифметического отрицания. Одним из авторов алгоритма, разработанного в 1960-е, является . В простейшем случае для вычисления значения, возвращаемого алгоритмом, требуется только генерация одного числа с плавающей точкой и одного случайного табличного индекса, за которой следует один табличный поиск, одна операция умножения и одно сравнение. Иногда (в гораздо меньшем количестве случаев) требуются более сложные вычисления. Тем не менее, данный алгоритм гораздо быстрее с вычислительной точки зрения, чем два наиболее часто используемых метода генерации нормально распределённых случайных чисел: и преобразования Бокса — Мюллера, где требуется вычисление по меньшей мере одного логарифма и одного квадратного корня для каждой пары генерируемых значений. Однако, так как алгоритм «Зиккурат» более сложен в реализации, наиболее часто он используется в случаях, где требуется большое количество случайных чисел. Сам термин «алгоритм „Зиккурат“» (Ziggurat Algorithm) фигурирует в совместной работе Марсальи и Ваи Ван Тсанга 2000 года и назван так потому, что концептуально основан на покрытии распределения вероятностей прямоугольными сегментами, сложенными друг на друге в порядке уменьшения размера (если рассматривать снизу вверх), что приводит к появлению фигуры, напоминающей зиккурат. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Ziggurat_method.gif?width=300 |
| dbo:wikiPageExternalLink | http://www.ee.cooper.edu/~nummey/ersa2009.pdf https://au.mathworks.com/company/newsletters/articles/normal-behavior.html http://www.doc.ic.ac.uk/~wl/papers/07/csur07dt.pdf https://blogs.mathworks.com/cleve/2015/05/18/the-ziggurat-random-normal-generator/ http://heliosphan.org/zigguratalgorithm/zigguratalgorithm.html https://www.jstatsoft.org/article/downloadSuppFile/v005i08/rnorrexp.c http://www.doornik.com/research/ziggurat.pdf https://apps.dtic.mil/sti/citations/AD0423993 https://web.archive.org/web/20140910003249/http:/www.dtic.mil/docs/citations/AD0423993 http://www.jstatsoft.org/v05/i08/paper |
| dbo:wikiPageID | 7093060 (xsd:integer) |
| dbo:wikiPageLength | 17519 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1102322020 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Probability_distribution dbr:Pseudo-random_number_sampling dbr:Root-finding_algorithm dbr:Monotonic_function dbr:Sanity_test dbr:Bisection_method dbr:Defense_Technical_Information_Center dbr:Algorithm dbc:Statistical_algorithms dbr:Unimodal_distribution dbr:Inline_function dbr:George_Marsaglia dbr:Box–Muller_transform dbc:Non-uniform_random_numbers dbr:Marsaglia_polar_method dbr:MATLAB dbr:Ziggurat dbr:Error_function dbr:Exponential_distribution dbr:Normal_distribution dbr:Normalizing_constant dbr:Numerical_integration dbr:Gaussian_distribution dbr:Recursion dbr:Rejection_sampling dbc:Pseudorandom_number_generators dbr:Symmetric_function dbr:IEEE_754 dbr:Round-off_error dbr:Pseudo-random_number_generator dbr:File:Ziggurat_method.gif |
| dbp:wikiPageUsesTemplate | dbt:Cite_techreport dbt:Citation_needed dbt:Cite_arXiv dbt:Cite_conference dbt:Cite_document dbt:Cite_journal dbt:Short_description dbt:Sqrt |
| dcterms:subject | dbc:Statistical_algorithms dbc:Non-uniform_random_numbers dbc:Pseudorandom_number_generators |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:WikicatNon-uniformRandomNumbers yago:WikicatStatisticalAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Amount105107765 yago:Attribute100024264 yago:Event100029378 yago:Magnitude105090441 yago:Number105121418 yago:Procedure101023820 yago:Property104916342 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | La méthode ziggourat est un algorithme pour engendrer des nombres aléatoires de loi non uniforme. Il s'agit d'une méthode de rejet et peut être choisie pour simuler une variable aléatoire ayant une densité strictement monotone. Cette méthode peut aussi être appliquée à des lois symétriques unimodales telles que la loi normale en choisissant un point sur l'une des moitiés et en choisissant le côté aléatoirement. Cette méthode a été développée par George Marsaglia et Wai Wan Tang. (fr) The ziggurat algorithm is an algorithm for pseudo-random number sampling. Belonging to the class of rejection sampling algorithms, it relies on an underlying source of uniformly-distributed random numbers, typically from a pseudo-random number generator, as well as precomputed tables. The algorithm is used to generate values from a monotonically decreasing probability distribution. It can also be applied to symmetric unimodal distributions, such as the normal distribution, by choosing a value from one half of the distribution and then randomly choosing which half the value is considered to have been drawn from. It was developed by George Marsaglia and others in the 1960s. (en) L'algoritmo ziggurat è un algoritmo di rejection sampling utilizzato per il campionamento numerico pseudo-casuale. È stato sviluppato negli anni '60 da George Marsaglia e viene utilizzato per generare valori da una distribuzione di probabilità decrescente monotona partendo da una sorgente di numeri casuali uniformemente distribuiti (solitamente un generatore di numeri pseudo-casuali) e da una tabella precalcolata. Può anche essere applicato a distribuzioni unimodali simmetriche, come la distribuzione normale. (it) Алгоритм «Зиккурат» (англ. Ziggurat Algorithm, Ziggurat Method) — это алгоритм выборки псевдослучайных чисел. Будучи представителем класса алгоритмов выборки с отклонением, он в работе своей опирается на источник равномерно распределённых случайных чисел — обыкновенно это генератор псевдослучайных чисел, либо же предварительно вычисленная таблица. Алгоритм используется для генерации значений на основе монотонно убывающего вероятностного распределения. Также может быть применён по отношению к симметричному унимодальному распределению, такому как нормальное, с помощью выбора значений из одной его половины, а затем, при необходимости, перехода к симметричному значению с помощью операции арифметического отрицания. Одним из авторов алгоритма, разработанного в 1960-е, является . (ru) |
| rdfs:label | Méthode ziggourat (fr) Algoritmo ziggurat (it) Алгоритм Зиккурат (ru) Ziggurat algorithm (en) |
| owl:sameAs | freebase:Ziggurat algorithm yago-res:Ziggurat algorithm wikidata:Ziggurat algorithm dbpedia-fa:Ziggurat algorithm dbpedia-fr:Ziggurat algorithm dbpedia-he:Ziggurat algorithm dbpedia-it:Ziggurat algorithm dbpedia-ru:Ziggurat algorithm https://global.dbpedia.org/id/2gi1F |
| prov:wasDerivedFrom | wikipedia-en:Ziggurat_algorithm?oldid=1102322020&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Ziggurat_method.gif |
| foaf:isPrimaryTopicOf | wikipedia-en:Ziggurat_algorithm |
| is dbo:wikiPageDisambiguates of | dbr:Ziggurat_(disambiguation) |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Inverse_transform_sampling dbr:List_of_numerical_analysis_topics dbr:Truncated_normal_distribution dbr:George_Marsaglia dbr:Box–Muller_transform dbr:Additive_process dbr:Normal_distribution dbr:Pseudorandom_number_generator dbr:Rejection_sampling dbr:Ziggurat_(disambiguation) dbr:List_of_statistics_articles dbr:Non-uniform_random_variate_generation |
| is foaf:primaryTopic of | wikipedia-en:Ziggurat_algorithm |
