円周率.jp - BBP系公式このページでは BBP の公式と呼ばれる公式やそれに類した公式を紹介する。 BBP の公式は 16 進数 (2 進数) 表記での $n$ 桁数目を $O(n)$ で求められる方式として知られる。 $\pi$ 全体を計算するという観点で見る場合、 単純な実装で考えると $O(n^2)$ で求めることができるが、 Binary Splitting 法や DRM 法を適用すれば $O(n(\log n)^3)$ で計算することもできる。 BBPの公式 \[ \pi = \sum_{n=0}^{\infty} \frac{1}{16^n}\left(\frac{4}{8n+1} - \frac{2}{8n+4} - \frac{1}{8n+5} - \frac{1}{8n+6}\right) \] これが1995年9月19日[JB02]に発見された "BBP の公式" と呼ばれる公式である。 発見
