xuanquang1999's blog

Calculating (n-th Fibonacci number) mod (10^9+7) with n <= 10^15 in less than 1 second?
By xuanquang1999, 10 years ago, In English

Is there a way to do this?

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (46)
| Write comment?
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Yes, there is.

→ Reply
»
10 years ago, # |
← Rev. 10   Vote: I like it +21 Vote: I do not like it

Yes, there is. Think about the formula...

Fi = Fi - 1 + Fi - 2 = 2 * Fi - 2 + Fi - 3 = 3 * Fi - 3 + 2 * Fi - 4....

If you keep on with the formula, assuming F0 = 1 and F1 = 1, you'll reach a point where...

(if i is even)

(if i is odd)

Or, generalizing for every i...

Using those formulas and a recursive function with memoization, you can run the algorithm in no time.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The implementation is very short and simple. Check it out here -> Fibonacci

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      i can't understand how it works if u call with fib(n+1) it never meet with base case...plz explain

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        The recursive function doesn't call fib(n+1), it calls fib((n+1) / 2).

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +15 Vote: I do not like it

          ooo sorry i saw wrong,,,that's my eye mistake sorry

          → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    That is interesting.

    Is this for Fibonacchi Numbers only?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      What do you mean? It's a function that calculates the nth Fibonacci number in O(logn).

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Generally we do these things by matrix exponentiation.

        What I meant to ask is whether it is possible for all such problems to find some formula and solve it. Like you did.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it -7 Vote: I do not like it

          Ahhhhh, I see. I don't know about matrix exponentiation. I always found it very hard and never decided to actually study about it.

          I knew Fibonacci numbers could be calculated using matrix exponentiation, but since that's beyond my understanding, I decided to try and find my own method. I did, and I must say I find this method much easier to understand, easier to code and maybe even faster.

          I don't know if there's a general formula for other problems that use matrix exponentiation too. I think that there might some that can be solved by a formula and also many others that can't.

          → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          If you can formulate your number like , you can solve it using matrix exponentiation. This is a nice article about it!

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +16 Vote: I do not like it

            Thanks for mentioning my blog post! I almost forgot that such post exists :P

            → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it -11 Vote: I do not like it

          Always,when you can present your sequence member using lower grade sequence numbers,you can calculate it in same way,as describe tenshi_kanade

          for example: if F(n)=F(n/3)*F(n/3+1)+x you can calculate in O(2^log(3,n))

          → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I instantly thought of Matrix Exponentiation when I read the statement...

    But this method is even easier and prettier... m(_ _)m

    → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

By the way can anyone say how to calculate Pisano period fast?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is formulae for prime powers. So you need only factorize modulo.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What formulae?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        For p=5^k pisano period is a divisor of 5^k; For p quadratic residue modulo 5 pisano period is a divisor of (p-1)p^{k-1}; For p quadratic nonresidue modulo 5 pisano period is a divisor of 2(p+1)p^{k-1}

        → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i am searching for pisano period (1e9 + 7) any idea?

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      $$$2e9 + 16$$$

      → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      As zeliboba mentioned above, the Pisano period is a divisor of $$$2(p+1)$$$, since $$$p=10^9+7$$$ is not a quadratic residue modulo $$$5$$$. Then, you can use standard algorithms for finding a multiplicative order of a number. Specifically, to check if the period is a divisor of $$$k$$$, you check that $$$F_k=F_0$$$ and $$$F_{k+1} = F_1$$$.

      → Reply
»
10 years ago, # |
← Rev. 6   Vote: I like it +1 Vote: I do not like it

I'm not sure about this, but you may test it. The formula for the n-th Fibonacci number is

If we write the pow function to be fast modulo exponentiation this gives us O(logN) complexity.

UPD: This function might not work with double arguments, so this is hardly a right solution.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    This formula is applicable iff 5 is a quadratic residue modulo p and p is prime. We can check it using Euler's criterion.

    For example, let's take p = 109 + 9. Euler's criterion is true: . That means we can find a square root of 5 modulo p.

    Let's find it. I prefer Wolfram Alpha: powermod[5,1/2,10^9+9] = 383008016. We can insert this number into your formula, and the final result is

    Fn = 276601605·(691504013n - 308495997n)

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So this actually works?

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Still can't understand where did you get all the numbers in the formula.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        They do this by finding some number x such that . This is like the in . It turns out that for p = 109 + 9, this x actually exists and is x = 383008016, which you can find out using Wolfram Alpha. They then substitute 383008016 for in your formula and simplify to get those numbers.

        → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 12   Vote: I like it +21 Vote: I do not like it

      If I am not mistaken, you can do same thing for all modules not equal to 5 by adding roots of x2 - 5 to if 5 is not quadratic residue . I mean, calculate value of the same formula on numbers of type a + bx, where and with rules of addition and multiplication similar to complex numbers (result will always be free of "imaginary" part):

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I guess you are right. The thing is the expression never contains square root of five. So we don't really care whether it even exists. It is nice if it does, but it is totally unnecessary. For example my program (link) can calculate Fibonacci numbers modulo 3^6*7^2=35721. And there is no x such that x*x=5 mod 35721. The trick is to work with numbers, similar to complex, with only one difference that i*i=5, not -1.

        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Nevertheless you can actually use this formula to calculate Fibonacci numbers modulo any odd number. You just need to calculate it not with the help of doubles, but numbers of the form . They have properties similar to complex numbers. For example the product of two numbers equals .

    And because of special structure of this formula, the answer is , where Im takes the part right next to square root of five (I called it so because of similarity with complex numbers). So you only need to be able to divide by two and that can be done modulo any odd number.

    → Reply
»
10 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Matrix exponentiation

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes. See this page.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You came and gave a problem: Calculate Fib(n)=Fib(n-1)+Fib(n-2) % M in O(logN). Cool.

Now I come and give you a challenge: SuperFib(n)=A*SuperFib(n-1)+B*SuperFib(n-2)+C*SuperFib(n-3) % M (SuperFib(0), SF(1), SF(2) are given, as well as A, B and C). Solve it in O(logN) time. This requires matrix exponential. If you want to learn something great.

→ Reply
»
8 years ago, # |
  Vote: I like it -34 Vote: I do not like it

You could use matrix multiplication here, to get to the Nth number in log(N) time. Here is a video tutorial explaining the same: Fibonacci Numbers using Matrix Multiplication

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it -74 Vote: I do not like it

.

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it -20 Vote: I do not like it

.

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

idk

→ Reply