ベルヌーイ数をFPSで求める
はじめに
これを読んでね
やること
$ \frac{e^x - 1}{x}の逆数を計算して、各項に$ n!をかける
くわしく
ベルヌーイ数は $ \frac{x}{e^x - 1} の級数展開の係数として表される
$ \frac{x}{e^x - 1} = \sum_{n = 0}^\infty \frac{B_n}{n!} x^n
今、ベルヌーイ数の$ N項目までが欲しいとする
まず、$ \frac{e^x - 1}{x}をFPSで表すと$ F(x) = \sum_{n = 0}^N \frac{1}{(n+1)!} x^nとなる
次に、FPSで逆数を計算する($ O(N \log N))
$ F(x)^{-1} = \sum_{n = 0}^N \frac{B_n}{n!} x^n
あとは$ F(x)^{-1}の各項に$ n!をかければ$ B_nが出る!
実装