Sometimes I'm ashamed

to write such ugly things. This clearly was a trial-and-error design. Strip away all the comments, and mourn your 'cleverness' ever after.

long fib(long n){
long a[3] = {1, 0, 1};
int i = 1;
while(n > 0) {
a[(i+2)%3] = a[(i + 1)%3] + a[i%3];
i = (i+1)%3;
n--;
}
return a[i];
}


Of course, you could define a class of integers mod n, and replace int i with
modular i = new modular(3);