Could someone, please, comment on my code?
Here it is:
Fib.cpp
#include "Fib.h" unsigned fibonacciLinear(const unsigned& n) { unsigned val[] = {0,1,1}; for(unsigned i(2); i<=n; ++i) {val[i%3] = val[(i-1)%3] + val[(i-2)%3];} return val[n%3]; } unsigned fastRecursiveFibonacci(const unsigned& n) { Matrix2x2 res = { 1, 0, 0, 1 }; fastRecursiveFibonacci(res, n); assert(("Fibonacci number was computed wrong", res._21 == fibonacciLinear(n))); return res._21; } void fastRecursiveFibonacci(Matrix2x2& res, const unsigned& n) { static Matrix2x2 m = { 1, 1, 1, 0 }; if(n > 0) { unsigned lN(n); if(n&1) { res*=m; --lN; } else { m*=m; lN/=2; } fastRecursiveFibonacci(res, lN); } }
Fib.h
//#define NDEBUG #include <cassert> struct Matrix2x2 { int _11, _12, _21, _22; void Matrix2x2::operator*=(const Matrix2x2 matrix) { int new11(matrix._11*_11 + matrix._21*_12); int new12(matrix._12*_11 + matrix._22*_12); int new21(matrix._11*_21 + matrix._21*_22); int new22(matrix._12*_21 + matrix._22*_22); _11 = new11; _12 = new12; _21 = new21; _22 = new22; return; } }; unsigned fibonacciLinear(const unsigned&); unsigned fastRecursiveFibonacci(const unsigned&); void fastRecursiveFibonacci(Matrix2x2&, const unsigned&);
The things which seem to be a bad practice are using a static function variable and a bad recursion style. Could you recommend any other approaches?