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.
This is a discussion on Large Fibonacci within the C++ Programming forums, part of the General Programming Boards category; Off topic here, but is that code using .NET features ('managed C++' I think?) Just curious, because I've only seen ...
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.
Just Google It. √
(\ /)
( . .)
c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.
The S and curly bracket 0 is just syntax for visuall c++.net. Its has to do with strings and spaces. I will try out your suggestions. Thanks for replying.
Lol. Ladies and Gentlemen I have finished!!!!! My program works! I was able to calculate the 10,000 and 100,000 fibonacci number. However, my program is very slow and inefficient. So I was wondering if you guys can help me make it better. Here is the code, you can run it urself.
Code:#include "stdafx.h" #using <mscorlib.dll> using namespace System; void sumA(Byte[],Byte [],Byte[], int); void copy(Byte [], Byte[]); void print(Byte []); int _tmain() { Byte f[] = new Byte[100000]; Byte s[] = new Byte[100000]; Byte sum[] = new Byte[100000]; f[0]=1; s[0]=1; Console::Write(S"Input N: "); int n =Int32::Parse(Console::ReadLine()); sumA(sum,f,s,n); return 0; } void sumA(Byte su[], Byte fir[], Byte sec[], int nv) { int sum,carry = 0; for( int count = 1; count < nv-1; count ++ ) { for( int digit = 0; digit < 10000; digit++) { sum = fir[digit] + sec[digit] + carry; su[digit] = sum % 10; carry = sum/10; } copy(sec,fir); copy(su,sec); } print(su); } void copy(Byte a[], Byte b[]){ for(int i=0; i<b->Length; i++) b[i] = a[i]; } void print(Byte b[]){ for(int i=b->Length-1; i>=0; i--) Console::Write(S"{0}",b[i].ToString()); }
Don't use Byte has a type for the array, use a Int32 - that's 4 times less operations between array elements
you can shorten this cicle. you never reach the last element in the array (or first).Code:for( int digit = 0; digit < 10000; digit++)
This also aplies to the print and copy functions.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; }
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
very simple this oneCode:smaller = smaller + bigger; //or f(n) = f(n-2) + f(n-1)
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
and for a little description: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; }
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
Last edited by xErath; 05-29-2005 at 01:16 PM.
cool thanks for the the advise I will definitely try to modify the code.
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.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; }
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
That has already considered. Never in the fibonacci sequence you'll find such result, unless you store a very small number in each array element (below 10000). That's why I recomended to use Int32Originally Posted by CornedBee
So it's a trap for the unwary maintainer: "Hey look, we've already got a Bignum class there."
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law