495 - Fibonacci Freeze

[edmanm]

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]

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]

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]

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]

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]

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]

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]

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]

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]

I constantly got TL despite any "optimisations" i made, until i just made a table[1..5000], and it worked on the first try

[popel]

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]

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]

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]

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]

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