Thread: Large Fibonacci

Off topic here, but is that code using .NET features ('managed C++' I think?) Just curious, because I've only seen Int32 and Console:: stuff once or twice before, and I've never been sure where they come from.

Don't use Byte has a type for the array, use a Int32 - that's 4 times less operations between array elements

Code:

 for( int digit = 0; digit < 10000; digit++)

you can shorten this cicle. you never reach the last element in the array (or first).

Code:

for( int digit = 0; digit < 10000; digit++){
    sum = fir[digit] + sec[digit] + carry;
    if(sum == 0)//no need for more calculations - end of number reached
        break;
    su[digit] = sum % 10;
    carry = sum/10;
}

This also aplies to the print and copy functions.

Now for the GREAT tweak !!
You're using 3 arrays !!! very inefficient, then you drag the result around.
Instead use only 2 arrays: the one that keeps the bigger number and the one that keeps the smaller one then calculate them like this

Code:

smaller = smaller + bigger;
//or
f(n) = f(n-2) + f(n-1)

very simple this one

I have a full working source that calculates any number from 0 to 10000. I've done it all in C because it was what Iknew at the time.
To increase it's limit, just change to VECTOR_DIM macro to something bigger.
Oh, and it calculates the number instantly

Code:

#include<stdio.h>

#define SIZE_NUM 1000000000
#define VECTOR_DIM 234//enough to hold fib(10000)

/*MACRO output number*/
#define display_arr(vec)\
            for(i=indfin-1; i>-1; i--){\
				temp=SIZE_NUM/10;\
				if(i!=indfin-1)\
				while(1){\
					if(vec[i]/temp) break;\
					putchar('0');\
					temp/=10;\
				}\
				printf("%d", vec[i]);}
				
int main()
{
	int i=-1, opt;
	int indfin=1, ref=1;
	unsigned int n0[VECTOR_DIM] = {0}, n1[VECTOR_DIM] = {1};
	unsigned int temp;

	scanf("%d", &opt);

	if(!opt)
	printf("The Fibonacci number for 0 is 0");
	else{
		while(i++<opt){/*sum cicle*/
			indfin=0;

			if(ref){
			while(temp = n0[indfin] + n1[indfin]){
				n0[indfin]   = temp%SIZE_NUM;\
				n0[indfin+1] = temp/SIZE_NUM + n0[indfin+1];\
				indfin++;
			}ref=0;}
			else{
			while(temp = n0[indfin] + n1[indfin]){
				n1[indfin]   = temp%SIZE_NUM;\
				n1[indfin+1] = temp/SIZE_NUM + n1[indfin+1];\
				indfin++;
			}ref=1;}
		}
		
		/*	display*/
		printf("The Fibonacci number for %d is ", opt);
		if(ref)  display_arr(n0)
		else   display_arr(n1)
	}
	putchar('\n');
	
	getchar();
	return 0;
}

and for a little description:
i is the cicle controling var, opt is the index of the fib number to calculate, n0 and n1 are the fub numbers calculated, tempo is a temp var used for the sum, ref tells which number is the bigger, indfin stores the index of the final slot used in the array, to limit the sum and display cicles. The display_vec macro already displays the zeros at the left of the number. SIZE_NUM stores the upper limit for each number stored in each array slot. SIZE_NUM has to a multiple of the base for the number representation.. in this case 10.

Code:

The Fibonacci number for 10000 is 
5443837311356528133873426099375038013538918455469
5967026247715841208582865622349017083051547938960
5411738226759780263173843595847511162414391747026
4295916992558633411790606304808979353147610846625
9072759367899150677960088306597966641965824937721
8003814411588410424809979846964873753371800281637
6331778192794110136926275097950980071359671802381
4710669912644214775254478587674568963808002962265
1331113599297627266794414001015758000435107774659
3580536250246170791805922641467900569075232189586
8142367849593880756423483754386342639635970733756
2600989624626687461120417398194048750624437098686
5431562684718619562014612664223271181504036701882
5205314845875817193533529827837800351902529239517
8366894676619179538847124410284639354494846144507
7876252952096188759727288922076853739647586954315
9172434537193611263743926337313005896167248051737
9863063681150030883967495871026195246313524474995
0520419830518716832162328385979462724591977145462
8218399695789223798912199431775469705216131081096
5599506382972612538482420078971090547540284381496
1193046506186617012298328896435273375079278606944
4761853525144421077928045979904561298129423809156
0550330323389196091622366987599227829231918966880
1771857555552099465332012844650237115371514174929
0913104897203455577507196645425232862022019506091
4835852238827110167084330511699421157751512555102
5165593188816404834412955703882547752111157739578
0115868397072602565614824956460538700280331311861
4853998053970315557275296933995860798503815814462
7643385882852953580342485084542644647168153100153
3180479567436396815653326152509571127480411928196
0221488491482843891241785201745073055389287178579
2350941774338333150689823935442198880542933244037
1194867215543576548565499134519271098919802665184
5649278278272129576492402355075955582056475693653
9487331765900020637312657064350970948264971003873
3517477713403319028105575667931789470024118803094
6040343629534719974613922747915497303564126330742
3082405199999610154978466734045832685296038830112
0765629245998136251652347093963049734046445106365
3041636308236692422577614682884617918432247934344
06079917883360676846711185597501

Code:

for( int digit = 0; digit < 10000; digit++){
    sum = fir[digit] + sec[digit] + carry;
    if(sum == 0)//no need for more calculations - end of number reached
        break;
    su[digit] = sum % 10;
    carry = sum/10;
}

This ain't kosher. A very large number might well have an intermediate sum be 0, even though higher places need addition. Your code breaks addition of two such numbers, and it might not even appear now, because I doubt there are such numbers in the Fibonacci sequence.

So it's a trap for the unwary maintainer: "Hey look, we've already got a Bignum class there."