著者

高橋 大介

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.41, no.6, pp.1918-1921, 2000-06-15

---

本論文では,Fibonacci数を高速に計算する方法について述べる.Fibonacci数 $F_n$ を計算するには,Lucas数の積に基づくアルゴリズムが,最もビット演算量が少ないことが知られている.このアルゴリズムにおいて,多倍長数の乗算を多倍長数の自乗計算に置き換えることで,さらに演算量を減らすことができることを示す.