著者

高橋 大介

出版者

一般社団法人情報処理学会

雑誌

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

巻号頁・発行日

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

参考文献数

9

---

本論文では,Fibonacci数を高速に計算する方法について述べる.Fibonacci数 $F_n$ を計算するには,Lucas数の積に基づくアルゴリズムが,最もビット演算量が少ないことが知られている.このアルゴリズムにおいて,多倍長数の乗算を多倍長数の自乗計算に置き換えることで,さらに演算量を減らすことができることを示す.We present a fast algorithm for computing Fibonacci numbers.It is known that the product of Lucas numbers algorithm usesthe fewest bit operations to compute the Fibonacci number $F_n$.We show that the number of bit operations in the conventional product ofLucas numbers algorithm can be reduced by replacingmultiple-precision multiplication with the multiple-precision square operation.