#include <stdlib.h>
#include <stdio.h>

void fib__(long n,long *f1,long *f2)
{
        if(n==1)
        {
                *f1=*f2=1;
	}
	else
        if(n==2)
        {
                *f1=1; *f2=2;
	}
	else
        if(n&1) /* (n%2) als Binaerer test */
        {
                long f3,f4,f5;
                fib__(n>>1,&f3,&f4);
                /* fib__(n/2,&f3,&f4); */
                f5 = f3+f4;
                *f1 = f3*f3 + f4*f4;
                *f2 = f5*f5 - f3*f3;
        }
        else
        {
                long f3,f4,f5;
                fib__((n>>1)-1,&f3,&f4);
                /* fib__(n/2-1,&f3,&f4); */
                f5 = f3+f4;
                *f1 = f5*f5 - f3*f3;
                *f2 = f5*f5 + f4*f4;
        }
}

long fibonacci(long n)
{
        long f1,f2;
        fib__(n,&f1,&f2);
        return f1;
}

int main()
{
        long K;
        char s[80];
        do
        {
                printf("n: ");
                gets(s);
                if (strlen(s)==0) exit(0);
                K = atol(s);
                printf("\rErgebnis: %ld\n\n", fibonacci(K));
        }
        while (1);
}