There is a task "It is required to find the last digit of the n-th Fibonacci number." at http://acmp.ru/?main=task&id_task=623

My solution is (I do not know how ethical it is to put the solution code in public)

#include <iostream> #include <stdio.h> using namespace std; int main(){ int a=1, b=1, c=a+b, n; cin >> n; if (n <= 1) c = 1; else for (int i = 2; i <= n; i++){ c = (a + b) % 10; a = b; b = c; } cout << c % 10; return 0; }

Result: Runtime 0.858 Memory 772 Kb

According to the table on the page http://acmp.ru/index.asp?main=bstatus&id_t=623&lang=CPP due to a small increase in memory consumption as it manages to invest in 1-2 seconds. On the one hand, I may have slipped the input number 1000, and the other 10.

Any ideas for better performance?

  • Obvious optimization of the task itself seems to have already been applied. Most likely, you can save on IO. - D-side
  • one
    Why is it bad to use a formula for the nth member of a recurrent relation specifying Fibonacci numbers? On paper, displays minutes for 7, and is programmed easily. ideone.com/WTXmX5 - typemoon
  • Rewrite on asma habrahabr.ru/post/252647 - Serge Esmanovich
  • @typemoon: Hm. A thousandth term in a sequence requires only a thousand iterations with addition, so this is not much. But in the construction of the thousandth degree, you can get out of the double . - VladD

4 answers 4

Quote from wikipedia

The period of Fibonacci numbers modulo a natural number n is called the Pisano period and is denoted by π (n). The Pisano π (n) periods form the sequence: 1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, ... (sequence A001175 in OEIS)

In particular, the last digits of Fibonacci numbers form a periodic sequence with a period π (10) = 60, the last pair of digits of Fibonacci numbers forms a sequence with a period π (100) = 300, the last three digits with a period π (1000) = 1500, the last four - with a period of π (10,000) = 15,000, the last five - with a period of π (100,000) = 150000, etc.

What is the Pisano period is clear from the table for π (4):

 n | 1 2 3 4 5 6 | 7 8 9 ... F(n) | 0 1 1 2 3 5 | 8 13 21 ... F(n) mod 4 | 0 1 1 2 3 1 | 0 1 1 ...

That is, π (4) = 6, namely: the remnants of dividing the Fibonacci numbers by 4 are repeated with a period of 6.

How to use it to solve the problem think for yourself.

    Obvious simple improvements:

    1. You can replace the taking of the residue by comparing with 10 and subtracting 10 (because the result is guaranteed to be less than 20). In theory, the division operation is more severe.
    2. It is possible to calculate the lookup table (a, b) -> c , which, in theory, is small. But it is unlikely that a double lookup will be significantly faster than a pair of additions / subtractions.
    3. Algorithmic improvement: since the next member of the sequence depends only on the two previous ones, the sequence will always loop. And since there are no more than 100 pairs of digits, a cycle length is no more than 100. Find the cycle length in advance (by a separate program), now the number n can be taken modulo the cycle length.
    4. By combining 2 and 3, you can calculate in advance the answers for n from 0 to 99, and according to 3 this is enough. Total decision for O (1).
    • one
      Regarding pp 3.4 applaud - tutankhamun
    • @tutankhamun: Thank you! ( blushed ) - VladD
    • one
      @VladD here it is, real programming. Regarding paragraph 3, it remains to add - the length of the cycle is not more than 100, one can no longer consider the real one, quite a little. - Lapshin Dmitry
    • @LapshinDmitry: Yeah, you're right. Basically 100 iterations, just wait for it to repeat (0, 1). - VladD

    Raising the matrix

     1 1 1 0

    To the degree of binary construction, taking its elements modulo 10, we can solve this problem for O (logN).

    Even you can not be limited to module 10.

      Here we have already written above, but the best optimization is the use of the matrix, or rather the raising to the power of the number you are looking for. About the implementation can be found on the Habré, there everything on the python is very clear. You can familiarize yourself with the theoretical substantiation in the book of D. Knut, where, for the first time, an explanation of the effectiveness of the solution is given.