#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

typedef unsigned int ui;
typedef unsigned long long ull;

ui addmod ( ui a, ui b, ui m )
{
   ull c;

   c = (ull)a + (ull)b;
   if (c >= (ull)m) c -= m;
   return (ui)c;
}

ui submod ( ui a, ui b, ui m )
{
   ull c;

   if (a >= b) return (a - b);
   c = (ull)a + (ull)m - (ull)b;
   return (ui)c;
}

ui mulmod ( ui a, ui b, ui m )
{
   ull c;

   c = (ull)a * (ull)b;
   c %= (ull)m;
   return (ui)c;
}

ui Fibrec ( ui n, ui m )
{
   if (n == 0) return 0U;
   if (n == 1) return 1U;
   return addmod(Fibrec(n-1,m),Fibrec(n-2,m),m);
}

ui Fibiter ( ui n, ui m )
{
   ui F, F_1, F_2, i;

   if (n == 0) return 0U;
   if (n == 1) return 1U;
   F_2 = 0; F_1 = 1; i = 1;
   while (i < n) {
      ++i; F = addmod(F_1,F_2,m);
      F_2 = F_1; F_1 = F;
   }
   return F;
}

ui Fiblog ( ui n, ui m )
{
   int s;
   ui F, Fnext, t, t1;

   if (n == 0) return 0U;
   if (n == 1) return 1U;
   F = 0; Fnext = 1;
   s = 31; while ((n & (1U << s)) == 0) --s;
   while (s >= 0) {
      t1 = mulmod(Fnext,Fnext,m);
      t = mulmod(F,F,m);
      t1 = addmod(t1,t,m);
      if ((n & (1U << s)) == 0) {
         t = addmod(Fnext,Fnext,m);
         t = submod(t,F,m);
         F = mulmod(t,F,m);
         Fnext = t1;
      } else {
         t = addmod(F,F,m);
         t = addmod(Fnext,t,m);
         Fnext = mulmod(Fnext,t,m);
         F = t1;
      }
      --s;
   }
   return F;
}

int main ()
{
   clock_t c1, c2;
   ui m, n, r, f;

   c1 = clock();
   m = 29U; r = m % 5; n = ((r == 1) || (r == 4)) ? m - 1 : m + 1;
   f = Fibrec(n,m);
   c2 = clock();
   printf("*** Recursive Fibonacci   : F_%u (mod %u) = %u\n", n, m, f);
   printf("    Time taken = %lf sec\n", (double)(c2 - c1) / (double)CLOCKS_PER_SEC);
   c1 = clock();
   m = 43U; r = m % 5; n = ((r == 1) || (r == 4)) ? m - 1 : m + 1;
   f = Fibrec(n,m);
   c2 = clock();
   printf("*** Recursive Fibonacci   : F_%u (mod %u) = %u\n", n, m, f);
   printf("    Time taken = %lf sec\n", (double)(c2 - c1) / (double)CLOCKS_PER_SEC);

   c1 = clock();
   m = 33554393U; r = m % 5; n = ((r == 1) || (r == 4)) ? m - 1 : m + 1;
   f = Fibiter(n,m);
   c2 = clock();
   printf("*** Iterative Fibonacci   : F_%u (mod %u) = %u\n", n, m, f);
   printf("    Time taken = %lf sec\n", (double)(c2 - c1) / (double)CLOCKS_PER_SEC);
   c1 = clock();
   m = 1073741789U; r = m % 5; n = ((r == 1) || (r == 4)) ? m - 1 : m + 1;
   f = Fibiter(n,m);
   c2 = clock();
   printf("*** Iterative Fibonacci   : F_%u (mod %u) = %u\n", n, m, f);
   printf("    Time taken = %lf sec\n", (double)(c2 - c1) / (double)CLOCKS_PER_SEC);

   c1 = clock();
   m = 2147483647U; r = m % 5; n = ((r == 1) || (r == 4)) ? m - 1 : m + 1;
   f = Fiblog(n,m);
   c2 = clock();
   printf("*** Logarithmic Fibonacci : F_%u (mod %u) = %u\n", n, m, f);
   printf("    Time taken = %lf sec\n", (double)(c2 - c1) / (double)CLOCKS_PER_SEC);
   c1 = clock();
   m = 4294967291U; r = m % 5; n = ((r == 1) || (r == 4)) ? m - 1 : m + 1;
   f = Fiblog(n,m);
   c2 = clock();
   printf("*** Logarithmic Fibonacci : F_%u (mod %u) = %u\n", n, m, f);
   printf("    Time taken = %lf sec\n", (double)(c2 - c1) / (double)CLOCKS_PER_SEC);

   exit(0);
}