貝利-波爾溫-普勞夫公式

貝利-波爾溫-普勞夫公式（BBP 公式）提供一个計算圓周率 π的第 _ n _ 位二進位數的 spigot 算法（spigot algorithm）。 這个求和公式是佇一九九五年由西蒙 ・ 普勞夫提出的，並且用公佈這个公式的論文作者大衛 ・ 貝利（David H . Bailey）、 皮特 ・ 波爾溫（Peter Borwein）佮普勞夫的名號。佇論文發表進前，普勞夫已經將這个公式佇伊的網站頂懸咧公佈。這个公式是：

$ \ pi=\ sum _ { k=零 } ^ { \ infty } \ left [{ \ frac { 一 } { 十六 ^ { k } } } \ left ( { \ frac { 四 } { 八 k + 一 } }-{ \ frac { 二 } { 八 k + 四 } }-{ \ frac { 一 } { 八 k + 五 } }-{ \ frac { 一 } { 八 k + 六 } } \ right ) \ right] $

這个公式的發現講捌驚惶學界。百年來，求出 π 的第 _ n _ 小數而無共求出伊的前 _ n _ 糊一个捌予人認為是無可能的。

自從這件發現講以來，發現閣較濟的無理數常數的類似公式，𪜶攏有一个類似的形式：

$ \ alpha=\ sum _ { k=零 } ^ { \ infty } \ left [{ \ frac { 一 } { b ^ { k } } } { \ frac { p ( k ) } { q ( k ) } } \ right] $

其中 α 是目標捷數，_ p _ 和 _ q _ 是整係數多項式，_ b _ ≥ 二是整數的數制。

這種形式的公式予人稱做BBP 式公式（BBP-type formulas）。 由特定的 _ p _ , _ q _ 和 _ b _ 會當組合出一寡出名的常數。毋過到今猶未揣出一種系統的算法來揣合適的組合，爾知的公式多數是通過實驗數學會出的。

特例

一个已經著愛出真濟解的 BBP 式的特例是：

$ P ( s , b , m , A )=\ sum _ { k=零 } ^ { \ infty } \ left [{ \ frac { 一 } { b ^ { k } } } \ sum _ { j=一 } ^ { m } { \ frac { a _ { j } } { ( mk + j ) ^ { s } } } \ right] $

其中 _ s _ , _ b _ 和 _ m _ 是整數，$ A=( a _ { 一 } , a _ { 二 } , \ dots , a _ { m } ) $ 是一个整數向量。 使用 P 函數會當得著一寡解法的省略記法。

已經知的 BBP 式

佇咧 BBP 公式發現進前，就已經有一寡上簡單的此類公式闊為所知。𪜶使用 P 函數的省略記法如下：

$ { \ begin { aligned } \ ln { \ frac { 九 } { 十 } } &=-{ \ frac { 一 } { 十 } }-{ \ frac { 一 } { 兩百 } }-{ \ frac { 一 } { 三 \ 零 } }-{ \ frac { 一 } { 四十 \ 零 } }-{ \ frac { 一 } { 五百 \ 零 } }-\ cdots \ \ &=-\ sum _ { k=一 } ^ { \ infty } { \ frac { 一 } { 十 ^ { k } \ cdot k } }=-{ \ frac { 一 } { 十 } } \ sum _ { k=零 } ^ { \ infty } \ left [{ \ frac { 一 } { 十 ^ { k } } } \ left ( { \ frac { 一 } { k + 一 } } \ right ) \ right] \ \ &=-{ \ frac { 一 } { 十 } } P \ left ( 一 , 十 , 一 , ( 一 ) \ right ) \ end { aligned } } $

$ { \ begin { aligned } \ ln 二 &={ \ frac { 一 } { 二 } } + { \ frac { 一 } { 二 \ cdot 二 ^ { 二 } } } + { \ frac { 一 } { 三 \ cdot 二 ^ { 三 } } } + { \ frac { 一 } { 四 \ cdot 二 ^ { 四 } } } + { \ frac { 一 } { 五 \ cdot 二 ^ { 五 } } } + \ cdots \ \ &=\ sum _ { k=一 } ^ { \ infty } { \ frac { 一 } { 二 ^ { k } \ cdot k } }={ \ frac { 一 } { 二 } } \ sum _ { k=零 } ^ { \ infty } \ left [{ \ frac { 一 } { 二 ^ { k } } } \ left ( { \ frac { 一 } { k + 一 } } \ right ) \ right] \ \ &={ \ frac { 一 } { 二 } } P \ left ( 一 , 二 , 一 , ( 一 ) \ right ) \ end { aligned } } $

