title: Fibonacci - Divide and conquer algorithm
body: <pre><code>#include &lt;iostream&gt;
  using namespace std;
  
  int main() {
      int i=1;
      int j=0;
      int k=0;
      int h=1;
      int t=0;
      int n;
      cin&gt;&gt;n;
  
      while (n) {
          if (n%2) {
              t=j*h;
              j=i*h+j*k+t;
              i=ik+t;
          }
  
          t=h*h;
          h=2*k*h+t;
          k=k*k+t;
          n=n/2;
      }
  
      cout&lt;&lt;j;
      return 0;
  }
  </code></pre>
  
  <p>This is the fastest algorithm for Fibonacci I found on the internet. Other algorithms I understand but this one doesn't make any sense to me.</p>
  
  <p>I don't see how this algorithm is related to matrix multiplication or exponentiation by squaring. Can someone explain?</p>