modified fibonacci, O(n^1.58), Karatsuba algorithm, Fast SQR = (x*b + y)^2, where len(x) = len(y) +/- 1

gistfile1.cpp

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <algorithm>
using namespace std;

#define assert(x) ((void)(!(x) && (cout << "ERROR: at " << __FILE__ << ":" << __LINE__ << " " << #x << endl)))

class num {
  vector<long> v;
  bool neg;

  const static long base = 1000000000ul;
  const static int width = 9;

public:
  num(int n = 0) {
    v.clear();

    neg = false;
    if (n < 0) {
      n *= -1;
      neg = true;
    }

    while (n > 0) {
      v.push_back(n % base);
      n /= base;
    }

    norm();
  }

  num(const num &n) {
    v = n.v;
    neg = n.neg;
  }

  num(num &&n) : v(move(n.v)), neg(n.neg) {}

  inline size_t size() const { return v.size(); }

  inline void clear() { v.clear(); v.push_back(0); }

  inline void reserve(int n)  { v.reserve(n); }

  inline void fill0(int n) {
    while (n - (int)size() > 0) {
      v.push_back(0);
    }
  }

  inline void norm() {
    while (!v.empty() && *v.rbegin() == 0) {
      v.pop_back();
    }

    if (v.empty()) {
      v.push_back(0);
      neg = false;
    }
  }

  inline bool is0() const {
    return (v[0] == 0 && v.size() == 1) || v.empty();
  }

  inline bool positive() const { return !neg; }

  inline bool negative() const { return neg; }

  inline long& operator[](size_t i) { return v[i]; }

  inline long operator[](size_t i) const { return v[i]; }

  num& operator+=(const num &n) {
    // x + (-y) -> x - y
    if (!neg && n.neg) {
      num x(n);
      x.neg = !x.neg;
      *this -= x;
       return *this;
    }

    // -x + y -> y - x
    if (neg && !n.neg) {
      num x(*this);
      x.neg = !x.neg;
      *this = n - x;
      return *this;
    }

    size_t ms = max(size(), n.size());

    reserve(ms + 1);
    fill0(ms + 1);

    long c = 0;
    size_t i = 0;
    for (; i < ms; i++) {
      if (i < n.size()) {
        v[i] += c + n[i];
      } else {
        v[i] += c;
      }
      c = v[i] / base;
      v[i] %= base;
    }
    v[i] += c;

    norm();

    return *this;
  }

  num& operator-=(const num &n) {
    // x - (-y) -> y + x, if x < 0 <=> y - (+x)
    if (n.neg) {
      num y(n);
      y.neg = !y.neg;
      *this = y + *this;
      return *this;
    }

    // -x - (y) -> - (x + y)
    if (neg && !n.neg) {
      num x(*this);
      x.neg = !x.neg;
      x += n;
      x.neg = !x.neg;
      *this = x;
      return *this;
    }

    // 1 - 2
    if (*this < n) {
      *this = n - *this;
      neg = !neg;
      return *this;
    }

    // 2 - 1
    size_t ms = max(size(), n.size());
    long c = 0;
    size_t i = 0;
    for (; i < ms; i++) {
      if (i < n.size()) {
        v[i] -= c + n[i];
      } else {
        v[i] -= c;
      }
      if (v[i] < 0) {
        v[i] += base;
        c = 1;
      } else {
        c = 0;
      }
    }

    norm();

    return *this;
  }

  num& operator*=(const num &n) {
    num m;

    m.reserve(size() + n.size());
    m.fill0(size() + n.size());

    for (size_t i = 0; i < n.size(); i++) {
      long c = 0;
      for (size_t j = 0; j < v.size(); j++) {
        const size_t mi = i + j;
        m[mi] += c + v[j] * n[i];
        c = m[mi] / base;
        m[mi] %= base;
      }
      m[i + v.size()] += c;
    }

    m.norm();
    // -1 if -a*b, a*(-b), else +1
    m.neg = !m.is0() && neg != n.neg;

    *this = m;

    return *this;
  }

  num& operator=(num&& n) {
    v = move(n.v);
    neg = n.neg;
    return *this;
  }