普勞夫嘛對這種形式的反正切函數的級數展開感興趣（P 猶閣記法會當泛化做 _ b _ 毋是整數的情形）:

$ { \ begin { aligned } \ arctan { \ frac { 一 } { b } } &={ \ frac { 一 } { b } }-{ \ frac { 一 } { b ^ { 三 } 三 } } + { \ frac { 一 } { b ^ { 五 } 五 } }-{ \ frac { 一 } { b ^ { 七 } 七 } } + { \ frac { 一 } { b ^ { 九 } 九 } } + \ cdots \ \ &=\ sum _ { k=一 } ^ { \ infty } \ left [{ \ frac { 一 } { b ^ { k } } } { \ frac { \ sin { \ frac { k \ pi } { 二 } } } { k } } \ right]={ \ frac { 一 } { b } } \ sum _ { k=零 } ^ { \ infty } \ left [{ \ frac { 一 } { b ^ { 四 k } } } \ left ( { \ frac { 一 } { 四 k + 一 } } + { \ frac { 影一 } { 四 k + 三 } } \ right ) \ right] \ \ &={ \ frac { 一 } { b } } P \ left ( 一 , b ^ { 四 } , 四 , ( 一 , 零 , 影一 , 零 ) \ right ) \ end { aligned } } $

走揣新的等式

使用的上述 P 函數，令 _ s =  一 _ , _ m  >   一 _ 會當出已知的 π 的上簡單公式。真濟已知的公式是令 b 是二抑三的冪，m 是二的冪抑是其他多因子的值，並令向量 A 等於零。佇咧算一寡類似的佮了後，這類發現引發了使用計算機搜揣類似線性組合的試看覓。搜查的程序為每一个參數，s , b , m 分別選擇一个定義域，然後求和檢查值，並且使用整數關係偵查算法（integer relation algorithm）， 譬如講赫拉曼 ・ 鋪古森（Helaman Ferguson）的 PSLQ 算法，來揣著一个向量 _ A _ 予遮的中間值會當加做伙得著一个出名的常數（_ A _ 嘛可能是零）。

π 的 BBP 公式

原始的 BBP π 求佮公式是在一九九五年由 Plouffe 使用 PSLQ 算法（integer relation algorithm）發現的。伊仝款會當由來講 _ P _ 函數表示：

$ { \ begin { aligned } \ pi &=\ sum _ { k=零 } ^ { \ infty } \ left [{ \ frac { 一 } { 十六 ^ { k } } } \ left ( { \ frac { 四 } { 八 k + 一 } }-{ \ frac { 二 } { 八 k + 四 } }-{ \ frac { 一 } { 八 k + 五 } }-{ \ frac { 一 } { 八 k + 六 } } \ right ) \ right] \ \ &=P \ left ( 一 , 十六 , 八 , ( 四 , 零 , 零 , 鋪二 , 影一 , 影一 , 零 , 零 ) \ right ) \ end { aligned } } $

這个公式嘛會當使用下述兩个外項式的商來表示：

$ \ pi=\ sum _ { k=零 } ^ { \ infty } \ left [{ \ frac { 一 } { 十六 ^ { k } } } \ left ( { \ frac { 百二 k ^ { 二 } + 百五一 k + 四十七 } { 五百十二 k ^ { 四 } + 一千空二十四 k ^ { 三 } + 七仔十二 k ^ { 二 } + 一百九十四 k + 十五 } } \ right ) \ right] $

這个等式會當用一个較簡單的方式嚴格證明。

π 的 BBP 位抽取算法

這个公式共出一个抽取 π 的十六進位數值的算法。首先咱需要將這个公式化做：

$ \ pi=四 \ sum _ { k=零 } ^ { \ infty } { \ frac { 一 } { ( 十六 ^ { k } ) ( 八 k + 一 ) } } 鋪二 \ sum _ { k=零 } ^ { \ infty } { \ frac { 一 } { ( 十六 ^ { k } ) ( 八 k + 四 ) } }-\ sum _ { k=零 } ^ { \ infty } { \ frac { 一 } { ( 十六 ^ { k } ) ( 八 k + 五 ) } }-\ sum _ { k=零 } ^ { \ infty } { \ frac { 一 } { ( 十六 ^ { k } ) ( 八 k + 六 ) } } $。

來使用此公式實現一个 spigot 算法進前，閣需要做一寡改動。阮想欲揣出 π 佇咧十六進位下的第 _ n _ 位，所以起先咱需要將這个該佮序列拆做 n 進前佮 n 了後兩个分。對前述公式的第一項來講，

