Pell numbers, Fibonacci numbers, memoized, and GCD...oh my...

number-thy.cpp

#include <functional>
#include <iostream>
#include <string>
#include <map>

/*
 * An example of some number theory calculations, done with dynamic
 * programming.
 *
 * Partially inspired by http://programminggenin.blogspot.com/2013/01/memoization-in-c.html
 *
 * Compiles as:
 * $ g++ -Wall -std=c++11 number-thy.cpp
 **/

typedef unsigned long long ubyte64;

template<class InType, class OutType>
std::function<OutType(InType)> memoize(std::function<OutType(InType)> fn)
{
  // return a lambda, this is a function
  return [fn](InType n) {
    static std::map<InType,OutType> memo;
    
    OutType ret;
    // if the value has been memoized
    if (memo.count(n) > 0) {
      ret = memo[n];
      return ret;
    }
    
    ret = fn(n);
    memo[n] = ret;
    return ret;
  };
}

std::function<unsigned(unsigned)> fibonacci=[](unsigned n)
{
  if (n <= 1)
    return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
};

std::function<ubyte64(ubyte64)> pell=[](ubyte64 n)
{
  if (n < 2) 
    return n;
  return 2*pell(n - 1) + pell(n - 2);
};

long long gcd(long long x, long long y)
{
  long long a, b, r;
  a = (x > y ? x : y);
  b = (x > y ? y : x);
  r = a % b;
  while (r != 0) {
    a = b;
    b = r;
    r = a % b;
  }
  return a;
}   

int main(int argc, char*argv[])
{
  ubyte64 x;
  fibonacci = memoize(fibonacci);
  pell = memoize(pell);
  x = std::stoull(argv[1]);
  std::cout << argv[1] 
            << " -> " 
            << pell(x)
            << std::endl;
  return 0;
}