### xuanquang1999's blog

By xuanquang1999, 5 years ago, ,

Is there a way to do this?

• +11

 » 5 years ago, # |   +1 Yes, there is.
 » 5 years ago, # | ← Rev. 10 →   +21 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.
•  » » 5 years ago, # ^ |   0 The implementation is very short and simple. Check it out here -> Fibonacci
•  » » » 4 years ago, # ^ |   -7 i can't understand how it works if u call with fib(n+1) it never meet with base case...plz explain
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +1 The recursive function doesn't call fib(n+1), it calls fib((n+1) / 2).
•  » » » » » 4 years ago, # ^ |   +15 ooo sorry i saw wrong,,,that's my eye mistake sorry
•  » » 5 years ago, # ^ |   +5 That is interesting.Is this for Fibonacchi Numbers only?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 What do you mean? It's a function that calculates the nth Fibonacci number in Unable to parse markup [type=CF_TEX].
•  » » » » 5 years ago, # ^ |   0 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.
•  » » » » » 5 years ago, # ^ |   -7 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.
•  » » » » » 5 years ago, # ^ |   +16 If you can formulate your number like , you can solve it using matrix exponentiation. This is a nice article about it!
•  » » » » » » 5 years ago, # ^ |   +16 Thanks for mentioning my blog post! I almost forgot that such post exists :P
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   -11 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))
•  » » » » » » 5 years ago, # ^ |   0 So we don't actually need matrix exponentiation for such kind of problems? :P
•  » » » » » » » 5 years ago, # ^ |   0 yes,we don't
•  » » 5 years ago, # ^ |   +5 I instantly thought of Matrix Exponentiation when I read the statement...But this method is even easier and prettier... m(_ _)m
 » 5 years ago, # |   +5 By the way can anyone say how to calculate Pisano period fast?
•  » » 5 years ago, # ^ |   0 There is formulae for prime powers. So you need only factorize modulo.
•  » » » 5 years ago, # ^ |   0 What formulae?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 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}
 » 5 years ago, # | ← Rev. 6 →   +1 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.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +5 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 isFn = 276601605·(691504013n - 308495997n)
•  » » » 5 years ago, # ^ |   0 So this actually works?
•  » » » 5 years ago, # ^ |   0 Still can't understand where did you get all the numbers in the formula.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 5 years ago, # ^ | ← Rev. 12 →   +21 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):
•  » » » » 5 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ |   +13 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.
 » 5 years ago, # |   +15