Big Numbers Library in C++

Big numbers library in c++

The GNU Multiple Precision Arithmetic Library does what you want http://gmplib.org/

Gnu MP is a C library but it has a C++ class Interface and if you are interested only in big integers, you may just deal with mpz_class. Look at the sample below which I took from the page C++ Interface General

 int main (void)
 {
   mpz_class a, b, c;

   a = 1234;
   b = "-5678";
   c = a+b;
   cout << "sum is " << c << "\n";
   cout << "absolute value is " << abs(c) << "\n";

   return 0;
 }

handle snippet code wrtten in C for large numbers

Use long long data type instead of int. Because a signed 32-bit integer can handle upto 2^31 - 1(i.e 32,767) and unsigned int can reach upto 65,535.

Also even if the integers are within int range you should use long long in contests on codeforces in case of multiplication. See example for better explanation.

Example:

m: 100000
n: 100000
a: 1
count = 1

From your code,
count *= m/a; // count *= 100000/1 = 100000
Now,
count *= n/a; // count *= 100000/1 = 10000000000(10^10);
10^10 is beyond 32 bit int range so you will get a wrong answer -_-
So use long long to avoid such overflow errors

Read more about Data Type Ranges

If you wish, you can reduce your code length, like:

#include<stdio.h>
int main()
{
    long long m, n, a, count1 = 1, count2 = 1;
    scanf("%lld%lld%lld",&m,&n,&a);
    count1 *= (m/a);
    count2 *= (n/a);
    if (m%a != 0) count1++;
    if (n%a != 0) count2++;
    printf("%lld", count1*count2);
    return 0;
}

Store and work with Big numbers in C

Normal types in C can usually only store up to 64 bits, so you'll have to store big numbers in an array, for example, and write mathematical operations yourself. But you shouldn't reinvent the wheel here - you could try the GNU Multiple Precision Arithmetic Library for this purpose.

And as the comments already pointed out, the ^ operation is binary XOR. For exponentiation, you will have to use mathematical functions like pow.

BigInteger in C?

Use libgmp:

GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating-point numbers. There is no practical limit to the precision except the ones implied by the available memory in the machine GMP runs on...

Since version 6, GMP is distributed under the dual licenses, GNU LGPL v3 and GNU GPL v2...

GMP's main target platforms are Unix-type systems, such as GNU/Linux, Solaris, HP-UX, Mac OS X/Darwin, BSD, AIX, etc. It also is known to work on Windows in both 32-bit and 64-bit mode...

How to show large integer numbers on C++

You need to either use an existing library that deals with large numbers, or implement your own. There's many options, gnu multi-precision, boost, etc...

If you choose to implement your own, you'll store digits in something like:

• A string "90120304153543643626424262"
• A std::vector<int> of digits (base 10)
  {9,0,1,2,0,....}
• A std::vector<int> of digits (large base, for efficiency. 2^16 works well)
  {42567, 29183, 10987, ...}

Then, you'd need to roll your own multiplication, addition, assignment.

Optimized way to handle extremely large number without using external library

Finding the Least Significant Digits (last k digits) are easy because of the property of modular arithmetic, which says: (n*n)%m == (n%m * n%m)%m, so the code shown by BLUEPIXY which followed exponentiation by squaring method will work well for finding k LSDs.

Now, Most Significant Digits (1st k digits) of N^N can be found in this way:

 We know, 
 N^N = 10^(N log N)

So if you calculate N log (N) you will get a number of this format xxxx.yyyy, now we have to use this number as a power of 10, it is easily understandable that xxxx or integer part of the number will add xxxx zeros after 10, which is not important for you! That means, if you calculate 10^0.yyyy, you will get those significants digits you are looking for.
So the solution will be something like this:

double R = N * log10 (N);
R = R - (long long) R; //so taking only the fractional part
double V = pow(10, R);
int powerK = 1;
for (int i=0; i<k; i++) powerK *=10;
V *= powerK;
//Now Print the 1st K digits from V

---

Related Topics