Wrong Calculating

[SteveAustin]

Hello, as being new to C++ i tried to Programme an Emulator for Fibonacci-Numbers. Noticing that only the 93rd first Fibonacci-Numbers were right and the 94th wrong I tried a lot and figured out, that my program says:

7540113804746346429 + 12200160415121876738 = 19740274219868223168

which is definitiely wrong (should be 19740274219868223167) :-(


Why is that wrong, can anyone help me ? Thanks a lot !

#include <stdio.h>
#include <iostream>

using namespace std;

int main()
{
long double t1 = 0, t2 = 1, nextTerm = 0;
int n;
for (n = 0; n <= 100; n++)
{

std::cout << std::fixed << nextTerm << " " << n
<< "\n";
t1 = t2;
t2 = nextTerm;
nextTerm = t1 + t2;
}
return 0;
}

[Ganado]

Data types do not have infinite precision; you're eventually going to get overflow errors with integers, or rounding errors with floating-point numbers. I suggest a "Big/Large Number/Integer" library for C++ if you want to calculate those super huge numbers. Try searching Google for "big int C++".

[keskiverto]

You do use long double, a floating point type. They have limited precision.

http://en.cppreference.com/w/cpp/language/types
http://en.cppreference.com/w/cpp/types/climits#Limits_of_floating_point_types

[zaphraud]

Yeah but you're still going to run into problems very very quickly if you rely on the CPU's ability to handle numbers - or even on emulations built into some versions of C for higher bit numbers. To make the really long numbers, you need to implement your own number system from scratch, the way we did in the days of 8-bit CPUs and assembly language!

To see an example of a program written from scratch, check out "bc" in the GNU library. Handles arbitrarily large integers (which means it's easier to write your program as a bash shell script than in C++ :-)

[zaphraud]

#define DIGITS 500
// Should be plenty

#define BASE 10
// in case you want to see this in binary or octal..

#define LOOPS 500
// when to stop

#include <stdio.h>

int main () {
        //save space use chars
        unsigned char oldnum[DIGITS];
        unsigned char oldestnum[DIGITS];
        unsigned char newnum[DIGITS];
        int count = 0;
        int loopcount = 2; // fake the first 2 digits
        int digit=0, carry = 0;

        //Initialize array. Position at 0 is lowest value and last printed digit.
        for (count = 0; count < DIGITS ; count++) {
                oldnum[count] = 0 ;
                oldestnum[count] = 0 ;
                newnum[count] = 0 ;
                }
        //preload first two numbers
        oldnum[0] = 1 ;
        oldestnum[0] = 1 ;
        //fake output for the first two numbers in the series:
        printf ("1\n1\n");

        while (loopcount < LOOPS) {

                //Compute the next number
                carry = 0;
                for (count = 0; count < DIGITS ; count++) {
                        digit = oldnum[count] + oldestnum[count] + carry;
                        carry = 0;
                        if (digit >= BASE) {
                                digit = digit - BASE;
                                carry = 1;
                                }
                        newnum[count] = digit;
                        }

                //Print the next number
                carry = 0; //recycle variable. use as flag to skip leading zeros
                for (count = DIGITS-1; count >= 0 ; count--) {
                        digit = newnum[count];
                        if (digit > 0) {
                                carry = 1;
                                }
                        if (carry > 0) {
                                printf("%c",newnum[count]+48); //this will need to be rewritten for base systems over 10 i.e. hex
                                }
                        }
                printf("\n");

                //Age the numbers
                for (count = 0; count < DIGITS ; count++) {
                        oldestnum[count] = oldnum[count];
                        oldnum[count] = newnum[count];
                        newnum[count] = 0; //unnecessary clearing but good practice
                        }

                loopcount++;
                }

        }

fresh served. thanks that was fun and refreshing. its your job to make it look like c++ instead of c.

[zaphraud]

I made two others just now, bitonacci and octonacci, that display their output without skipping leading zeros, but instead of numbers they output vt100 sequences for background color changes and spaces. Makes a very pretty triangle!

[TheIdeasMan]

zaphraud wrote:

Yeah but you're still going to run into problems very very quickly if you rely on the CPU's ability to handle numbers - or even on emulations built into some versions of C for higher bit numbers. To make the really long numbers, you need to implement your own number system from scratch, the way we did in the days of 8-bit CPUs and assembly language!

As Ganado says there are perfectly good big int libraries that work really well. I disagree about needing to write your own, especially not in assembly.

http://www.boost.org/doc/libs/1_66_0/libs/multiprecision/doc/html/index.html

[lastchance]

#include <iostream>
#include <vector>
using namespace std;


class Big
{
public:
   vector<int> digits;       // digits stored in REVERSE order
   Big( int N = 0 );
};


Big::Big( int n )
{
   if ( n == 0 )
   {
      digits.push_back( 0 );
   }
   else
   {
      for ( ; n; n /= 10 ) digits.push_back( n % 10 );
   }
}


Big operator+( const Big &a, const Big &b )
{
   Big result = a;

   int last = b.digits.size() - 1;
   int i = 0, carry = 0;
   while ( i <= last || carry > 0 )
   {
      if ( i < result.digits.size() ) carry += result.digits[i];
      if ( i < b.digits.size()      ) carry += b.digits[i];
      int digit = carry % 10;
      carry /= 10;
      if ( i < result.digits.size() ) result.digits[i] = digit;
      else                            result.digits.push_back( digit );

      i++;
   }
   return result;
}


ostream &operator<<( ostream &stream, const Big &a )
{
   for ( int i = a.digits.size() - 1; i >= 0; i-- ) stream << a.digits[i];
   return stream;
}


//======================================================================


int main()
{
   Big first = 1, second = 1;          // Change to 0 and 1 if you prefer

   cout << 1 << ": " << first  << '\n';
   cout << 2 << ": " << second << '\n';

   for ( int i = 3; i <= 150; i++ )
   {
      Big temp = first + second;
      first = second;
      second = temp;
      cout << i << ": " << temp << endl;
   }
}