CODEWITHSUNDEEP
c++linked-listfibonacci
Ryan Allred
Ryan Allred

Reputation: 414

Calculating Giant Numbers using a Linked List

Well, I got an assignment to build a scalable data type to use in a Fibonacci generator, and I have the assignment just about finished when I went to test it out to the 1000th number in the sequence.

I noticed that it got out of align and determined the problem to be at the 262nd number in the sequence. After a little debugging, I discovered this is where the linked list moves from 7 integers to 8 integers, but I don't know that it is related to the problem.

The number I am looking for is:

2 542 592 393 026 885 507 715 496 646 813 780 220 945 054 040 571 721 231

The number I am getting is:

1 154 259 239 326 885 507 715 496 646 813 780 220 945 054 040 571 721 231

As you may notice, they are very similar up until the last chunk (left end).

My source is a little long for SO so I made a gist:

https://gist.github.com/anonymous/5802620

The magic of carrying anything over 1,000,000,000 happens in the function on line 378: https://gist.github.com/anonymous/5802620#file-main-cpp-L378

As an update, I am still getting 'close, but no cigar' output. Here is the code that is likely the culprit (Includes contributed answers):

Giant Giant::operator + (const Giant & rightSide)
{
   Giant returned;
   int extra = 0;

   for(int i = 0;
      i < chunks.getNumItems() && i < rightSide.chunks.getNumItems(); i++)
   {
      int num = chunks.getData(i) + rightSide.chunks.getData(i);
      returned.chunks.insert((num + extra) % chunkSize,
         returned.chunks.getNumItems());
      extra = (num + extra) / chunkSize;
   }

   if(chunks.getNumItems() > rightSide.chunks.getNumItems())
   {
      for(int i = rightSide.chunks.getNumItems();
          i < chunks.getNumItems(); ++i)
      {
         returned.chunks.insert(extra + chunks.getData(i),
            returned.chunks.getNumItems());
         extra = 0;
      }
   }
   else if(chunks.getNumItems() < rightSide.chunks.getNumItems())
   {
      for(int i = chunks.getNumItems();
          i < rightSide.chunks.getNumItems(); ++i)
      {
         returned.chunks.insert(extra + rightSide.chunks.getData(i),
            returned.chunks.getNumItems());
         extra = 0;
      }
   }

   if (extra != 0)
   {
       returned.chunks.insert(extra, returned.chunks.getNumItems());
   }

   return returned;
}

UPDATE A member of the class came over and we looked through the code. Here was the problem:

ostream & operator << (ostream & out, const Giant & giant)
{
   for(int i = giant.chunks.getNumItems() - 1;
      i >= 0; i -= 1)
   {
      if (i != giant.chunks.getNumItems()-1)
         out << setw(9) << setfill('0');
      out << giant.chunks.getData(i);
   }
   return out;
}

I forgot to force display the leading zeros which caused problems. The solution has been found.

Upvotes: 2

Views: 445

Answers (3)

Ryan Allred
Ryan Allred

Reputation: 414

UPDATE A member of the class came over and we looked through the code. Here was the problem:

ostream & operator << (ostream & out, const Giant & giant)
{
   for(int i = giant.chunks.getNumItems() - 1;
      i >= 0; i -= 1)
   {
      if (i != giant.chunks.getNumItems()-1)
         out << setw(9) << setfill('0');
      out << giant.chunks.getData(i);
   }
   return out;
}

I forgot to force display the leading zeros which caused problems. The solution has been found.

Upvotes: 0

Turix
Turix

Reputation: 4490

In addition to what others have said, I think you need to take extra into account in the loops starting on lines 399 and 408. In particular, if extra was non-zero, and you take one of those two loops, you need to add the extra amount to the first thing you insert in that loop (as opposed to adding it separately on line 394).

Edited as per your comment below. This is basically what I meant for lines 392-414:

if(chunks.getNumItems() > rightSide.chunks.getNumItems())
{
   for(int i = rightSide.chunks.getNumItems();
       i < chunks.getNumItems(); ++i)
   {
      returned.chunks.insert(extra + chunks.getData(i),
         returned.chunks.getNumItems());
      extra = 0;
   }
}
else if(chunks.getNumItems() < rightSide.chunks.getNumItems())
{
   for(int i = chunks.getNumItems();
       i < rightSide.chunks.getNumItems(); ++i)
   {
      returned.chunks.insert(extra + rightSide.chunks.getData(i),
         returned.chunks.getNumItems());
      extra = 0;
   }
}
else if (extra != 0)
{
    returned.chunks.insert(extra, returned.chunks.getNumItems());
}

Of course, if that works, there are ways to "streamline it" too.

Upvotes: 1

Mark B
Mark B

Reputation: 96241

Your problem appears to be on lines 387 and 389. You're not accounting extra soon enough in the equation. Those lines should have ((num + extra) % chunkSize) and extra = (num + extra )/ chunkSize; respectively. With your current implementation one of the segments may be 1000000000 with no carry rather than 0 with a carry (Which if I'm reading your intention if what you wanted).

Upvotes: 2

Related Questions