I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Talk:Fibonacci matrix-exponentiation

From Rosetta Code

Clarify Task[edit]

The task to implement fib(n) using matrix multiplication is a great task. However, given that fib(2^32) has hundreds of million of digits, the task is unachievable. Many implementations use fibMod for the last digits, and another methodology for the first digits. Recommend a selecting smaller values of n, and sticking to the task of fib(n) using matrix multiplication, not fibMod or other implementations.

--DavidFashion (talk) 00:04, 13 February 2020 (UTC)

I will add fib(2^16) in the main task. If only fib(2^64) is not calculated, the task is considered accomplished.

The goal of the task is to show that the iterative method is slow to calculate large fibonacci numbers. Smaller values like fib(2^16) is easily found using the iterative method.

I think fib(2^32) is reachable using matrix exponentiation and even if it remains slow, Julia solution shows a faster method using Lucas sequence.

I confess fib(2^64) seems unreachable using matrix exponentiation. Nevertheless it allowed to see some creative solution like the Sidef solution using fibmod.