講演抄録/キーワード |
講演名 |
2020-06-11 15:15
ポアソン二項分布の計算アルゴリズムの比較について 坂田悠馬・○土肥 正・岡村寛之(広島大) R2020-4 |
抄録 |
(和) |
本稿ではポアソン二項分布の計算アルゴリズムに着目し, Hong (2013) によって提案されたポアソン二項分布の特性
関数に離散高速フーリエ変換を適用する手法と,ポアソン二項分布の再帰式を逐次的に解く手法を, 計算実行時間
の観点から比較する. また, Zhang ら (2018) によって考察された一般化ポアソン二項分布の計算手法に対しても同
様な計算実行時間の比較を行う. 結果として、逐次的解法に実装上の工夫を施すことにより, 従前まで計算爆発を
起こすとされていた単純な計算アルゴリズムの方が, 現在の汎用的な計算環境においては高速に計算実行できること
が示される. |
(英) |
In this article, we focus on the computation algorithms of Poisson binomial distributions, and compare the
well-known algorithm by Hong (2013), applying the discrete fast Fourier transform to the characteristic
function of the Poisson binomial distribution, with a simple recursive algorithm by solving an algebraic
equation, in terms of their computation time. We also consider a generalized Poisson binomial distribution
and compare our simple algorithm with the similar discrete fast Fourier transform algorithm by Zhang et
al. (2018). As a result, it is shown that the improvement on coding in the simple recursive algorithm,
which has been known to cause the computational explosion, leads to the much better computation performance |
キーワード |
(和) |
ポアソン二項分布 / 計算アルゴリズム / 計算性能 / 実装技術 / 再帰式 / 離散高速フーリエ変換 / / |
(英) |
Poisson binomial distributions / computation algorithms / computation performance / implementation technique / recursive formulae / discrete fast Fourier transform / / |
文献情報 |
信学技報, vol. 120, no. 60, R2020-4, pp. 21-26, 2020年6月. |
資料番号 |
R2020-4 |
発行日 |
2020-06-04 (R) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
R2020-4 |