# O(lg n) algorithm for a fibonacci number with c++ template

I wrote a function to find a specific fibonacci number, which runs in O(lg n). Then I modified it with a template. Though it works, I'm new to template and want to know if I used template correctly. Moreover, I wonder whether someone who has a BigNumber class can use my function without modify my source code.

#include <iomanip>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstring>

using namespace std;

const int initFibo[5] = {5,3,2,1,1};
template <class U, class V>
void fastFibo(U n, V *tuple) {
assert(n >= 4);
if(n <= 5) {
for(int i = 0; i < 4; i++)
tuple[i] = initFibo[i + (5 - n)];
return;
}
V tmp[4];
fastFibo<U, V>(n / 2 + 1, tmp);
if(n % 2 == 0) { // even
tuple[0] = tmp[0] * tmp[1] + tmp[1] * tmp[2];
tuple[1] = tmp[1] * tmp[1] + tmp[2] * tmp[2];
tuple[2] = tmp[1] * tmp[2] + tmp[2] * tmp[3];
tuple[3] = tmp[2] * tmp[2] + tmp[3] * tmp[3];
} else {
tuple[0] = tmp[0] * tmp[0] + tmp[1] * tmp[1];
tuple[1] = tmp[0] * tmp[1] + tmp[1] * tmp[2];
tuple[2] = tmp[1] * tmp[1] + tmp[2] * tmp[2];
tuple[3] = tmp[1] * tmp[2] + tmp[2] * tmp[3];
}
}

int main(){
unsigned long long tuple[4];
for(int i = 4; i <= 93; i++){
fastFibo<int, unsigned long long >(i, tuple);
cout << "Fibo(" << setw(2) << i << ")=" << setw(20) << tuple[0] << endl;
}
system("pause");
return 0;
}


@Yuushi:

"Why does n have to be >= 4?... passing a size and a pointer..." Required by my algorithm, n must be >= 4 and tuple is always an array of size 4 (not n) (After invocation tuple will contains 4 fibonacci numbers: the nth, n-1th, n-2th and n-3th). I thought up an idea to create a method like this:

V fastFibo2(U n){
if( n < 4 )
return initFibo[5 - n];
else{
V buf[4];
fastFibo(n, buf)
return buf[0];
}
}


However if I create it I don't want user to access the ordinary fastFibo. Is it possible or is there a better solution?

• using namespace std is not good to use. Read this for more information.system("PAUSE") is not good, either. Instead, try std::cin.get(). Jun 14, 2013 at 4:28
• @Jamal: Rather than add any command to pause the code. 1) run it in the command line (there it does not matter). 2) Set up your IDE to pause and not shut down the window when the application exits. There should be no reason to add manual pause. Jun 14, 2013 at 15:05
• @LokiAstari: Oh yeah, I forgot to mention that. I also never figured out how to do it with my own IDE (Visual C++ 2010), but I'll find out. Jun 14, 2013 at 17:04
• If you don't mind some precision loss, you can use the formula $$F_n = \frac{\phi^n - \hat{\phi}{}^n}{\sqrt{5}}.$$ Apr 27, 2019 at 2:14

As always, using namespace std; is dangerous. In fact, there is a tuple class in C++11, std::tuple. You could very easily have a naming collision here thanks to that.

Why bother using a template for the size if you compare it to an int anyway? It's overkill here. If you do decide to keep it, you should give your template parameters more descriptive names here. T is used when there really is no information about what the possible type could be, as in container classes. However, the value here is going to have to be some kind of integral constant - so call it as such.

template <class IntegralValue, class IntegralValue2>
void fastFibo(IntegralValue n, IntegralValue *tuple)


Why does n have to be >= 4? What happens if the user wants the value at 1? This shouldn't throw up an error (or in this case, call abort). This violates the principle of least surprise.

Finally, passing a size and a pointer as parameters is the C way of doing things. In C++, prefer to use the concept of Iterators:

template <typename Iterator>
void fastFibo(Iterator begin, Iterator end)


This makes the code below a little bit messier, but doesn't force the user to utilize an array. They could use a std::vector (preferable), or even a list, set, or their own custom data structure to store the results. You can get the distance between two iterators using std::distance.

Edit: There are a couple of solutions to your problem. Using another function which forwards to fastFibo is a reasonable solution here, as it hides the user from some of the implementation details. With templates, it's a bit trickier to hide things (since they need to be in header files). One way is using a namespace like detail (which generally indicates that the things inside it are internal and shouldn't be used directly). Another possibility is to use a class or struct with static member functions: the call then looks very much like using a namespace, but you can utilize access protection modifiers. For example:

struct fib
{
private:
const static int initFibo[5] = {5,3,2,1,1};

template <class U, class V>
static void fastFibo_impl(U n, V *tuple) {
assert(n >= 4);
if(n <= 5) {
for(int i = 0; i < 4; i++)
tuple[i] = initFibo[i + (5 - n)];
return;
}
V tmp[4];
fastFibo_impl<U, V>(n / 2 + 1, tmp);
if(n % 2 == 0) { // even
tuple[0] = tmp[0] * tmp[1] + tmp[1] * tmp[2];
tuple[1] = tmp[1] * tmp[1] + tmp[2] * tmp[2];
tuple[2] = tmp[1] * tmp[2] + tmp[2] * tmp[3];
tuple[3] = tmp[2] * tmp[2] + tmp[3] * tmp[3];
} else {
tuple[0] = tmp[0] * tmp[0] + tmp[1] * tmp[1];
tuple[1] = tmp[0] * tmp[1] + tmp[1] * tmp[2];
tuple[2] = tmp[1] * tmp[1] + tmp[2] * tmp[2];
tuple[3] = tmp[1] * tmp[2] + tmp[2] * tmp[3];
}
}

public:

template <typename U, typename V>
static V fastFibo(U n){
if( n < 4 )
return initFibo[5 - n];
else {
V buf[4];
fastFibo_impl<U, V>(n, buf)
return buf[0];
}
}
};


which is then called by fib::fastFibo<...>(...).

I also noticed I didn't answer one of your questions. If someone wishes to use this with their own BigNumber class, then their class would need to support operator*, operator+, and operator= (and have those functions perform integer multiplication, integer addition, and integer assignment). This falls under the idea of Concepts, which were slated for inclusion into C++11, but were dropped due to not being ready. Suffice to say, as long as the user has a BigNumber class that "acts like" an integer with respect to *, + and =, is DefaultConstructable (since you call the default constructor for V in V buf[4]), and has an overload of operator+ taking a BigNumber and an int, they could use it in your template without having to touch anything.

• Can you take a look at my update? I put everything I want to speak there. Jun 14, 2013 at 7:59
• @johnchen902 See my edit. Jun 14, 2013 at 8:35