10229 - Modular Fibonacci

[DemonCris]

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>

[..]

It means that you get "division by zero"......

[Andrey Popyk]

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);
}
}

int ReadData()
{ 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()
{
while(ReadData()) Solve();
return 0;
}

[wyvmak]

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]

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]

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

[Larry]

Look up Q-Matrix (I think it's called..)

[caxibrema]

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();
}
}

[caxibrema]

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]

[Larry]

for (register unsigned int i = 2 ; i <= n ; i++) {

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

[caxibrema]

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

[caxibrema]

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

[Larry]

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]

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]

Excuse me, that should be O(m), and not O(log(m)).. what I meant was O(log(2^m))....