  num& operator=(const num &n) {
    v = n.v;
    neg = n.neg;
    return *this;
  }

  friend num operator+(num lv, const num &rv) {
    lv += rv;
    return lv;
  }

  friend num operator-(num lv, const num &rv) {
    lv -= rv;
    return lv;
  }

  friend num operator*(num lv, const num &rv) {
    lv *= rv;
    return lv;
  }

  friend istream& operator>>(istream &io, num &v) {
    assert(!v.v.empty());

    v.v.clear();

    istream::sentry s(io);
    if (s) while (io.good()) {
      const char c = io.get();
      if (c == '-') {
        if (v.v.empty()) {
          v.neg = true;
        } else {
          break;
        }
      } else if (isspace(c, io.getloc())) {
        break;
      } else if (isdigit(c, io.getloc())) {
        long n = c - '0';
        if (v.v.empty() || (long)(*v.v.end() * 10 + n) >= base) {
          v.v.push_back(n);
        } else {
          v.v.push_back(*v.v.end() * 10 + n);
        }
      }
    }

    if (v.v.empty()) {
      v.v.push_back(0);
    }
    else {
      reverse(v.v.begin(), v.v.end());
    }

    return io;
  }

  friend ostream& operator<<(ostream &io, const num &v) {
    assert(!v.v.empty());

    if (v.neg) {
      io << "-";
    }

    auto x = v.v.rbegin();
    io << *x;

    while (++ x != v.v.rend()) {
      io << setw(width) << setfill('0') << *x;
    }

    return io;
  }

  friend bool operator==(const num &lv, const num &rv) {
    if (lv.neg != rv.neg || lv.size() != rv.size()) {
      return false;
    }

    return equal(lv.v.begin(), lv.v.end(), rv.v.begin());
  }

  friend bool operator!=(const num &lv, const num &rv) {
    return !(lv == rv);
  }

  friend bool operator<(const num &lv, const num &rv) {
    if (lv.is0() && rv.is0()) {
      return false;
    }

    if (lv.neg && !rv.neg) {
      return true;
    }

    if (!lv.neg && rv.neg) {
      return false;
    }

    if (lv.size() == rv.size()) {
      for (auto li = lv.v.rbegin(), ri = rv.v.rbegin(); \
          li != lv.v.rend() && ri != rv.v.rend(); \
          li ++, ri ++) {
            if (*li != *ri) {
              return *li < *ri && !lv.neg;
            }
      }
      return false;
    }

    // lv size != rv && (both neg or both pos)
    return (lv.size() < rv.size() && !lv.neg) ||
        (lv.size() > rv.size() && lv.neg);
  }

  friend bool operator<=(const num &lv, const num &rv) {
    return lv < rv || lv == rv;
  }

  void split_at(size_t m, num &h, num &l) const {
    h.v.clear();
    l.v.clear();

    auto vi = v.begin();
    for (; vi != v.end() && m > 0; vi ++, m --) {
        l.v.push_back(*vi);
    }
    for (; vi != v.end(); vi ++) {
        h.v.push_back(*vi);
    }

    h.norm();
    l.norm();
  }

  inline void mul10(size_t c) {
    v.insert(v.begin(), c, 0);
  }

  // karatsuba x *= y, x by reference
  friend void ksuba_mul_ref(num &lv, const num &rv,
      num &h1, num &l1, num &h2, num &l2,
      num &z0, num &z1, num &z2) {

    static const num num10(10);

    if (lv < num10 && rv < num10) {
      lv *= rv;
      return;
    }

    size_t m = max(lv.size(), rv.size());
    size_t m2 = m / 2;

    lv.split_at(m2, h1, l1);
    rv.split_at(m2, h2, l2);

    // z0 = karatsuba(low1,low2)
    z0 = l1; z0 *= l2;
    // z1 = karatsuba((low1+high1),(low2+high2))
    z1 = l1;
    z1+= h1;
    z2 = l2;
    z2+= h2;
    z1*= z2;
    // z2 = karatsuba(high1,high2)
    z2 = h1;
    z2*= h2;
    // (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)
    lv = z2;
    lv.mul10(2 * m2);

    lv+= z0;

    z1-= z2;
    z1-= z0;
    z1.mul10(m2);
    lv+= z1;
  }

