Derivation of an O(k^ 2 n) algorithm for computing order-k Fibonacci numbers from the O(k^ 3 n) matrix multiplication method

DOI10.1016/0020-0190(80)90045-9zbMATH Open0509.68032OpenAlexW2013785943MaRDI QIDQ1838293FDOQ1838293

Authors: Alberto Pettorossi 

Publication date: 1980

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

Full work available at URL: https://doi.org/10.1016/0020-0190(80)90045-9

zbMATH Keywords

matrix multiplicationFibonacci numberslinear recurrence relationsiterative and recursive algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Recurrences (11B37)

Cites Work

• Title not available (Why is that?)
• A Transformation System for Developing Recursive Programs
• An O(log n) algorithm for computing general order-k Fibonacci numbers
• Deriving very efficient algorithms for evaluating linear recurrence relations using the program transformation technique

Cited In (7)

• Horner's rule and the computation of linear recurrences
• An O(k²log(n/k)) Algorithm for Computing Generalized Order-k Fibonacci Numbers with Linear Space
• A Formal Derivation of an 0(log n) Algorithm for Computing Fibonacci Numbers
• A fast algorithm for computing large Fibonacci numbers
• On the computing of the generalized order-\(k\) Pell numbers in log time
• Computing sums of order-k Fibonacci numbers in log time
• Fast computation of solutions of linear difference equations by Er's rule

This page was built for publication: 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

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