Last active
May 25, 2017 11:34
-
-
Save jerstlouis/ea2f3249b00951b26df89e541d2ec4eb to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; } | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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