title: Very Large Fibonacci in Java
body: <p>I am trying to rapidly calculate large Fibonacci numbers. Here is my code. It is prohibitively slow for numbers above 1 million, how can it be improved?  </p>
  
  <pre><code>public static BigInteger fib(BigInteger n) {
  
          int k = n.intValue();
          BigInteger ans = null;
  
          if(k == 0) { 
              ans = new BigInteger("0");
          } else if(Math.abs(k) &lt;= 2) {
              ans = new BigInteger("1");
          } else {
              BigInteger km1 = new BigInteger("1");
              BigInteger km2 = new BigInteger("1");
  
              for(int i = 3; i &lt;= Math.abs(k); ++i) {
                  ans = km1.add(km2);
                  km2 = km1;
                  km1 = ans;
              }
          }
  
         if(k&lt;0 &amp;&amp; k%2==0) { ans = ans.negate(); }
         return ans;
      } 
  </code></pre>
  
  <p>Binet's worked well. Thanks guys! </p>