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

DemonCris
New poster
Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan
I sent my pro and get a runtime error:
Floating point exception

What does it mean???

<font size=-1>[ This Message was edited by: DemonCris on 2002-02-25 14:08 ]</font>

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
It means that you get "division by zero"......

Andrey Popyk
New poster
Posts: 6
Joined: Wed Jan 16, 2002 2:00 am
Location: Ukraine
Contact:

### 10229 - Modular Fibonacci

There is my programm.
I cannot find where it fails.

// programm compute
// |1 1|^(N-1)
// |1 0|
// with modular arithmetic

#include <iostream.h>
#include <math.h>

long N,L;
long double i,j,k,h,LL;

void mathpow(long N)
{ long t;
if (N>1)
{
mathpow(N/2);
//next 2 lines is M=M*M;
t=k*j;
k=i*k+k*h; j=i*j+j*h; i=i*i+t; h=h*h+t;
i=fmod(i,LL); j=fmod(j,LL); k=fmod(k,LL); h=fmod(h,LL);
}
if (N%2)
{
//next 2 lines is M=M*{{1,1},{1,0}}
t=i+j; j=i; i=t;
t=k+h; h=k; k=t;
i=fmod(i,LL); j=fmod(j,LL); k=fmod(k,LL); h=fmod(h,LL);
}
}

{ long i;
cin>>N>>L;
for(i=1,LL=1;i<=L;i++,LL*=2);
return !cin.eof();
}

void Solve()
{
if(N==0) { cout<<0<<endl; return; }
i=1; j=0; k=0; h=1;

mathpow(N-1);
cout<<i<<endl;
}

int main()
{
return 0;
}

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
at a rough scan on your code, what i think is, there seems not a need to use long double, you can make it to int, or long long. then, your program may be better, at least need not worry about floating point error. though i cannot tell you whether it will get AC

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

### 10229 (fibonacci modular)

why i got wa?
any tricky there?
i find the repetends for 0<=m<=20 and store them..

[cpp]
#include <stdio.h>

long data[3145727];
long a[21], sp[21];

int main()
{
long n, m, q;
long f1, f2, f3;
long len;

a[0] = 1; sp[0] = 0; data[0] = 0;
len = 1;
for (m = 1; m <= 20; m++) {
q = 1 << m;
sp[m] = len;
data[len++] = 0;
data[len++] = 1;
data[len++] = 1;
f1 = 1;
f2 = 1;
a[m] = 1;
while (f1 != 0 || f2 != 1) {
a[m]++;
f3 = (f1 + f2) % q;
data[len++] = f3;
f1 = f2;
f2 = f3;
}
}

while (scanf("%ld %d", &n, &m) == 2) {
n %= a[m];
printf("%ld\n", data[sp[m] + n]);
}

return 0;
}
[/cpp]

udvat
New poster
Posts: 29
Joined: Thu Aug 07, 2003 9:56 pm

### 10229..............hints

am a novice programmer.i tried to solve this problem for many times,but failed. wud anyone plz give me some hints????

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Look up Q-Matrix (I think it's called..)

caxibrema
New poster
Posts: 5
Joined: Sat Oct 04, 2003 5:25 pm
Location: Brazil
Contact:
Well i tryed also do make this one but i've got a time limit exceeded, i tried the biggest case (2^31 - 1) and in my computer runned in 2s, what's the problem???

#include <stdio.h>

unsigned int m, n;
unsigned const int mascara[20] = {0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287};

inline int fib() {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
unsigned int fibA, fibB, fibTEMP;

fibA = 0;
fibB = 1;

for (register unsigned int i = 2 ; i <= n ; i++) {
fibTEMP = fibA + fibB;
fibA = fibB;
fibB = fibTEMP;
}

return fibB;
}

}

void processar() {
printf("%u\n", fib()&mascara[m]);

}

void main() {
while (scanf("%u%u", &n ,&m) == 2) {
processar();
}
}
Best regards,
S

caxibrema
New poster
Posts: 5
Joined: Sat Oct 04, 2003 5:25 pm
Location: Brazil
Contact:
Well i tryed also do make this one but i've got a time limit exceeded, i tried the biggest case (2^31 - 1) and in my computer runned in 2s, what's the problem???

Maybe this is more clear than the above...
[cpp]
#include <stdio.h>

unsigned int m, n;
unsigned const int mascara[20] = {0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287};

inline int fib() {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
unsigned fibA, fibB, fibTEMP;

fibA = 0;
fibB = 1;

for (register unsigned int i = 2 ; i <= n ; i++) {
fibTEMP = fibA + fibB;
fibA = fibB;
fibB = fibTEMP;
}

return fibB;
}

}

void processar() {
printf("%u\n", fib()&mascara[m]);

}

void main() {
while (scanf("%u%u", &n ,&m) == 2) {
processar();
}

}[/cpp]
Best regards,
S

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
for (register unsigned int i = 2 ; i <= n ; i++) {

of course it's going to TLE... try finding another method..

caxibrema
New poster
Posts: 5
Joined: Sat Oct 04, 2003 5:25 pm
Location: Brazil
Contact:
Look don't say that is obviously going to be TLE, my algorithm runs at O(n), as the maximum input is 2^31 -1 so the max running time is:

T = (2^31-1) /(10^9) ~ 2 so its 2 seconds aproximately.

Talking about algorithms i only know calculating fibonacci with the obscure formula
Fn = 1/sqrt(5)*[ 1/2*(1+sqrt(5)^n - 1/2*(1-sqrt(5)^n)];

but i thing its inapropriate...

another way i thought was making preprocessing of some values ex:
storing fibonnaci of 100,101,1000,1001,10000,10001, ... something like this... and using for saving time, e.g. if i wanted to calculate the fibonacci of 1010 i was going to start to calculate in 1000...
Best regards,
S

caxibrema
New poster
Posts: 5
Joined: Sat Oct 04, 2003 5:25 pm
Location: Brazil
Contact:
i've found an algorithm that runs in O(log(n)) and i've got an AC for anyone who is curious go to
http://www.ics.uci.edu/~dan/class/161/notes/7/Fib.html

it ran in 0.02 s
Best regards,
S

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Sure, that case might be two seconds, but what if someone give you something like:

2000000000
2000000000
2000000000
2000000000
2000000000
2000000000
2000000000
2000000000

and you're done.

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
My algorithm runs in O(2^20) time for all test cases together, and then O(1) for each test case, by making use of the fact that F(n) mod (2^m) is a periodic sequence in n, which period 3*2^{m-1}. I suppose I can improve the algorithm to O(log(m)) for each test case, haven't tried this yet though...

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
Excuse me, that should be O(m), and not O(log(m)).. what I meant was O(log(2^m))....