Large Fibonacci

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

  1. #16
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    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.

  2. #17
    Registered User
    Join Date
    Apr 2005
    Posts
    41
    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.

  3. #18
    Registered User
    Join Date
    Apr 2005
    Posts
    41

    All done!!!!!!!!

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

  4. #19
    #include<xErath.h> xErath's Avatar
    Join Date
    Jun 2004
    Posts
    722
    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
    Last edited by xErath; 05-29-2005 at 12:16 PM.

  5. #20
    Registered User
    Join Date
    Apr 2005
    Posts
    41
    cool thanks for the the advise I will definitely try to modify the code.

  6. #21
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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.
    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

  7. #22
    #include<xErath.h> xErath's Avatar
    Join Date
    Jun 2004
    Posts
    722
    Quote Originally Posted by CornedBee
    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.
    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 Int32

  8. #23
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. fibonacci prime
    By dbzx in forum C Programming
    Replies: 5
    Last Post: 04-17-2009, 11:13 AM
  2. [Large file][Value too large for defined data type]
    By salsan in forum Linux Programming
    Replies: 11
    Last Post: 02-05-2008, 03:18 AM
  3. large Fibonacci numbers
    By kocika73 in forum C Programming
    Replies: 3
    Last Post: 09-22-2005, 11:10 AM
  4. Representing a Large Integer with an Array
    By random_accident in forum C Programming
    Replies: 3
    Last Post: 03-03-2005, 07:56 PM
  5. Representing a Large Integer with an Array
    By random_accident in forum C++ Programming
    Replies: 3
    Last Post: 03-03-2005, 11:23 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21