fork download 
  1. # F(2n) = (F(n-1) + F(n+1)) * F(n)
  2. #       = (F(n-1) + F(n-1) + F(n)) * F(n)
  3. #       = (2F(n-1) + F(n)) * F(n)
  4.  
  5. # F(2n-1) = F(n-1)*F(n-1) + F(n)*F(n)
  6.  
  7. # this returns [F(n-1), F(n)]
  8. def fast_matrix_pow(n):
  9.     if n==0: return [1,0]
  10.     [a,b] = fast_matrix_pow(n>>1)
  11.     b2 = b*b
  12.     a,b = a*a+b2, (a<<1)*b+b2
  13.     if n%2 == 1:
  14.         return [b,a+b]
  15.     return [a,b]
  16.  
  17. def fast_fib(n):
  18.     return fast_matrix_pow(n)[1]
  19.  
  20. print ([[fast_fib(x) for x in range(71)] for _ in range(1000)][-1])
Success #stdin #stdout 0.52s 9984KB
comments (?)
stdin 
Standard input is empty
stdout 
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135]
https://ideone.com/EZz9zm
language:
Python 3 (python  3.9.5)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!