10229 - Modular Fibonacci

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

caxibrema
New poster
Posts: 5
Joined: Sat Oct 04, 2003 5:25 pm
Location: Brazil
Contact:

Post by caxibrema » Sun Oct 05, 2003 2:47 pm

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

Post by Maarten » Sun Oct 05, 2003 3:52 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!

Post by oulongbin » Fri Oct 01, 2004 7:37 am

I don't know why my method is wrong,please help me,thanks.
[cpp]
get AC now! :D
[/cpp]
Last edited by oulongbin on Tue Oct 05, 2004 4:51 am, edited 1 time in total.

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Fri Oct 01, 2004 3:37 pm

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..

Post by wook » Sat Oct 02, 2004 1:20 am

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. :D
Sorry For My Poor English.. :)

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

Post by oulongbin » Tue Oct 05, 2004 4:50 am

thank you very much!
i got AC used unsigned long long.
:D

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Wed Dec 29, 2004 3:00 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:

Post by Larry » Wed Dec 29, 2004 6:47 pm

You can either solve this problem by the Q-matrix method (google for it).

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Sat Feb 26, 2005 5:35 am

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:

Post by mf » Mon Feb 28, 2005 4:55 am

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

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Mon Feb 28, 2005 11:32 am

Thanks for the hints. I will try them when I have some more
time to play with the Fibonacci Sequence. Thanks.

User avatar
sahand
New poster
Posts: 19
Joined: Sat Mar 12, 2005 5:56 pm
Location: Halifax, Nova Scotia, Canada
Contact:

10229 - WA - please help

Post by sahand » Sun Mar 13, 2005 2:21 am

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]=0
I couldn't possibly expect that they would put n=0 in the input..
anyway. I got AC in 0:00.004 :D
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:

Post by mf » Sun Mar 13, 2005 3:14 am

You missed one case:
F[0] = 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

Post by I LIKE GN » Fri Sep 02, 2005 2:23 am

USE BITWISE TO ACHIEVE 0.000
hope it helps :P :lol: :lol:
good luck :wink:
regards
RSS
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

Post by sklitzz » Thu May 25, 2006 12:38 pm

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.
I know what modular arithmetic is but I never heared about q matricies, where can I find a good implementation and explanation about this. I already googled but couldn't find anything satisfactory.

TIA

Post Reply

Return to “Volume 102 (10200-10299)”