## 495 - Fibonacci Freeze

Moderator: Board moderators

edmanm
New poster
Posts: 13
Joined: Sat Feb 09, 2002 2:00 am

### 495 - Fibonacci Freeze

I'm looking for any tips on #495. Clearly, the 5000th Fibonacci number is going to be huge, so what data type can store that number? Any tricks to calculating it quickly? Any help would be appreciated.

pochmann
New poster
Posts: 28
Joined: Sat Jan 26, 2002 2:00 am
Contact:
In Java I'd go for BigInteger, but that's currently disabled.

So I'd go for char arrays or int arrays. In char arrays, you'd usually represent a number as a string, one char per digit. It makes things easier to store the number reversed, so number[0] holds the last digit.

In this problem you only have addition, so you can use an int array and store the numbers not in base 10, but in base 1000000000. This will speed it up roughly by a factor of 9.

For multiplication of big numbers you can go up to 10000 as the base, because the result of two "digits" will still fit in an integer that way.

Since we usually use base 10, you should always choose 10^i as base with some integer i, since converting between base 10 and yours is easy this way.

Stefan

pochmann
New poster
Posts: 28
Joined: Sat Jan 26, 2002 2:00 am
Contact:
I think in newer Java versions, BigInteger is implemented in 100% pure Java, so one could simply copy&paste its sourcecode into his/her own program.

If you use a base as small as 10000, a short[] would also suffice, doesn't have to be an int[]. Maybe it's not only smaller but also faster, because it's better for the cache.

Stefan

Alexander Denisjuk
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:
I have written a program and obtained WA. On the other hand I calcucated all the Fibonacci numbers form 0 to 5000 in Maple. My program gives the same answer. Is there something wrong in Mapple? Does anyone who got Accepted compared his answers with Maple or mathematica results?

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
I think it's more likely that your program contains a bug. For example, did you try decreasing numbers in the input?

When you're sure that your program can compute every single value correctly, sometimes a bug is that certain consecutive requests make you fail. If this doesn't help, I can have a look at it: pochmann(AT)gmx.de

Alexander Denisjuk
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:
Yes, you are right. If fact my program had long line, which was cut by Outlook. The typical mistake for beginers. Now it is accepted. I used simple addition. The only optimization I provided was the following: If the next number is greater than currently copmuted one, I start from it, not form the first Fib.

popel
New poster
Posts: 33
Joined: Fri Mar 15, 2002 2:00 am
Contact:

### TL!! in 495

I cannot realize what the problem is.

At first I wrote it with char Array,which took about 2 seconds
to calculate the fibonacci 5000.

When I posted it got Time Limit Exceeded.Then I made with int array with
BASE 1000000000.This is a quite fast process which shows no delay in our
mind to calculate fibonaccoi 5000 or such ones.

But, Again TL!!

What can I do!

The code is below:

Code: Select all

``````#include<stdio.h>

#define MAX 116
#define BAS 1000000000

void zeroarray(int *ar);

void zeroarray(int ar[MAX+1]){
int i;
for(i=0;i<=MAX;i++) *(ar+i)=0;
}

void main(){
int f1[MAX+1],f0[MAX+1],fr[MAX+1];
int *ff1,*ff0,*ffr,*temp;
int fn,i,inter,carry,c;
while(scanf("%d",&fn)==1){
if(fn!=0){
ff1=f1;ff0=f0;ffr=fr;

zeroarray(ff0);
zeroarray(ff1);

*(ff1+MAX)=1;

carry=0;
for(c=2;c<=fn;c++){
for(i=MAX;i>=0;i--){
inter=*(ff0+i)+*(ff1+i)+carry;

if(inter>(BAS-1)){

inter=inter%BAS;
carry=1;
}
else
carry=0;
*(ffr+i)=inter;

}

temp=ff0;
ff0=ff1;
ff1=ffr;
ffr=temp;
}
for(i=0;i<=MAX;i++){
if((*(ff1+i))!=0)break;
}
printf("The Fibonacci number for %d is %d",fn,*(ff1+i));
for(c=i+1;c<=MAX;c++)printf("%.9d",*(ff1+c));

printf("\n");
}
else printf("The Fibonacci number for 0 is 0\n");
}
}``````

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Why do you calculate all the fibonacci numbers again and again for each input? You should precalculate them and store them in an array, then you won't get TLE.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Furthermore, you add over the full array the whole time, even though most of it will be zero most of the time. And, if the current number is larger than the previous one, then you don't have to start all over again. And one could also try going backwards in the sequence, subtracting But I agree with Adrian, I'd precalculate everything...

sweko
New poster
Posts: 7
Joined: Fri Apr 19, 2002 4:05 pm
I constantly got TL despite any "optimisations" i made, until i just made a table[1..5000], and it worked on the first try
SWeko has spoken

popel
New poster
Posts: 33
Joined: Fri Mar 15, 2002 2:00 am
Contact:

### Thanks to Everyone

Thank you ,Everyone.
Yes,I got accepted.Nothing of the optimizations were needed.
I think the name of the problem 'fibonacci freeze' says it by the freeze
word as prestored elements.

-Md. Tanvir Al Amin

corecode
New poster
Posts: 1
Joined: Thu May 02, 2002 1:22 am
i've written code that runs here in 0.120 to calculate all numbers. somehow my submissions need 3.200 on the judge.

how is that? i think the judge must be broken somehow.

or is it my input loop? i don't suspect tho:

[cpp]
int n;
while (std::cin >> n) {
std::cout << "The Fibonacci number for " << n << " is " << fib(n).tostring() << std::endl;
}
[/cpp]

ps: please don't tell me to precalculate as i already do so (in some way)

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
If you want to send me your code, then I can test it a bit. Otherwise, with just the info you gave so far, it's really hard to tell.

Betovsky
New poster
Posts: 26
Joined: Wed Jun 05, 2002 7:30 pm
Location: Portugal
yes i know is a huge number
but could some1 say whats the fibo to the 5000
just to compare with mine, cause it gives w.a. to me

Thx...

Betovsky
New poster
Posts: 26
Joined: Wed Jun 05, 2002 7:30 pm
Location: Portugal
hmmm i was comparing values with the prog of a friend that was accepted
and for num 100.
mine was : 354224848179261915072
and his was: 354224848179261915075

only 3 of difference.
and he use the base techinc
and i use long doubles, does any1 know whats the prob of using it
cause this is belong my knowledge...

Thx...