How can you represent large numbers?

Question

What is the best way to handle large numeric inputs in C++ (for example 10^100)?

For algorithms I usually switch over to ruby and I sometimes use strings.

Any other good methods?

Vorous

Answer 1

It sounds like you're looking for a way to enter Arbitrary Precision numbers. here are two libraries you could use: GMP and MAPM

Lucienlucienne

Answer 2

Check out The Large Integer Case Study in C++.pdf by Owen Astrachan. I found this file extremely useful with detail introduction and code implementation. It doesn't use any 3rd-party library. I have used this to handle huge numbers (as long as you have enough memory to store vector<char>) with no problems.

---

Idea: It implements an arbitrary precision integer class by storing big int in a vector<char>.

vector<char> myDigits; // stores all digits of number

Then all operations related to the big int, including <<, >>, +, -, *, ==, <, !=, >, etc., can be done based on operations on this char array.

---

Taste of the code: Here is the header file, you can find its cpp with codes in the pdf file.

#include <iostream>
#include <string> // for strings
#include <vector> // for sequence of digits
using namespace std;

class BigInt
{
public:
    BigInt(); // default constructor, value = 0
    BigInt(int); // assign an integer value
    BigInt(const string &); // assign a string
    // may need these in alternative implementation
    // BigInt(const BigInt &); // copy constructor
    // ~BigInt(); // destructor
    // const BigInt & operator = (const BigInt &);
    // assignment operator
    // operators: arithmetic, relational
    const BigInt & operator += (const BigInt &);
    const BigInt & operator -= (const BigInt &);
    const BigInt & operator *= (const BigInt &);
    const BigInt & operator *= (int num);
    string ToString() const; // convert to string
    int ToInt() const; // convert to int
    double ToDouble() const; // convert to double
    // facilitate operators ==, <, << without friends
    bool Equal(const BigInt & rhs) const;
    bool LessThan(const BigInt & rhs) const;
    void Print(ostream & os) const;
private:
    // other helper functions
    bool IsNegative() const; // return true iff number is negative
    bool IsPositive() const; // return true iff number is positive
    int NumDigits() const; // return # digits in number
    int GetDigit(int k) const;
    void AddSigDigit(int value);
    void ChangeDigit(int k, int value);
    void Normalize();
    // private state/instance variables
    enum Sign{positive,negative};
    Sign mySign; // is number positive or negative
    vector<char> myDigits; // stores all digits of number
    int myNumDigits; // stores # of digits of number
};

// free functions
ostream & operator <<(ostream &, const BigInt &);
istream & operator >>(istream &, BigInt &);
BigInt operator +(const BigInt & lhs, const BigInt & rhs);
BigInt operator -(const BigInt & lhs, const BigInt & rhs);
BigInt operator *(const BigInt & lhs, const BigInt & rhs);
BigInt operator *(const BigInt & lhs, int num);
BigInt operator *(int num, const BigInt & rhs);
bool operator == (const BigInt & lhs, const BigInt & rhs);
bool operator < (const BigInt & lhs, const BigInt & rhs);
bool operator != (const BigInt & lhs, const BigInt & rhs);
bool operator > (const BigInt & lhs, const BigInt & rhs);
bool operator >= (const BigInt & lhs, const BigInt & rhs);
bool operator <= (const BigInt & lhs, const BigInt & rhs);

Coat

Answer 3

If you wish to make your own code for the purpose try using strings to store big numbers... you can then create basic ops like + - / * on them... for example -

#include <iostream>

using namespace std;

string add (string &s1, string &s2){
    int carry=0,sum,i;

    string  min=s1,
    max=s2,
    result = "";

    if (s1.length()>s2.length()){
        max = s1;
        min = s2;
    } else {
        max = s2;
        min = s1;
    }

    for (i = min.length()-1; i>=0; i--){
        sum = min[i] + max[i + max.length() - min.length()] + carry - 2*'0';

        carry = sum/10;
        sum %=10;

        result = (char)(sum + '0') + result;
    }

    i = max.length() - min.length()-1;

    while (i>=0){
        sum = max[i] + carry - '0';
        carry = sum/10;
        sum%=10;

        result = (char)(sum + '0') + result;
        i--;
    }

    if (carry!=0){
        result = (char)(carry + '0') + result;
    }       

    return result;
}

int main (){
    string a,b;

    cin >> a >> b;

    cout << add (a,b)<<endl;

    return 0;
}

