Skip to content

Instantly share code, notes, and snippets.

@jerstlouis
Last active May 25, 2017 11:34
Show Gist options
  • Save jerstlouis/ea2f3249b00951b26df89e541d2ec4eb to your computer and use it in GitHub Desktop.
Save jerstlouis/ea2f3249b00951b26df89e541d2ec4eb to your computer and use it in GitHub Desktop.
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, null);
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, null);
}
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, bool * justAdded)
{
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, null);
}
return null;
}
T GetData(IteratorPointer ip) { return *(T *)&((FibIterator)ip).num1; }
void FreeIterator(IteratorPointer ip) { delete ip; }
}
void TestFibonacci()
{
Fibonacci fibonacci { };
Iterator<uint64> i { fibonacci };
int c;
//while(i.Next())
while(i.Prev())
{
PrintLn(i.data);
}
for(c = 0; c<10; c++)
{
i.Index(c, false);
PrintLn(i.data);
}
if(i.Find(233))
{
Print(i.data, " is a Fibonacci number, next is ");
i.Next();
PrintLn(i.data);
}
if(i.Find(145))
PrintLn(i.data, " is a Fibonacci number");
i.Free();
delete fibonacci;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment