Handling Large Numbers in C++

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.

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;
}

handling large numbers and overflows

To insure no overflow, use int32_t and int64_t.

The range of values [-2147483648 ... 2147483647] matches the int32_t range. You could also use int64_t for this, but an array of 10000000 deserves space considerations.

As the sum of any 10,000,000 values does not exceed the range of int64_t, perform all your additions using int64_t.

#include <stdint.h>
size_t foo(const int32_t *value, size_t N) {
  int64_t sum = 0;
  ...
  sum += value[i];
  ...
}

---

BTW: Confident that a solution can be had that does not require addition 64-bit addition.

[Edit] Failed to derive simple int32_t only solution, but came up with:

size_t HalfSum(const int32_t *value, size_t N) {
  // find sum of entire array    
  int64_t ArraySum = 0;
  size_t P;
  for (P = 0; P < N; P++) {
    ArraySum += value[P];
  }

  // compute sum again, stopping when it is half of total
  int64_t PartialSum = 0;
  for (P = 0; P < N; P++) {
    PartialSum += value[P];
    if ((PartialSum * 2) == ArraySum) {
      return P;
    }
  }

  return N;  // No solution (normally P should be 0 ... N-1)
}

how to handle extremely large numbers

Use a BigInteger

The BigInteger type is an immutable type that represents an arbitrarily large integer whose value in theory has no upper or lower bounds.

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