  friend void sqr(num &lv) {
    if (lv.size() < 2) {
      lv *= lv;
      return;
    }

    size_t m = lv.size() / 2;

    num h1, l1;
    lv.split_at(m, h1, l1);

    lv = 2 * h1 * l1;
    lv.mul10(m);

    sqr(h1);
    h1.mul10(2 * m);
    lv+= h1;

    sqr(l1);
    lv+= l1;
  }
};

num fib(num t0, num t1, int n) {
  num t2;

  while (n > 2) {
    t2 = t1 * t1 + t0;

    t0 = t1;
    t1 = t2;

    n--;
  }

  return t2;
}

num ksuba_fib(num t0, num t1, int n) {
  num t2;
  num h1, l1, h2, l2, z0, z1, z2;

  while (n > 2) {
    t2 = t1;
    ksuba_mul_ref(t2, t1, h1, l1, h2, l2, z0, z1, z2);
    t2+= t0;

    t0 = t1;
    t1 = t2;

    n--;
  }

  return t2;
}

num sqr_fib(num t0, num t1, int n) {
  num t2;

  while (n > 2) {
    t2 = t1;
    sqr(t2);
    t2+= t0;

    t0 = t1;
    t1 = t2;

    n--;
  }

  return t2;
}

int test() {
  cout << "start test" << endl;
  for (int i = -100; i < 100; i ++) {
    for (int j = -100; j < 100; j ++) {
      if (num(i) < num(j) && i >= j) {
        cout << "ERROR: i < j, i = " << i << ", j = " << j << endl;
        return -1;
      }
    }
  }

  for (int i = -100; i < 100; i ++) {
    for (int j = -100; j < 100; j ++) {
      if (num(i * j) != num(i) * num(j)) {
        cout << "ERROR: i * j, i = " << i << ", j = " << j << endl;
        return -1;
      }
    }
  }

  for (int i = -100; i < 100; i ++) {
    for (int j = -100; j < 100; j ++) {
      if (num(i + j) != num(i) + num(j)) {
        cout << "ERROR: i + j, i = " << i << ", j = " << j << endl;
        return -1;
      }
    }
  }

  for (int i = -100; i < 100; i ++) {
    for (int j = -100; j < 100; j ++) {
      if (num(i - j) != num(i) - num(j)) {
        cout << "ERROR: i - j, i = " << i << ", j = " << j << endl;
        return -1;
      }
    }
  }

  for (int i = -100; i < 100; i ++) {
    for (int j = -100; j < 100; j ++) {
      if (num(i * j + i + j) != num(i) * num(j) + num(i) + num(j)) {
        cout << "ERROR: i * j + i + j, i = " << i << ", j = " << j;
        cout << ", i * j = " << num(i) * num(j);
        cout << ", i * j + i = " << num(i) * num(j) + num(i);
        cout << ", i * j + i + j = " << num(i) * num(j) + num(i) + num(j);
        cout << endl;
        return -1;
      }
    }
  }

  for (int i = 0; i < 1000; i ++) {
      num j = num(i);
      sqr(j);
      if (num(i * i) != j) {
        cout << "ERROR: i * j, i = " << i << ", j = " << j;
        cout << endl;
        return -1;
      }
  }

  for (int l = 3; l <= 20; l ++) {
  for (int i = 0; i <= 2; i ++) {
  for (int j = 0; j <= 2; j ++) {
    num r1 = fib(i, j, l);
    num r2 = ksuba_fib(i, j, l);
    num r3 = sqr_fib(i, j, l);
    if (r1 != r2 || r2 != r3) {
      cout << "wrong result " << i << ", " << j << ", " << " " << l << endl << r1 << endl << r2 << endl << r3 << endl;
      return -1;
    }
  }
  }
  }

  cout << "end test" << endl;
  return 0;
}

int main() {
  num a, b;
  int n;

  // int top = test(); if (top) { return top;  }

  cin >> a >> b >> n;

  //cout << fib(a, b, n) << endl;
  //cout << ksuba_fib(a, b, n) << endl;
  cout << sqr_fib(a, b, n) << endl;

  return 0;
}