C++ Big Integer

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...

Big integer numbers & C

Since modern possessors are highly efficient when dealing with fixed bit length numbers why don't you have an array of them?

Suppose you use unsigned long long. They should be 64 bits width, so max possible unsigned long long should be 2^64 - 1. Lets represent any number as a collection of numbers as:

-big_num = ( n_s, n_0, n_1, ...)

-n_s will take only 0 and 1 to represent + and - sign

-n_0 will represent number between 0 and 10^a -1 (exponent a to be determent)

-n_1 will represent number between 10^a and 10^(a+1) -1
and so on, and so on ...

DETERMINING a:

All n_ MUST be bounded by 10^a-1. Thus when adding two big_num this means we need to add the n_ as follow:

// A + B = ( (to be determent later),
//          bound(n_A_1 + n_B_1) and carry to next,
//          bound(n_A_2 + n_B_2 + carry) and carry to next,
//        ...)

The bounding can be done as:

bound(n_A_i + n_B_i + carry) = (n_A_i + n_B_i + carry)%(10^a)

Therefore the carry to i+1 is determined as:

// carry (to be used in i+1) = (n_A_i + n_B_i + carry)/(10^a) 
// (division of unsigned in c++ will floor the result by construction)

This tell us that the worst case is carry = 10^a -1, and thus the worst addition (n_A_i + n_B_i + carry) is:
(worst case) (10^a-1) + (10^a-1) + (10^a-1) = 3*(10^a-1)
Since type is unsigned long long if we don't want to have overflow on this addition we must bound our exponent a such that:

//    3*(10^a-1) <= 2^64 - 1, and a an positive integer
// => a <= floor( Log10((2^64 - 1)/3 + 1) )
// => a <= 18

So this has now fixed are maximum possible a=18 and thus the biggest possible n_ represented with unsigned long long is 10^18 -1 = 999,999,999,999,999,999. With this basic set up lets now get to some actual code. For now I will use std::vector to hold the big_num we discussed, but this can change:

// Example code with unsigned long long
#include <cstdlib>
#include <vector>
//
// FOR NOW BigNum WILL BE REPRESENTED
// BY std::vector. YOU CAN CHANGE THIS LATTER
// DEPENDING ON WHAT OPTIMIZATIONS YOU WANT
//
using BigNum = std::vector<unsigned long long>;

// suffix ULL garanties number be interpeted as unsigned long long
#define MAX_BASE_10 999999999999999999ULL

// random generate big number
void randomize_BigNum(BigNum &a){
  // assuming MyRandom() returns a random number
  // of type unsigned long long
  for(size_t i=1; i<a.size(); i++)
    a[i] = MyRandom()%(MAX_NUM_BASE_10+1); // cap the numbers
}

// wrapper functions
void add(const BigNum &a, const BigNum &b, BigNum &c); // c = a + b
void add(const BigNum &a, BigNum &b);         // b = a + b

// actual work done here
void add_equal_size(const BigNum &a, const BigNum &b, BigNum &c, size_t &N);
void add_equal_size(const BigNum &a, const BigNum &b, size_t &N);
void blindly_add_one(BigNum &c);
// Missing cases
// void add_equal_size(BigNum &a, BigNum &b, BigNum &c, size_t &Na, size_t &Nb);
// void add_equal_size(BigNum &a, BigNum &b, size_t &Na, size_t &Nb);

int main(){
  size_t n=10;
  BigNum a(n), b(n), c(n);
  randomize_BigNum(a);
  randomize_BigNum(b);
  add(a,b,c);
  return;
}

The wrapper functions should look as follows. They will safe guard against incorrect size of array calls:

// To do: add support for when size of a,b,c not equal

// c = a + b
void add(const BigNum &a, const BigNum &b, BigNum &c){

  c.resize(std::max(a.size(),b.size()));

  if(a.size()==b.size())
    add_equal_size(a,b,c,a.size());
  else
    // To do: add_unequal_size(a,b,c,a.size(),b.size());

  return;
};
// b = a + b
void add(const BigNum &a, const BigNum &b){

  if(a.size()==b.size())
    add_equal_size(a,b,a.size());
  else{
    b.resize(a.size());
    // To do: add_unequal_size(a,b,a.size());
  }

  return;
};

