## 10229 - Modular Fibonacci

Moderator: Board moderators

caxibrema
New poster
Posts: 5
Joined: Sat Oct 04, 2003 5:25 pm
Location: Brazil
Contact:
No the algorithm i used, each time divides n by 2 so is clearly log2(n)...

But i didt got the idea u used in the problem... do u process anything before and use it?
Best regards,
S

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
Maarten wrote:Excuse me, that should be O(m), and not O(log(m)).. what I meant was O(log(2^m))....
That means I was talking about MY algorithm, and it means it's O(m) and not O(log(n)). Notice the difference between m and n please.

And yes, I precalculated fibonacci numbers up to 3*2^19

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

### 10229 help!

[cpp]
get AC now! [/cpp]
Last edited by oulongbin on Tue Oct 05, 2004 4:51 am, edited 1 time in total.

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
Your output is not quite correct for all inputs.
Try for example:

Input:

19000 19
123456 19

Correct output:

227947
64256

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

### Oh..

Did you except that integer would be overflow?

64bit integer cannot save Fibonacci(2147483647) ....

Then you can use (a * b + c) % d = ((a % d) * (b % d) + c % d) %d

So, try modular operating in "O(logN) Fibonacci" Code.

You can get correct answer without using "BigInteger".

Thank You. Sorry For My Poor English.. oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China
thank you very much!
i got AC used unsigned long long. CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Hi, is there any equation to find nth fibonacci? i think it will be stupid to find fibonacci(2147483647) even though i use modular arithematic by adding the previous two fibonacci numbers....there must be a formula, but unfortunately i dont know it. can anyone help? Jalal : AIUB SPARKS

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
You can either solve this problem by the Q-matrix method (google for it).

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
My C++ program runs in 0.500 secs on this problem.

How do some people have 0.000 on this problem.

Is that possible?

I mean that in this problem we at least need some
serios pre-calculation. I do it in O (K), where K = 3*2^19.

Even if I do it in O ( log (K) ) / I think I read this is possible /,
I am sure I won't get that much of a speed-up ?!

So... How is 0.000 secs running time possible on this problem ?

Or... ? Am I misunderstanding something ?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Sedefcho wrote: So... How is 0.000 secs running time possible on this problem ?
It is well-known and easy to prove by induction, that n-th powers of the
matrices [[0,1],[1,1]] and [[1,1],[1,0]] are:

[[0, 1], [1, 1]]^n = [[F(n-1), F(n)], [F(n), F(n+1)]]
[[1, 1], [1, 0]]^n = [[F(n+1), F(n)], [F(n), F(n-1)]]

(where F(n) is the n-th fibonacci number)

Since matrix multiplication is associative, to compute n-th matrix power
you can use the standard right-to-left exponentiation algorithm, with
all numbers computed modulo 0xFFFFF.
X^(2k) = (X*X)^k, X^(2k+1) = X * (X*X)^k

My own implementation of the above scheme ran 0.002 sec.

If you don't like matrices etc, you can also try to use the identities:

F(2n) = F(2n+1) - F(2n-1)
F(2n+1) = 4 * F(n)^2 - F(n-1)^2 + 2 * (-1)^n
F(2n-1) = F(n)^2 + F(n-1)^2

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Thanks for the hints. I will try them when I have some more
time to play with the Fibonacci Sequence. Thanks.

sahand
New poster
Posts: 19
Joined: Sat Mar 12, 2005 5:56 pm
Contact:

Hi guys, this is my code for 10229, and I just can't understand why I get WA's. It uses Q-matrix. It gives correct outputs for the samples and for anything else I checked. It would be great if someone could tell me what i'm doing is wrong. Thanks

------------ Problem solved thanks to mf -----------
What a stupid mistake it was, just missing f=0
I couldn't possibly expect that they would put n=0 in the input..
anyway. I got AC in 0:00.004 Last edited by sahand on Sun Mar 13, 2005 3:24 am, edited 2 times in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
You missed one case:
F = 0

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

### to achieve 0.00000000

USE BITWISE TO ACHIEVE 0.000
hope it helps   good luck regards
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm

### 10229 Modular Fibonacci

Hi,
I'm having trouble with this task. I roamed througout the forum and figured out that I have to use modular arithmetic and qmatricies.