| 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)
|
| 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)
|
