fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3.  
  4. using namespace std;
  5.  
  6. struct Matrix
  7. {
  8.     int m[2][2] = {{1,1},{1,0}};
  9. };
  10.  
  11. Matrix operator*(const Matrix& a, const Matrix& b)
  12. {
  13.     Matrix m;
  14.     m.m[0][0] = a.m[0][0]*b.m[0][0]+a.m[0][1]*b.m[1][0];
  15.     m.m[0][1] = a.m[0][0]*b.m[0][1]+a.m[0][1]*b.m[1][1];
  16.     m.m[1][0] = a.m[1][0]*b.m[0][0]+a.m[1][1]*b.m[1][0];
  17.     m.m[1][1] = a.m[1][0]*b.m[0][1]+a.m[1][1]*b.m[1][1];
  18.     return m;
  19. }
  20.  
  21. Matrix pow(Matrix M, int N)
  22. {
  23.     if (N == 1) return Matrix{};
  24.     Matrix m = pow(M,N/2);
  25.     m = m*m;
  26.     if (N%2) m = M*m;
  27.     return m;
  28. }
  29.  
  30. int fib(int N)
  31. {
  32.     Matrix M = pow(Matrix{},N);
  33.     return M.m[0][1];
  34. }
  35.  
  36. int main()
  37. {
  38.     for(int i = 1; i < 20; ++i)
  39.     {
  40.         cout << i << "   " << fib(i) << endl;
  41.     }
  42. }
  43.  
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1   1
2   1
3   2
4   3
5   5
6   8
7   13
8   21
9   34
10   55
11   89
12   144
13   233
14   377
15   610
16   987
17   1597
18   2584
19   4181
https://ideone.com/3CK5vD
language:
C++ (gcc 8.3)
created:
5 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!