A fast algorithm for computing large Fibonacci numbers

被引：13
作者：
Takahashi, D [1 ]
机构：
[1] Saitama Univ, Dept Informat & Comp Sci, Urawa, Saitama 3388570, Japan
来源：
INFORMATION PROCESSING LETTERS | 2000年 / 75卷 / 06期
关键词：
program derivation; Fibonacci numbers;
D O I：
10.1016/S0020-0190(00)00112-5
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We present a fast algorithm for computing large Fibonacci numbers. It is known that the product of Lucas numbers algorithm uses the fewest bit operations to compute the Fibonacci number F-n. We show that the number of bit operations in the conventional product of Lucas numbers algorithm can be reduced by replacing multiplication with the square operation. (C) 2000 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：243 / 246
页数：4
相关论文
共 12 条
[1]   AN ALGORITHM FOR MACHINE CALCULATION OF COMPLEX FOURIER SERIES [J].
COOLEY, JW ;
TUKEY, JW .
MATHEMATICS OF COMPUTATION, 1965, 19 (90) :297-&
[2]   COMPUTING FIBONACCI NUMBERS QUICKLY [J].
CULL, P ;
HOLLOWAY, JL .
INFORMATION PROCESSING LETTERS, 1989, 32 (03) :143-149
[3]   COMPUTING SUMS OF ORDER-K FIBONACCI NUMBERS IN LOG TIME [J].
ER, MC .
INFORMATION PROCESSING LETTERS, 1983, 17 (01) :1-5
[4]   A FAST ALGORITHM FOR COMPUTING ORDER-K FIBONACCI NUMBERS [J].
ER, MC .
COMPUTER JOURNAL, 1983, 26 (03) :224-227
[5]   COMPUTING FIBONACCI NUMBERS (AND SIMILARLY DEFINED FUNCTIONS) IN LOG TIME [J].
GRIES, D ;
LEVIN, G .
INFORMATION PROCESSING LETTERS, 1980, 11 (02) :68-69
[6]  
Knuth D. E., ART COMPUTER PROGRAM, V2
[7]   A PRESENTATION OF THE FIBONACCI ALGORITHM [J].
MARTIN, AJ ;
REM, M .
INFORMATION PROCESSING LETTERS, 1984, 19 (02) :67-68
[8]   DERIVATION OF AN O(K2LOG N) ALGORITHM FOR COMPUTING ORDER-K FIBONACCI NUMBERS FROM THE O(K3LOG N) MATRIX MULTIPLICATION METHOD [J].
PETTOROSSI, A .
INFORMATION PROCESSING LETTERS, 1980, 11 (4-5) :172-179
[9]   ON THE NUMBER OF ARITHMETICAL OPERATIONS FOR FINDING FIBONACCI NUMBERS [J].
PROTASI, M ;
TALAMO, M .
THEORETICAL COMPUTER SCIENCE, 1989, 64 (01) :119-124
[10]   FAST MULTIPLICATION OF LARGE NUMBERS [J].
SCHONHAGE, A ;
STRASSEN, V .
COMPUTING, 1971, 7 (3-4) :281-+
12