The main grunt of the work will be done here (which you can call directly and skip a function call, if you know what you are doing):

// If a,b,c same size array
// c = a + b
void add_equal_size(const BigNum &a, const BigNum &b, BigNum &c, const size_t &N){
  // start with sign of c is sign of a
  // Specific details follow on whether I need to flip the
  // sign or not
  c[0] = a[0];
  unsigned long long carry=0;

  // DISTINGUISH TWO GRAND CASES:
  //
  // a and b have the same sign
  // a and b have oposite sign
  // no need to check which has which sign (details follow)
  //
  if(a[0]==b[0]){// if a and b have the same sign
    //
    // This means that either +a+b or -a-b=-(a+b)
    // In both cases I just need to add two numbers a and b
    // and I already got the sign of the result c correct form the
    // start
    //
    for(size_t i=1; i<N;i++){
      c[i]  = (a[i] + b[i] + carry)%(MAX_BASE_10+1);
      carry = c[i]/(MAX_BASE_10+1);      
    }
    if(carry){// if carry>0 then I need to extend my array to fit the final carry
      c.resize(N+1);
      c[N]=carry;
    }
  }
  else{// if a and b have opposite sign
    //
    // If I have opposite sign then I am subtracting the
    // numbers. The following is inspired by how
    // you can subtract two numbers with bitwise operations.
    for(size_t i=1; i<N;i++){
      c[i]  = (a[i] + (MAX_BASE_10 - b[i]) + carry)%(MAX_BASE_10+1);
      carry = c[i]/(MAX_BASE_10+1);      
    }
    if(carry){ // I carried? then I got the sign right from the start
      // just add 1 and I am done
      blindly_add_one(c);
    }
    else{ // I didn't carry? then I got the sign wrong from the start
      // flip the sign
      c[0] ^= 1ULL;
      // and take the compliment
      for(size_t i=1; i;<N;i++)
    c[i] = MAX_BASE_10 - c[i];
    }
  }
  return;
};

A few details about the // if a and b have opposite sign case follow:
Lets work in base 10. Lets say we are subtracting a - b Lets convert this to an addition. Define the following operation:

Lets name the base 10 digits of a number di. Then any number is n = d1 + 10*d2 + 10*10*d3... The compliment of a digit will now be defined as:

     `compliment(d1) = 9-d1`

Then the compliment of a number n is:

   compliment(n) =         compliment(d1)
                   +    10*compliment(d2)
                   + 10*10*compliment(d3)
                   ...

Consider two case, a>b and a<b:

EXAMPLE OF a>b: lest say a=830 and b=126. Do the following 830 - 126 -> 830 + compliment(126) = 830 + 873 = 1703 ok so if a>b, I drop the 1, and add 1 the result is 704!

EXAMPLE OF a<b: lest say a=126 and b=830. Do the following 126 - 830 -> 126 + compliment(830) = 126 + 169 = 295 ...? Well what if I compliment it? compliment(295) = 704 !!! so if a<b I already have the result... with opposite sign.

Going to our case, since each number in the array is bounded by MAX_BASE_10 the compliment of our numbers is

compliment(n) = MAX_BASE_10 - n

So using this compliment to convert subtraction to addition
I only need to pay attention to if I carried an extra 1 at
the end of the addition (the a>b case). The algorithm now is

FOR EACH ARRAY subtraction (ith iteration):
na_i - nb_i + carry(i-1)
convert -> na_i + compliment(nb_i) + carry(i-1)
bound the result -> (na_i + compliment(nb_i) + carry(i-1))%MAX_BASE_10
find the carry -> (na_i + compliment(nb_i) + carry(i-1))/MAX_BASE_10
keep on adding the array numbers...
At the end of the array if I carried, forget the carry
and add 1. Else take the compliment of the result

This "and add one" is done by yet another function:

// Just add 1, no matter the sign of c
void blindly_add_one(BigNum &c){
  unsigned long long carry=1;
  for(size_t i=1; i<N;i++){
    c[i]  = carry%(MAX_BASE_10+1);
    carry = c[i]/(MAX_BASE_10+1);
  }
  if(carry){ // if carry>0 then I need to extend my basis to fit the number
    c.resize(N+1);
    c[N]=carry;
  }
};

