495 - Fibonacci Freeze

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

Moderator: Board moderators

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

495 - Fibonacci Freeze

Post by edmanm » Wed Feb 27, 2002 8:29 am

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:

Post by pochmann » Wed Feb 27, 2002 9:55 am

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:

Post by pochmann » Wed Feb 27, 2002 8:55 pm

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:

Post by Alexander Denisjuk » Sun Mar 17, 2002 11:04 am

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:

Post by Stefan Pochmann » Sun Mar 17, 2002 11:26 am

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:

Post by Alexander Denisjuk » Thu Mar 21, 2002 5:19 pm

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
Location: Dhaka, Bangladesh
Contact:

TL!! in 495

Post by popel » Tue Apr 23, 2002 10:25 am

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!
Please help me.

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Apr 23, 2002 11:54 am

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:

Post by Stefan Pochmann » Thu Apr 25, 2002 9:36 am

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

Post by sweko » Thu Apr 25, 2002 3:29 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
Location: Dhaka, Bangladesh
Contact:

Thanks to Everyone

Post by popel » Fri Apr 26, 2002 9:41 am

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

Post by corecode » Thu May 02, 2002 1:34 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:

Post by Stefan Pochmann » Thu May 02, 2002 7:35 am

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

Post by Betovsky » Thu Jun 06, 2002 6:10 pm

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

Post by Betovsky » Thu Jun 06, 2002 8:20 pm

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

Post Reply

Return to “Volume 4 (400-499)”