Page **1** of **4**

Posted: **Mon Feb 25, 2002 3:05 pm**

by **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>

Posted: **Wed Feb 27, 2002 1:09 pm**

by **..**

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

### 10229 - Modular Fibonacci

Posted: **Wed May 29, 2002 1:10 pm**

by **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;

}

Posted: **Sun Jun 16, 2002 4:23 pm**

by **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

### 10229 (fibonacci modular)

Posted: **Fri Jun 06, 2003 5:28 am**

by **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]

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

Posted: **Sat Aug 09, 2003 3:28 pm**

by **udvat**

am a novice programmer.i tried to solve this problem for many times,but failed.

wud anyone plz give me some hints????

Posted: **Sun Aug 10, 2003 4:38 am**

by **Larry**

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

Posted: **Sat Oct 04, 2003 6:00 pm**

by **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();

}

}

Posted: **Sat Oct 04, 2003 6:02 pm**

by **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]

Posted: **Sat Oct 04, 2003 10:58 pm**

by **Larry**

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

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

Posted: **Sat Oct 04, 2003 11:27 pm**

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

Posted: **Sun Oct 05, 2003 12:10 am**

by **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

Posted: **Sun Oct 05, 2003 4:40 am**

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

Posted: **Sun Oct 05, 2003 12:25 pm**

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

Posted: **Sun Oct 05, 2003 12:27 pm**

by **Maarten**

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