×

Computing Fibonacci numbers (and similarly defined functions) in log time. (English) Zbl 0452.68052


MSC:

68Q25 Analysis of algorithms and problem complexity
11-04 Software, source code, etc. for problems pertaining to number theory
11B37 Recurrences
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Shortt, J., An iterative algorithm to calculate Fibonacci numbers in O(log n) arithmetic operations, Information Processing Lett., 7, 299-303 (1978) · Zbl 0385.65057
[2] Wilson, T. C.; Shortt, J., An O(log n) algorithm for computing general order-k Fibonacci numbers, Information Processing Lett., 10, 68-75 (1980) · Zbl 0437.10004
[3] Dijkstra, E. W., A Discipline of Programming (1976), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0286.00013
[4] Conway, R.; Gries, D., An Introduction to Programming (1979), Winthrop: Winthrop Cambridge
[5] Hildebrand, F. B., Methods of Applied Mathematics (1952), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0049.09103
[6] Brualdi, R. B., Introductory Combinatorics (1977), North-Holland: North-Holland Amsterdam · Zbl 0385.05001
[7] Korn, G. A.; Korn, T. M., Mathematical Handbook for Scientists and Engineers (1961), McGraw-Hill: McGraw-Hill New York · Zbl 0121.00103
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.