495 - Fibonacci Freeze
Moderator: Board moderators
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.
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
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
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
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
-
- New poster
- Posts: 35
- Joined: Sat Jan 05, 2002 2:00 am
- Contact:
-
- 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
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
-
- 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.
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!
Please help me.
The code is below:
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!!
![:(](./images/smilies/icon_frown.gif)
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");
}
}
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
-
- 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...
![;-)](./images/smilies/icon_wink.gif)
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
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
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)
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)
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
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...
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...