Large Fibonacci

This is a discussion on Large Fibonacci within the C++ Programming forums, part of the General Programming Boards category; Hello I posted this topic before but I want to try out a specific approach. I need to calculate fibonacci ...

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    41

    Large Fibonacci

    Hello I posted this topic before but I want to try out a specific approach. I need to calculate fibonacci 10000 its reprinted in all its glory for you below:

    Code:
    33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
    Thats a huge number. Rather than using a big number library I was wondering if I could store these digits in an array. If this is possible please let me know. If it is i am not sure how to accomplish it yet lol. But any suggestions welcome.

  2. #2
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    Sure is, I'm pretty sure you can use an array of any type you want other than float or double or long double. The best ones to use will probably be char or unsigned char, but it's up to you. Since finbonacci only requires addition, it shouldn't be too difficult to write a routine that does long addition, using the elements of each array as the ones/tens/etc. digits.

    However, unless you want to just use huge arrays and hope they're big enough to hold your largest number, you'll need to use dynamic memory, which can get unnecessarily messy. As such, if at all possible (i.e. it's allowed, and you know about them or are willing to read up about them on this site's tutorials), I highly recommend you use either std::string or std::vector<char> or std::vector<unsigned char> instead of an array.

    Good luck
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  3. #3
    Hardware Engineer
    Join Date
    Sep 2001
    Posts
    1,398
    I'm pretty sure that the big number libraries also use arrays(or vectors). The detalis could be hidden from you, but there's really no other way to do it. The hard thing about big numbers isn't so much storing them... the tricky part is the mathmematical operations. You need special functions and/or you need to overload the operators. The big-number math functions are the most valuable part of the big number library!

    If this is a homework assignment, there should be some hints from your studies/book/lecture about to approach the assignment. Maybe you can ask your instructor for a hint... You are probably not supposed to use a big number library.

    Maybe this is a "trick" assignment designed to show you (or remind you of) the limits of your system. (???) The first time I heard of Fibonacci was in an example of recursion. I seem to remember the book said you could overflow the stack by calling the function too many times.
    Last edited by DougDbug; 05-25-2005 at 05:17 PM.

  4. #4
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    >>I'm pretty sure that the big number libraries also use arrays
    Hmm, that would probably be simplest to implement, and might be more efficient speed-wise.. but I would imagine that the possibility is still there that they store/manipulate numbers in binary using bitwise operations or whatnot? In terms of memory usage, it would hold 25.6^n times as large a number in the same space as if you used arrays (n == size in bytes).
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  5. #5
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    Using an array of unsigned char types and actually using the full binary representation of the number (as opposed to trying to force a decimal representation) is certainly the most efficient in terms of storage space and speed.

    Also, if all you need this for is to compute large Fibonacci numbers, the only operation you will need is addition. This is rather nice, because you know that the length in (digits/bits/etc) of the sum will be at most one bit/digit/etc more than your largest operand, which will make the coding less messy.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Unless you want to implement the constant-time direct Fibonacci computation.

    The Wikipedia entry for Fibonacci numbers explicitely mentions a good approach for bignum libraries:
    http://en.wikipedia.org/wiki/Fibonacci_number
    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. #7
    Registered User
    Join Date
    Apr 2005
    Posts
    41
    Wow thanks for the interests guys I will keep ur suggestions in mind. When i finish I will post my code here for yall to check out. Thanks again for the input.

  8. #8
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    I once had this code nicely obfuscated at flashdaddee.
    Code:
    #include <stdio.h>
    #include <string.h>
    
    #define SIZE 4096
    
    char A[SIZE] = "0";
    char B[SIZE] = "1";
    char C[SIZE];
    
    int main(void)
    {
       int i = 2, carry = 0;
       printf("fibonacci(0) = %s\n", A);
       printf("fibonacci(1) = %s\n", B);
       while ( i <= 10000 )
       {
          char *a = A, *b = B, *c = C;
          for ( ;; )
          {
             int sum = 0;
             if ( *a )
             {
                sum += *a - '0';
                ++a;
             }
             if ( *b )
             {
                sum += *b - '0';
                ++b;
             }
             sum += carry;
             carry = sum > 10;
             if ( !sum && !*a && !*b )
             {
                break;
             }
             else if ( sum > 9 )
             {
                carry = 1;
                sum -= 10;
             }
             else
             {
                carry = 0;
             }
             *c++ = sum + '0';
             if ( c >= &C[sizeof(C)] )
             {
                puts("too big");
                return 0;
             }
          }
          *c = '\0';
    
          printf("fibonacci(%d) = ", i++);
          while ( --c >= C )
          {
             putchar(*c);
          }
          putchar('\n');
    
          strcpy(A,B);
          strcpy(B,C);
       }
       fflush(stdout);
       return 0;
    }
    [edit]Works best if output is piped to a file.
    [edit too]The file ends up about 10,650,846 bytes.
    Last edited by Dave_Sinkula; 05-25-2005 at 09:42 PM.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  9. #9
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    Code:
    carry = sum > 10;
    ...
    >>else if ( sum > 9 )
    {
        carry = 1;
    It looks to me like the carry = 1; can be taken out, and the sum > 10 should be sum > 9?
    Code:
    else
    {
        carry = 0;
    }
    Similarly, this seems to be unnecessary.
    Code:
    if ( *a )
    Doesn't this assume that all elements past the end of the string are '\0'? I'm not sure that assigning an initial string to A and B automatically zeroes all other elements.

    Otherwise, that seems to do the job very nicely with fixed-length arrays
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  10. #10
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    >It looks to me like the carry = 1; can be taken out, and the sum > 10 should be sum > 9?
    >Similarly, this seems to be unnecessary.

    Ya know, it's been so damn long that I've been trying to figure this code out since I posted it.

    [edit]You are right. That section might be written like this.
    Code:
             sum += carry;
             if ( !sum && !*a && !*b )
             {
                break;
             }
             carry = sum > 9;
             if ( carry )
             {
                sum -= 10;
             }
             *c++ = sum + '0';
    The *a part though checks to see whether the first number is shorter (in digits) than the second.
    [/edit]

    >Doesn't this assume that all elements past the end of the string are '\0'? I'm not sure that assigning an initial string to A and B automatically zeroes all other elements.

    That I know -- it does.

    >Otherwise, that seems to do the job very nicely with fixed-length arrays

    Thank you.

    [I still gotta try to figure this code out though.
    One thing I think I figured out is that the strings are stored "backwards".]
    Last edited by Dave_Sinkula; 05-26-2005 at 08:16 PM. Reason: Late 'reply' on post I took a bit off topic.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  11. #11
    Registered User
    Join Date
    Apr 2005
    Posts
    41
    Alright guys this is my first attempt at it. I am a begginner and my logic is probably flawed but before I continue can you please look this over. I also cant seem to fix this error message that says error C2064: term does not evaluate to a function taking 4 arguments and it points to my sum function in main. So here it is :

    Code:
    #include "stdafx.h"
    
    #using <mscorlib.dll>
    using namespace System;
    
    void sum(Int32[],Int32 [],Int32[], int);
    void copy(Int32 [], Int32[]);
    void print(Int32 []);
    
    int _tmain()
    {
    	Int32 f[] = new Int32[1000];
    	Int32 s[] = new Int32[1000];
    	Int32 sum[] = new Int32[1000];
    	
    	f[0]=1;
    	s[0]=1;
    
    	Console::WriteLine(S"Input N: ");
    	int n =Int32::Parse(Console::ReadLine());
    	
    	sum(sum,f,s,n);
    
    	return 0;
    }
    
    void sum(Int32 su[], Int32 fir[], Int32 sec[], int nv) {
    
    	int sum,carry;
    	for(int i=carry=0; i<=nv; i++){
    		sum = fir[i] + sec[i] + carry;
    		su[i]=sum%10;
    		carry = sum/10;
    		copy(sec,fir);
    		copy(su,sec);
    	}
    print(su);
    }
    
    void copy(Int32 a[], Int32 b[]){
    
    	for(int i=0; i<a->Length; i++)
    		a[i] = b[i];
    }
    
    void print(Int32 b[]){
    
    for(int i=0; i<b->Length; i++)
    Console::WriteLine(S"{0}",b[i].ToString());
    }
    Last edited by blindman858; 05-26-2005 at 12:32 PM.

  12. #12
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    I'ts probably because you have a function called sum and an array called sum so when you use the line:

    sum(sum, f, s, n);

    it can't tell the sum used as the first parameter to the function called sum from the function called sum. I'd try changing the array name or the function name to see what happens.
    You're only born perfect.

  13. #13
    Registered User
    Join Date
    Apr 2005
    Posts
    41
    cool that fixed the area but the numbers arent being generated the first element is always one and by default every other element is zero. So it prints 10000000000000000000 etc every time. I am probably not storing the sum correctly.

    [Edit] I think see my problem let me try to fix it.
    Last edited by blindman858; 05-26-2005 at 12:24 PM.

  14. #14
    Registered User
    Join Date
    Apr 2005
    Posts
    41
    ok I am stuck. I know the problem. The zeros are there because the fir and sec arrays are not getting the other values. I need to populate them some how. I tried using a for loop but i didnt work. I am gonna fiddle around some more.

  15. #15
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    try calling the print function after assigning 1 to f[0] and s[0] back in main() to be sure the correct values are assigned where you think they are, and that you can retrieve them appropriately there before passing them to sum(). The syntax you are using for the print function is not known to me, particularly, I don't know what S"{0}", means/does.

    Some other concerns:
    you have a variable called sum in the sum function. Change one or the other, unless you've already done so.

    I also think you might want to change this:
    Code:
    a[i] = b[i];
     
    to this:
     
    b[i] = a[i];
    in copy, but you'll have to confirm that.
    You're only born perfect.

Page 1 of 2 12 LastLast
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