Pentheam

Answer 4

Are you looking for how to perform operations on the large inputs you receive? There is a big integer C++ library (similar to Java) that allows you to perform arithmetic operations...

Mindoro

Answer 5

assuming you are talking about inputting numbers, double precision would get you up to 1.7976931348623157 x 10^308

Correspond

double lets you represent large integers, but not with perfect accuracy. For example, 10^100 represented as a double is actually 1000...15104, not exactly 10^100. – Everlasting

Answer 6

You might want to have a look to gmplib, an arbitrary precision number handling library for C and C++

Emera

Answer 7

If you want it to be accurate, you need a library made to deal with big numbers. Java has BigInt that will always be accurate no matter how many digits you want to take it to, and provides math operations on them. All the source code is included, you could transfer it, but this really isn't the kind of thing C++ is best at--I'd use a JVM based language and use one of the Big libraries.

I don't think I'd use ruby for this unless you wanted it to be slow, and I'm assuming that since you are talking about C++, speed is somewhat of a design consideration.

Manno

Answer 8

As others have already pointed out, there are various bignum/arbitrary precision libraries in C++ that you would likely find useful. If speed isn't necessary, I'm under the impression that Python and Lisp both use bignums by default.

Herniorrhaphy

That is correct for Liso. If I am doing bignum stuff, I roll with Lisp. :) – Suffice

@Paul Nathan > That is correct for Liso. Do you mean Lisp? or is Liso some library that I'm not aware of? – Cancan

Answer 9

Large numbers like 10^100 require arbitrary precision integers. Numbers are stored as a sequence of digits. A very naive way is to store them as a sequence of decimal digits in a string. However, it is more efficient to store them as a sequence of digits base 2³² or 2⁶⁴ since more work can be done per digit, and bitwise operations like & and | remain fast.

_BitInt (formerly _ExtInt)

_BitInt is a clang C++ compiler extension (since clang 14; formerly known as _ExtInt). It lets you define integers with an arbitrary amount of bits:

// representing 10100 requires at least 333 bits
_BitInt(512) huge = 100..00;

_BitInt is also a standardized feature in C23, although only clang implements it at this time.

If you are okay with compiling a portion of your program as C, or with relying exclusively on clang, then you can get arbitrary precision without any third-party libraries.

Third-Party Libraries

There isn't any big_int class in the standard library yet, but you can use third-party libraries:

Library	Format	Features
Boost.Multiprecision	C++ library	Arbitrary and infinite precision integers, arbitrary precision floating-point
GMP (GNU Multiple Precision Arithmetic Library)	C library (C++-compatible)	Arbitrary and infinite precision integers, arbitrary precision floating-point
MPIR (Multiple Precision Integers and Rationals)	Fork of GMP	Similar to GMP, but compiles with Visual Studio and has some extra features
BigDigits	C library (C++-compatible)	Arbitrary and infinite precision integers
ttmath (Bignum C++ library)	C++ library	Arbitrary precision integers and floating-point
faheel/BigInt	C++ header-only	Infinite precision integers
rgroshanrg/bigint	C++ single-header	Infinite precision integers
sercantutar/infint	C++ single-header	Infinite precision integers

For more libraries, see Wikipedia: List of arbitrary-precision arithmetic software

---

Note: "arbitrary precision" means that a number can have any fixed amount of bits, whereas "infinite precision" means that the amount of bits can increase when needed.

Everlasting

Answer 10

Consider boost::cpp_int

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>

int main()
{
   using namespace boost::multiprecision;

   cpp_int u = 1;
   for(unsigned i = 1; i <= 100; ++i)
      u *= i;

   // prints 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 (i.e. 100!)
   std::cout << u << std::endl;

   return 0;
}

Clandestine

Answer 11

Well I think the best way to do such arithmetic calculation is by using strings. Give input as command line arguments and then manipulate the whole logic using string functions like atoi() and itoa()! But, hey can this be done for multiplication and Division? I think in this way strlen of strings entered doesn't matter for programming for compiler until the logic is fine.

Assegai

This is not a good solution. Getting input from command line arguments is renders your program useless unless you're making a sort of command line calculator. Furthermore, using ato* functions both assumes you already know the desired data type AND that they're going to be in standard precision range, so it makes no sense to waste time converting to them instead of to your big number format directly when you'd just have to parse through those numbers again, assuming you even read them in properly. itoa is also not part of the standard C++ library. – Aniakudo