A fast algorithm for computing large Fibonacci numbers

DOI10.1016/S0020-0190(00)00112-5MaRDI QIDQ294835zbMATHWikidataFDO

Authors Daisuke Takahashi

Publication date 16 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019000001125?np=y

zbMATH Keywords

Fibonacci numbersprogram derivation

Mathematics Subject Classification ID

Fibonacci and Lucas numbers and polynomials and generalizations (11B39) Mathematical problems of computer architecture (68M07) Calculation of integer sequences (11Y55)

Recommendations

• scientific article; zbMATH DE number 1807669
• scientific article; zbMATH DE number 977919
• On the number of arithmetical operations for finding Fibonacci numbers
• Improved algorithms for the calculation of Fibonacci numbers
• Fast Computation of Fibonacci Numbers and Their Sums

Cites work

• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• A Fast Algorithm for Computing Order-K Fibonacci Numbers
• A presentation of the Fibonacci algorithm
• An Algorithm for the Machine Calculation of Complex Fourier Series
• An \(O(\log n)\) algorithm for computing the \(n\)th element of the solution of a difference equation
• An interative program to calculate Fibonacci numbers in O(log n) arithmetic operations
• Computing Fibonacci numbers (and similarly defined functions) in log time
• Computing sums of order-k Fibonacci numbers in log time
• Derivation of an \(O(k^ 2\log n)\) algorithm for computing order-k Fibonacci numbers from the \(O(k^ 3\log n)\) matrix multiplication method
• Fast multiplication of large numbers
• On the number of arithmetical operations for finding Fibonacci numbers

Cited in

(17)

• 3-step Fibonacci series modulo \(m\).
• scientific article; zbMATH DE number 17620 (Why is no real title available?)
• Tumble, a fast simple iteration algorithm for Fibonacci
• Truncated Lucas sequence and its period
• On the period of Fibonacci sequences in nilpotent groups.
• An application of Fibonacci numbers in matrices.
• Fibonacci linear forms and parallel arithmetic algorithms for large numbers
• scientific article; zbMATH DE number 6034 (Why is no real title available?)
• scientific article; zbMATH DE number 1807669 (Why is no real title available?)
• The generalized order-\(k\) Fibonacci-Pell sequence by matrix methods
• A Formal Derivation of an 0(log n) Algorithm for Computing Fibonacci Numbers
• Fast Computation of Fibonacci Numbers and Their Sums
• On the computing of the generalized order-\(k\) Pell numbers in log time
• 3-step Fibonacci sequences in nilpotent groups.
• Improved algorithms for the calculation of Fibonacci numbers
• Applications of Fibonacci sequences in a finite nilpotent group.
• An application of Fibonacci sequences in groups

This page was built for publication: A fast algorithm for computing large Fibonacci numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294835)