How can we achieve last e.g. 6 digits of of Nth Fibonacci number in O(logN) time?

Question

I have seen a task on an online test with competitive programming challenges (cannot disclose unfortunately where) to produce last (least significant) 6 digits of Nth Fibonacci number.

I have managed to come up with the following solution:

#include <iostream>
#include <cassert>
#include <tuple>

int solution(int N)
{
  if(N == 0) return 0;
  if(N == 1) return 1;
  if(N == 2) return 1;
  int a = 0;
  int b = 1;
  int c = 1;

  for (int i = 3; i <= N; ++i) {
    std::tie(a, b, c) = std::make_tuple(b, (a + b) % 1000000, (b + c) % 1000000);
  }
  return c;
}

int main()
{
  assert(solution(8) == 21);
  assert(solution(36) == 930352);
  std::cout << solution(10000000) << std::endl;
}

which unfortunately has O(N) time complexity and start to run quite slow for inputs like in the last line: N > 10000000.

Anyone knows how this can be achieved in O(logN)?

presumably, much the same way you can get the *entire* [nth fibonacci number in O(log n) time](http://stackoverflow.com/a/1525544/4892076) — jaggedSpire, Jul 26 '16 at 20:36
The notes on those questions indicate that the answer is wrong at a certain digit. — West, Jul 26 '16 at 20:41
@West [Covered by yairchu's answer to the tagged question](http://stackoverflow.com/questions/1525521/nth-fibonacci-number-in-sublinear-time/1550208#1550208) — user4581301, Jul 26 '16 at 20:45
with its ending statement that "If you only want the lower digits of the answer, then it is possible to calculate in sub-linear time using the matrix exponentiation method." nicely dovetailing into the [matrix exponentiation answer](http://stackoverflow.com/a/1526837/4892076) — jaggedSpire, Jul 26 '16 at 20:51
Wikipedia already has answer: [https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form](https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form) — Calvinxiao, Jul 27 '16 at 03:13

score 2 · Answer 1 · answered Jul 26 '16 at 20:37

There is an algorithm taking O(log_n) time to compute nth Fibonacci number using Q-Matrix. You can take a look at http://kukuruku.co/hub/algorithms/the-nth-fibonacci-number-in-olog-n, the only change you will need is to make sure it produce only last 6 digits.

How can we achieve last e.g. 6 digits of of Nth Fibonacci number in O(logN) time?

1 Answers1