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 
#include 
#include 
#include 
#include 

using namespace std;

const int initFibo[5] = {5,3,2,1,1};
template  
void fastFibo(U n, V *tuple) {
    assert(n >= 4);
    if(n (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 (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?

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  
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 
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  
    static void fastFibo_impl(U n, V *tuple) {
        assert(n >= 4);
        if(n (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 
    static V fastFibo(U n){
        if( n (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.

StackExchange Code Review Q#27388, answer score: 3