fib.manual_opt.cpp

#include <iostream>

long long fib_00(int n) {
  if (n < 3)
    return 1;
  return fib_00(n - 1) + fib_00(n - 2);
}

long long fib_01(int n) {
  if (n < 3)
    return 1;
  long long prev1 = fib_01(n - 1);
  long long prev2 = fib_01(n - 2);
  return prev1 + prev2;
}

long long fib_02(int n) {
  if (n < 3)
    return 1;
  long long prev1 = 1;
  if (n - 1 > 2)
    prev1 = fib_02(n - 2) + fib_02(n - 3);
  long long prev2 = 1;
  if (n - 2 > 2)
    prev2 = fib_02(n - 3) + fib_02(n - 4);
  return prev1 + prev2;
}

long long fib_03(int n) {
  if (n < 3)
    return 1;
  long long prev1 = 1;
  long long prev2 = 1;
  if (n > 3) {
    prev1 = fib_03(n - 2) + fib_03(n - 3);
    if (n > 4)
      prev2 = fib_03(n - 3) + fib_03(n - 4);
  }
  return prev1 + prev2;
}

long long fib_04(int n) {
  if (n < 3)
    return 1;
  long long prev1 = 1;
  long long prev2 = 1;
  if (n > 3) {
    long long prev3 = fib_04(n - 3);
    prev1 = fib_04(n - 2) + prev3;
    if (n > 4)
      prev2 = prev3 + fib_04(n - 4);
  }
  return prev1 + prev2;
}

long long fib_05(int n) {
  if (n < 3)
    return 1;
  long long prev1 = 1;
  long long prev2 = 1;
  if (n > 3) {
    long long prev3 = fib_05(n - 3);
    long long prev2a = 1;
    if (n > 4)
      prev2a = fib_05(n - 3) + fib_05(n - 4);
    prev1 = prev2a + prev3;
    if (n > 4)
      prev2 = prev3 + fib_05(n - 4);
  }
  return prev1 + prev2;
}

long long fib_06(int n) {
  if (n < 3)
    return 1;
  long long prev1 = 1;
  long long prev2 = 1;
  if (n > 3) {
    long long prev3 = fib_06(n - 3);
    long long prev2a = 1;
    if (n > 4)
      prev2a = prev3 + fib_06(n - 4);
    prev1 = prev2a + prev3;
    if (n > 4)
      prev2 = prev3 + fib_06(n - 4);
  }
  return prev1 + prev2;
}

long long fib_07(int n) {
  if (n < 3)
    return 1;
  long long prev1 = 1;
  long long prev2 = 1;
  if (n > 3) {
    long long prev3 = fib_07(n - 3);
    long long prev2a = 1;
    if (n > 4) {
      prev2a = prev3 + fib_07(n - 4);
      prev2 = prev3 + fib_07(n - 4);
    }
    prev1 = prev2a + prev3;
  }
  return prev1 + prev2;
}

long long fib_08(int n) {
  if (n < 3)
    return 1;
  long long prev1 = 1;
  long long prev2 = 1;
  if (n > 3) {
    long long prev3 = fib_08(n - 3);
    long long prev2a = 1;
    if (n > 4) {
      long long prev4 = fib_08(n - 4);
      prev2a = prev3 + prev4;
      prev2 = prev3 + prev4;
    }
    prev1 = prev2a + prev3;
  }
  return prev1 + prev2;
}

long long fib_09(int n) {
  if (n < 3)
    return 1;
  long long prev1 = 1;
  long long prev2 = 1;
  if (n > 3) {
    long long prev3 = fib_09(n - 3);
    if (n > 4) {
      prev2 = prev3 + fib_09(n - 4);
    }
    prev1 = prev2 + prev3;
  }
  return prev1 + prev2;
}

int main() {
  int n = 0;
  std::cout << "n = ";
  std::cin >> n;
  int fib_num = 0;
  std::cout << "fib_num = ";
  std::cin >> fib_num;
  switch (fib_num) {
    case 0: std::cout << "fib_00(" << n << ") = " << fib_00(n) << std::endl; break;
    case 1: std::cout << "fib_01(" << n << ") = " << fib_01(n) << std::endl; break;
    case 2: std::cout << "fib_02(" << n << ") = " << fib_02(n) << std::endl; break;
    case 3: std::cout << "fib_03(" << n << ") = " << fib_03(n) << std::endl; break;
    case 4: std::cout << "fib_04(" << n << ") = " << fib_04(n) << std::endl; break;
    case 5: std::cout << "fib_05(" << n << ") = " << fib_05(n) << std::endl; break;
    case 6: std::cout << "fib_06(" << n << ") = " << fib_06(n) << std::endl; break;
    case 7: std::cout << "fib_07(" << n << ") = " << fib_07(n) << std::endl; break;
    case 8: std::cout << "fib_08(" << n << ") = " << fib_08(n) << std::endl; break;
    case 9: std::cout << "fib_09(" << n << ") = " << fib_09(n) << std::endl; break;
    default: std::cerr << "Error: undefined function number " << fib_num << std::endl;
  }
}

n = fib_num = fib_00(50) = 12586269025

real  3m18.189s
user  3m16.864s
sys   0m0.116s

n = fib_num = fib_01(50) = 12586269025

real  3m9.642s
user  3m8.904s
sys   0m0.248s

n = fib_num = fib_02(50) = 12586269025

real  1m38.442s
user  1m38.206s
sys   0m0.072s

n = fib_num = fib_03(50) = 12586269025

real  1m32.391s
user  1m31.734s
sys   0m0.308s

n = fib_num = fib_04(50) = 12586269025

real  0m1.931s
user  0m1.912s
sys   0m0.016s

n = fib_num = fib_05(50) = 12586269025

real  0m2.600s
user  0m2.588s
sys   0m0.004s

n = fib_num = fib_06(50) = 12586269025

real  0m0.034s
user  0m0.024s
sys   0m0.004s

n = fib_num = fib_07(50) = 12586269025

real  0m0.033s
user  0m0.028s
sys   0m0.004s

n = fib_num = fib_08(50) = 12586269025

real  0m0.006s
user  0m0.000s
sys   0m0.000s

n = fib_num = fib_09(50) = 12586269025

real  0m0.006s
user  0m0.000s
sys   0m0.004s