First Fibonnaci index with 1000 digits

main.cpp

#include <cmath>
#include <iostream>
#include <vector>

const uint64_t MAX_UINT64 = std::numeric_limits<uint64_t>::max();

uint64_t numDigits(std::vector<uint64_t> num) {
  // num is described by num[0] + num[1] * MAX_UINT64 + num[2] * MAX_UINT64^2 + ...
  if (num.empty()) return 0;

  // The most significant block contributes the most digits
  // Use logarithm to estimate the number of digits
  int msbIndex = num.size() - 1;
  double msbDigits = std::log10(num[msbIndex]) + 1;
  double totalDigits = msbDigits + msbIndex * std::log10(static_cast<double>(MAX_UINT64));

  return static_cast<uint64_t>(std::floor(totalDigits));
}

std::vector<uint64_t> add(const std::vector<uint64_t>& l, const std::vector<uint64_t>& r) {
  size_t maxLength = std::max(l.size(), r.size());
  std::vector<uint64_t> result(maxLength, 0);
  uint64_t carry = 0;

  for (size_t i = 0; i < maxLength; ++i) {
    uint64_t left = i < l.size() ? l[i] : 0;
    uint64_t right = i < r.size() ? r[i] : 0;

    uint64_t sum = left + right + carry;
    carry = sum < left ? 1 : 0;  // check for overflow

    result[i] = sum;
  }

  if (carry > 0) {
    result.push_back(carry);
  }

  return result;
}

int main(void) {
  std::vector<uint64_t> f1 = {1};
  std::vector<uint64_t> f2 = {1};
  std::vector<uint64_t> f3 = {2};

  uint64_t i = 3;

  while (numDigits(f3) < 1000) {
    f1 = f2;
    f2 = f3;
    f3 = add(f1, f2);
    ++i;
  }

  std::cout << "index: " << i << std::endl;
  return 0;
}