Good up to here. Specifically in this code don't forget that at the start of the function we set the sign of c to the sign of a. So if I carry at the end, that means I had |a|>|b| and I did either +a-b>0 or -a+b=-(a-b)<0. In either case setting the results c sign to a sign was correct. If I don't carry I had |a|<|b| with either +a-b<0 or -a+b=-(a-b)>0. In either case setting the results c sign to a sign was INCORRECT so I need to flip the sign if I don't carry.

The following functions opperates the same way as the above one, only rather than do c = a + b it dose b = a + b

// same logic as above, only b = a + b
void add_equal_size(BigNum &a, BigNum &b, size_t &N){

  unsigned long long carry=0;
  if(a[0]==b[0]){// if a and b have the same sign
    for(size_t i=1; i<N;i++){
      b[i]  = (a[i] + b[i] + carry)%(MAX_BASE_10+1);
      carry = b[i]/(MAX_BASE_10+1);      
    }
    if(carry){// if carry>0 then I need to extend my basis to fit the number
      b.resize(N+1);
      b[N]=carry;
    }
  }
  else{ // if a and b have oposite sign
    b[0] = a[0];
    for(size_t i=1; i<N;i++){
      b[i]  = (a[i] + (MAX_BASE_10 - b[i]) + carry)%(MAX_BASE_10+1);
      carry = b[i]/(MAX_BASE_10+1);      
    }
    if(carry){
      add_one(b);
    }
    else{
      b[0] ^= 1ULL;
      for(size_t i=1; i;<N;i++)
    b[i] = MAX_BASE_10 - b[i];
    }
  }
  return;
};

And that is a basic set up on how you could use unsigned numbers in arrays to represent very large integers.

WHERE TO GO FROM HERE

Their are many thing to do from here on out to optimise the code, I will mention a few I could think of:

-Try and replace addition of arrays with possible BLAS calls

-Make sure you are taking advantage of vectorization. Depending on how you write your loops you may or may not be generating vectorized code. If your arrays become big you may benefit from this.

-In the spirit of the above make sure you have properly aligned arrays in memory to actually take advantage of vectorization. From my understanding std::vector dose not guaranty alignment. Neither dose a blind malloc. I think boost libraries have a vector version where you can declare a fixed alignment in which case you can ask for a 64bit aligned array for your unsigned long long array. Another option is to have your own class that manages a raw pointer and dose aligned allocations with a custom alocator. Borrowing aligned_malloc and aligned_free from https://embeddedartistry.com/blog/2017/02/22/generating-aligned-memory/ you could have a class like this to replace std::vector:

// aligned_malloc and aligned_free from:
// https://embeddedartistry.com/blog/2017/02/22/generating-aligned-memory/

// wrapping in absolutly minimal class to handle
// memory allocation and freeing 
class BigNum{
private:
  unsigned long long *ptr;
  size_t size;
public:  
  BigNum() : ptr(nullptr)
       , size(0)
  {};  

  BigNum(const size_t &N) : ptr(nullptr)
              , size(N)
  {
    resize(N);
  }  
  // Defining destructor this will now delete copy and move constructor and assignment. Make your own if you need them
  ~BigNum(){
    aligned_free(ptr);
  }  

  // Access an object in aligned storage
  const unsigned long long& operator[](std::size_t pos) const{
    return *reinterpret_cast<const unsigned long long*>(&ptr[pos]);
  }
  // return my size
  void size(){    
    return size;
  }
  // resize memory allocation
  void resize(const size_t &N){
    size = N;
    if(N){
      void* temp = aligned_malloc(ptr,N+1); // N+1, always keep first entry for the sign of BigNum 
      if(temp!=nullptr)
    ptr = static_cast<unsigned long long>(temp);
      else
    throw std::bad_alloc();
    }
    else{
      aligned_free(ptr);
    }
  }
};

Use of bigint in C (Example using libtomath library)

The best way is to use gmp.

#include <gmp.h>
#include <stdio.h>
 
int main(int argc, char *argv[])
{
    mpz_t x,y,two;
    if (argc<3)
        return 1;
    mpz_init_set_str (x, argv[1], 10);
    mpz_init_set_str (y, argv[2], 10);
    mpz_init_set_ui(two, 2U);
    mpz_add (x,x,y);/*x<-x+y*/
    mpz_mul (y,y,two);/*y<-y+y*/
    printf("%s\n", mpz_get_str (NULL, 10, x));
    printf("%s\n", mpz_get_str (NULL, 10, y));
    return 0;
}

