C++ Handling Very Large Integers

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.

Working with very large integers in c++

Have a look at Boost.Multiprecision
The following code works on VS 2015:

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

namespace mp = boost::multiprecision;

typedef mp::number<mp::cpp_int_backend<4096, 4096, mp::signed_magnitude, mp::unchecked, void> >  int4096_t;

int4096_t myPow(int4096_t base, long int exponent, long int mod) {
    int4096_t prod = 1;

    while (exponent > 0) {
        if (exponent & 1 == 1) {
            prod *= base;
            prod %= mod;
        }
        base *= base;
        base %= mod;
        exponent /= 2;
    }
    return prod;
}



int main()
{
    int4096_t a = myPow(2, 1000, 100007);
    std::cout << a << std::endl;

    int i;
    std::cin >> i;
    return 0;
}

And prints 44850. I defined int4096_t integer type (4096 bits length) for example, but you can use predefined boost::multiprecision::int1024_t or another appropriate type.

How to handle big integers in C

If you are interested in Cryptography, then everything has to be correct. Either you spend many months writing and testing and testing and testing... your own big number arithmetic functions, or you use an existing library.

It is difficult enough getting crypto to work correctly when you know that the methods you are using are correct. It is almost impossible if the methods you are using have subtle errors.

For crypto use GMP, and concentrate on the crypto.

If you want to write your own large number arithmetic package, then by all means do so. I have done the same myself and it is an interesting and useful experience. But don't use your own work for anything critical.

Using GMP to calculate very large Integers from formulas

Question 1 Long double allows to handle larger numbers than double (both in the exponent and in the significand precision). But you have to think that your 1e308 order of magnitude doesn't mean anything if your goal is to store large integers; you only have to care about the size of the significand precisions, either 52/53 bits (double) or 64 bits (x86 extended precision). If you try to use it with larger integers, you will have a correct order of magnitude but the exact value will be lost (when computing with integer numbers, people generally care a little more about this than when playing with approximate numbers).

Question 2 Using GMP is a nice choice. Other libraries also exist; for smaller values I use a lot the libqd which has an extended fixed precision and are very quick but this will not be enough for your own problem. Now your question is about setting the values:

using a string version of the number is generally a bad idea (you should keep that only for input/output purposes); it is a slow operation involving basis conversions and digit by digit treatment
doing as much as you can with the GMP types is the way to go (unless you really care about speed and have a full control over the expected range for the values to be computed with native types
if your formula is too long, I can't help much. But using GMP isn't that difficult, can't you really convert your formula? is there some logic in your formula that you could embed in a loop? maybe you could write a quick and dirty python script for converting your formula to a piece of C code using GMP?

Now I don't fully understand why you want to use mpz_t rather than mpf_t. This type implements arbitrary long floating numbers; did you notice you can set the precision with mpf_set_default_prec?

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