CODEWITHSUNDEEP
c++c
KudoCC
KudoCC

Reputation: 6952

Plus operation on large numbers

There are two n-bit numbers which are store in two byte array (little-endian).

for example : 40-bit number can be represented by: char c[5] = {0xff, 0xff, 0xff, 0xff, 0x01} ;, it is 0xffffffff01.

My question is How to implement the plus operation on two n-bit number efficiently in C or C++ ?

In fact I want to implement the basic operation on large number which is represented by byte array. Any suggestion ?

Upvotes: 1

Views: 182

Answers (1)

Adam
Adam

Reputation: 17329

The basic approach is the same as the one you learned in grade school. Starting at the least significant bytes, add the two bytes along with the incoming carry. If there is an out carry, carry it to the next set.

Of course today's processors are either 32 or 64 bit, so it makes more sense to use uint32_t or uint64_t as the base type instead of char. Note you likely want unsinged, not signed.

You can always look at code from libraries written for this purpose. GMP has a "mini-gmp" pair of .h/.c files that implements the most basic ops. You can browse them online here: mini-gmp.h, mini-gmp.c. In particular, the function you're interested in is mpz_add. Google finds example usage. mpz_add delegates to other functions, but the meat appears to be this function on line 393:

mp_limb_t
mpn_add_n (mp_ptr rp, mp_srcptr ap, mp_srcptr bp, mp_size_t n)
{
  mp_size_t i;
  mp_limb_t cy;

  for (i = 0, cy = 0; i < n; i++)
    {
      mp_limb_t a, b, r;
      a = ap[i]; b = bp[i];
      r = a + cy;
      cy = (r < cy);
      r += b;
      cy += (r < b);
      rp[i] = r;
    }
  return cy;
}

I'll leave it up to you to figure out what the types mean, how memory allocation works, etc., but think of an mp_limb_t as your char.

Upvotes: 3

Related Questions