You can use it like this:

% gcc addbig.c -lgmp
% ./a.out 49378437483789437894739874389\ 
          74387438978437894378743874837
123765876462227332273483749226
148774877956875788757487749674
% ./a.out 1111111111111111111111111111111111111111111\
          2222222222222222222222222222222222222222222
3333333333333333333333333333333333333333333
4444444444444444444444444444444444444444444

Adding large integer values in C

You cannot use regular arithmetic types for this, even unsigned long long only has 64 bits which is much less than required for your purpose.

Also note that your loop test is incorrect: it should be while (x == 2)

Here is a small program that can handle numbers with 99 decimal digits:

#include <stdio.h>
#include <string.h>

char *bigadd(char *c, const char *a, const char *b) {
    size_t alen = strlen(a);
    size_t blen = strlen(b);
    size_t clen = (alen > blen) ? alen : blen;
    size_t i = clen;
    int digit, carry = 0;
    c[i] = '\0';
    while (i > 0) {
        digit = ((alen ? a[--alen] - '0' : 0) +
                 (blen ? b[--blen] - '0' : 0) +
                 carry);
        carry = digit >= 10;
        c[--i] = (char)('0' + (digit - carry * 10));
    }
    if (carry) {
        memmove(c + 1, c, clen + 1);
        c[0] = '1';
    }
    return c;
}

int main(int argc, char *argv[]) {
    char a[100], b[100], c[101];

    while (scanf("%99s%99s", a, b) == 2) {
        printf("%s\n", bigadd(c, a, b));
    }
    return 0;
}

What is the simplest way of implementing bigint in C?

If you're looking for a simple library, libtommath (from libtomcrypt) is probably what you want.

If you're looking to write a simple implementation yourself (either as a learning exercise or because you only need a very limited subset of bigint functionality and don't want to tack on a dependency to a large library, namespace pollution, etc.), then I might suggest the following for your problem:

Since you can bound the size of the result based on n, simply pre-allocate an array of uint32_t of the required size to hold the result. I'm guessing you'll want to print the result, so it makes sense to use a base that's a power of 10 (i.e. base 1000000000) rather than a power of 2. That is to say, each element of your array is allowed to hold a value between 0 and 999999999.

To multiply this number by a (normal, non-big) integer n, do something like:

uint32_t carry=0;
for(i=0; i<len; i++) {
    uint64_t tmp = n*(uint64_t)big[i] + carry;
    big[i] = tmp % 1000000000;
    carry = tmp / 1000000000;
}
if (carry) big[len++] = carry;

If you know n will never be bigger than 100 (or some other small number) and want to avoid going into the 64-bit range (or if you're on a 64-bit platform and want to use uint64_t for your bigint array), then make the base a smaller power of 10 so that the multiplication result will always fit in the type.

Now, printing the result is just something like:

printf("%lu", (long)big[len-1]);
for(i=len-1; i; i--) printf("%.9lu", (long)big[i-1]);
putchar('\n');

If you want to use a power of 2 as the base, rather than a power of 10, the multiplication becomes much faster:

uint32_t carry=0;
for(i=0; i<len; i++) {
    uint64_t tmp = n*(uint64_t)big[i] + carry;
    big[i] = tmp;
    carry = tmp >> 32;
}
if (carry) big[len++] = carry;

However, printing your result in decimal will not be so pleasant... :-) Of course if you want the result in hex, then it's easy:

printf("%lx", (long)big[len-1]);
for(i=len-1; i; i--) printf("%.8lx", (long)big[i-1]);
putchar('\n');

Hope this helps! I'll leave implementing other things (like addition, multiplication of 2 bigints, etc) as an exercise for you. Just think back to how you learned to do base-10 addition, multiplication, division, etc. in grade school and teach the computer how to do that (but in base-10^9 or base-2^32 instead) and you should have no problem.

Implementing BigInteger

You need to implement two functions for your UINT1024 class, multiply by integer and add integer. Then for each digit you convert, multiply the previous value by 10 and add the value of the digit.

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.