$ \ sum _ { k=零 } ^ { \ infty } { \ frac { 一 } { ( 十六 ^ { k } ) ( 八 k + 一 ) } }=\ sum _ { k=零 } ^ { n } { \ frac { 一 } { ( 十六 ^ { k } ) ( 八 k + 一 ) } } + \ sum _ { k=n + 一 } ^ { \ infty } { \ frac { 一 } { ( 十六 ^ { k } ) ( 八 k + 一 ) } } $。

咱閣將等式兩爿乘以十六 _ n _，使得小數點拄好落佇第 _ n _ 位。

$ \ sum _ { k=零 } ^ { \ infty } { \ frac { 十六 ^ { n-k } } { 八 k + 一 } }=\ sum _ { k=零 } ^ { n } { \ frac { 十六 ^ { n-k } } { 八 k + 一 } } + \ sum _ { k=n + 一 } ^ { \ infty } { \ frac { 十六 ^ { n-k } } { 八 k + 一 } } $。

因為咱關心的是小數部份，咱觀察這个式的兩項，會發現干焦有第一項會當出現整數部份，啊若第二項袂出現整數部份。因為第二項中 _ k _ > _ n _ , 第二項中間的分子一定是小於分母。對此咱需要一个使用一種技巧來對第一項中除去整數。彼就是愛 mod  八 _ k _ +   一。所以原式第一項的小數部份的公式就是：

$ \ sum _ { k=零 } ^ { n } { \ frac { 十六 ^ { n-k } \ mod 八 k + 一 } { 八 k + 一 } } + \ sum _ { k=n + 一 } ^ { \ infty } { \ frac { 十六 ^ { n-k } } { 八 k + 一 } } $。

注意模運算將保證干焦小數部份的和會予人保留落來。想欲快速有效的計算十六 _ n _-_ k _  mod  八 _ k _ +   一 , 會當使用模冪運算（Modular exponentiation）。

對公式的以餘項使用仝款的處理辦法，並且根據原式求出最後的結果。

$ 四 \ Sigma _ { 一 } 鋪二 \ Sigma _ { 二 }-\ Sigma _ { 三 }-\ Sigma _ { 四 } . \ , \ ! $

因為干焦小數部份是準確，想欲抽的特定的小數位愛去掉最終結果的整數部份，乘十六來跳過這一个十六進位（理論講佇咧精度的範圍內底這位下跤的幾个小數位猶原是準確的）。

這个過程類似長整數乘法（long multiplication）， 但是干焦需要對一寡中央列來進行求和。因為有的進位無予計算，啊若阮干焦關心上重要的位，計算機通常對足濟的（三十二抑是六十四）同時進行計算。存在一種極低的可能性，就是當極端情形出來，伊可能會將一个小數（譬如講一）加到九百九十九點九千九百九十九點九千九百九十九點九千九百九十九上，然後這个錯誤會影響上重要的彼个位。但是佇終計算結果的時陣，這號情況若欲發生，彼嘛會是顯而易見的。

這个算法予人廣為應用並有足濟種程序實現。

使用 BBP 算法計算 π 的好處

這个算法無需要自定義一種包含數千甚至數億數字的「大數」數據類型。這種算法計算第 _ n _ 位而不需計算前 _ n _ ma一位，所以會當採用簡單有效的數據類型。

這種算法對計算 π 的第 _ n _ 位（抑是第 _ n _ 位的附近幾位）上緊上有效的，毋過使用大數據類型來計算 π 的前 _ n _ 位的算法猶原比這个算法閣較緊。

推廣

D . J . 布拉德赫斯欲特提出一種 BBP 算法的泛化形式。這種形式會當用佇接近線性的時間佮對數空間之下求足濟其他的常數。譬如講卡塔蘭常數，$ \ pi ^ { 三 } $，$ \ log ^ { 三 } 二 $，阿培內常數 $ \ zeta ( 三 ) $（其中 $ \ zeta ( x ) $ 是黎曼 ζ 函數）， $ \ pi ^ { 四 } $，$ \ log ^ { 四 } 二 $，$ \ log ^ { 五 } 二 $，$ \ zeta ( 五 ) $，猶閣有足濟 $ \ pi $ 和 $ \ log 二 $ 的無仝冪次。遮的結果主要是使用多重對數函數（polylogarithm ladder）得著的。

參考資料

==外部連結==* Cook’s Class Contains Pi