gistfile1.ec

public define Phi = 1.6180339887;

bool IsPerfectSquare(uint64 number)
{
   double root = sqrt(number);
   uint64 square = (uint64)root * (uint64)root;
   return square == number;
}

struct Matrix2x2
{
   uint64 m[2][2];

   void Multiply(Matrix2x2 a, Matrix2x2 b)
   {
      m[0][0] = a.m[0][0] * b.m[0][0] + a.m[0][1] * b.m[1][0];
      m[0][1] = a.m[0][0] * b.m[0][1] + a.m[0][1] * b.m[1][1];
      m[1][0] = a.m[1][0] * b.m[0][0] + a.m[1][1] * b.m[1][0];
      m[1][1] = a.m[1][0] * b.m[0][1] + a.m[1][1] * b.m[1][1];
   }

   void Power(Matrix2x2 src, int n)
   {
      if(n == 0)
      {
         static Matrix2x2 identity { { { 1, 0 }, { 0, 1 } } };
         this = identity;
         //this = { { { 1, 0 }, { 0, 1 } } };
      }
      else if(n == 1)
         this = src;
      else if(n == 2)
         Multiply(src, src);
      else
      {
         if(n > 1)
         {
            Matrix2x2 temp;
            temp.Power(src, n/2);
            Multiply(temp, temp);
         }
         if(n & 1)
         {
            Matrix2x2 temp;
            temp.Multiply(this, src);
            this = temp;
         }
      }
   }
};

class FibIterator : IteratorPointer { public uint64 num1, num2; }
class Fibonacci : Container<T = uint64>
{
   uint64 min, max;
   max = MAXQWORD;
   IteratorPointer GetFirst()
   {
      if(min)
      {
         int n = (int)((log((uint64)min) + log(5)/2) / log(Phi) + 0.5);
         FibIterator fib = (FibIterator)GetAtPosition(n, false);
         FibIterator result = fib;
         if(result.num1 < min)
         {
            result = (FibIterator)GetNext(result);
            // if(!result) delete fib;
         }
         return result;
      }
      else
         return FibIterator { num2 = 1 };
   }
   IteratorPointer GetLast()
   {
      int n = (int)((log((uint64)max) + log(5)/2) / log(Phi));
      return GetAtPosition(n, false);
   }

   IteratorPointer GetNext(IteratorPointer ip)
   {
      if(ip)
      {
         FibIterator fib = (FibIterator)ip;
         uint64 num = fib.num1 + fib.num2;
         if(fib.num2 > max || fib.num2 < fib.num1 || (fib.num1 > 1 && fib.num2 == fib.num1))
         {
            delete fib;
            return null;
         }
         fib.num1 = fib.num2;
         fib.num2 = num;
      }
      return ip;
   }
   IteratorPointer GetPrev(IteratorPointer ip)
   {
      if(ip)
      {
         FibIterator fib = (FibIterator)ip;
         uint64 diff = fib.num2 - fib.num1;
         if(fib.num1 <= min) { delete fib; return null; }
         fib.num2 = fib.num1;
         fib.num1 = diff;
      }
      return (IteratorPointer)ip;
   }
   IteratorPointer GetAtPosition(I pos, bool create)
   {
      static Matrix2x2 fibMatrix { { { 1,1 }, { 1,0 } } };
      Matrix2x2 result;
      result.Power(fibMatrix, (int)pos);
      return FibIterator { result.m[1][0], result.m[0][0] };
   }

   virtual IteratorPointer Find(D value)
   {
      uint64 number = 5*(uint64)value*(uint64)value;
      if(IsPerfectSquare(number - 4) || IsPerfectSquare(number + 4))
      {
         int n = (int)((log((uint64)value) + log(5)/2) / log(Phi) + 0.5);
         return GetAtPosition(n, false);
      }
      return null;
   }

   T GetData(IteratorPointer ip) { return *(T *)&((FibIterator)ip).num1; }
   void FreeIterator(IteratorPointer ip) { delete ip; }
}