1.最近看到有學弟在說BBP算法，然後就寫一下這個東東。
2.BBP其實是三個人，然後這個算法是幹嘛的嘞，其實是快速的求某些無理數的第n為數字或者第n位以後的一串數字。比如求PI，log2,log3等等。下面來說明一下它是怎麼求PI的在16進制下的第n位數字的。（什麼，為什麼是16進制？，看完就明白了）
3.首先給出一個PI的級數求和公式：
（這玩意怎麼來的？emmmm，泰勒展一下就出來了吧，雖然我沒展）。
看一下HDU 6217，題意十分的直白，求PI的第n位數字。
我們知道，比如給你一個小數：1.23456789.現在求這個數的第4位小數，咋整？其實很簡單，你把小數點放在4和5之間，然後類型強制轉換一下，把整數去掉，再乘個10就是第4位小數。一般化一下，對于第n位小數，先把小數點移動到它的前邊，然後整數部分去掉，再乘個基底就是答案。這也就是BBP算法的核心了。那麼對于PI，我們首先把這個和式拆一下，拆成四個求和，然後對于每一個求和，考慮：
首先時兩邊同時乘16^d,這樣在16進制下，小數點就會後移動d-1位。然後将整個求和式子分為兩部分，前邊的部分就是d>k,後邊時d<k.當d<k時，這就是一個小數，對答案有貢獻，然後分子對分母取模，這也是直接計算小數部分，把整數部分全部去掉。這樣全部加起來就是小數部分，然後再*16，就是16進制下的答案。到這裡也解釋了為啥隻能求16進制下的數位。同理，如果求log2這個數的第n位，由于使用泰勒展開之後是2^k,是以隻能求二進制下的數位。emmm，基本上就是這些了。
最後附上HDU 6217的代碼:
#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
#define ll long long
ll qpow(ll a, ll b, ll mod)
{
ll res = 1;
while (b)
{
if (b & 1)res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
double BBP(int n, double a, double b)
{
double r = 0;
for (int k = 0; k <= n; k++) r += qpow(16, n - k, 8 * k + b) * 1.0 / (k * 8.0 + b);
return r * a;
}
double BBPformular(int n)
{
return BBP(n, 4, 1) + BBP(n, -2, 4) + BBP(n, -1, 5) + BBP(n, -1, 6);
}
int main() {
int t;
scanf("%d", &t);
for (int c = 1; c <= t; c++) {
int n;
scanf("%d", &n);
n--;
double r = BBPformular(n);
r = r - (ll)r;
if (r < 0)r += 1.0;
r *= 16;
int res = r;
printf("Case #%d: %d %c\n", c, n + 1, res > 9 ? res - 10 + 'A' : res + '0');
}
return 0;
}