@Saurabh: :) Well, I could think of a way of solving this without using other libraries.
Use iterative version of fibonacci numbers but when adding the ith and (i+1)st values, use circular linked lists (or doubly linked lists) to add these 2 values. Since the question of integer overflow does not come into picture when 2 big numbers are added, there is no problem. As an optimization, one can use linked lists for addition only when values get close to max integer value. Bharath. On Jul 31, 8:38 pm, saurabh singh <[email protected]> wrote: > By creating a bugnum library using link list....:) > > > > > > > > > > On Sun, Jul 31, 2011 at 11:12 PM, bharath <[email protected]> wrote: > > @Amit: Thanks for the solution but I have seen this approach. I was > > wondering how this can be solved using linked lists without using > > bignum libraries. > > > Bharath > > > On Jul 31, 12:38 pm, amit karmakar <[email protected]> wrote: > > > Since long long cannot store the 100th Fibonacci number, you need to > > > implement or use an existing library for bignum. > > > > You may use linked lists to solve this problem. > > > Read about bignum herehttp:// > > en.wikipedia.org/wiki/Arbitrary-precision_arithmetic > > > > Here is my implementation for solving this problem, > > > #include <cstdio> > > > #include <algorithm> > > > #include <cstring> > > > > using namespace std; > > > > #define REP(i, n) for(int i = 0; i < (n); i++) > > > #define FILL(c, v) memset(c, v, sizeof(c)) > > > > const int MX = 100000; > > > int prv1[MX], prv2[MX], cur[MX], l1, l2, lcur; > > > > int main() { > > > FILL(prv1, 0); FILL(prv2, 0); FILL(cur, 0); > > > int n; > > > scanf("%d", &n); > > > > prv1[0] = 0; l1 = 1; > > > prv2[0] = 1; l2 = 1; > > > cur[0] = 0; lcur = 1; > > > REP(i, n) { > > > int mx = max(l1, l2); > > > int carry = 0; > > > REP(j, mx) { > > > int imd = prv1[j]+prv2[j]+carry; > > > cur[j] = imd%10; > > > carry = imd/10; > > > } > > > if(carry) { > > > cur[mx++] = carry; > > > } > > > lcur = mx; > > > > REP(j, l1) prv2[j] = prv1[j]; l2=l1; > > > REP(j, lcur) prv1[j] = cur[j]; l1=lcur; > > > } > > > REP(i, lcur) printf("%d", cur[lcur-i-1]); printf("\n"); > > > > } > > > > On Jul 31, 9:31 pm, bharath sriram <[email protected]> wrote: > > > > > Since both the "normal" recursive (stack overflow) and non-recursive > > (data > > > > type overflow) versions fails, is there a way one can use linked lists > > to > > > > solve this problem? > > > > > Bharath. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Saurabh Singh > B.Tech (Computer Science) > MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
