BigInteger implementation in C, supporting addition and multiplication

Question

I've implemented adding and multiplying arbitrary precision integers.

Also available as a gist.

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

typedef struct {
    int *data;
    int size;
} bi;

bi *bi_new() {
    bi *a = malloc(sizeof(bi));
    return a;
}

bi *bi_from_string(char *a) {
    bi *b = bi_new();

    int skip = 0;
    while(a[skip] == '0') { skip++; }

    b->size = strlen(a) - skip;

    if(b->size == 0) {
        b->size++;
        b->data = malloc(b->size * sizeof(int));
        b->data[0] = 0;
    } else {
        b->data = malloc(b->size * sizeof(int));
        int i;
        for(i = 0; i < b->size; i++) {
            b->data[i] = a[skip + i] - '0';
        }
    }

    return b;
}

char *bi_to_string(bi *a) {
    char *b = malloc(a->size * sizeof(char));
    int i;
    for(i = 0; i < a->size; i++) {
        b[i] = a->data[i] + '0';
    }
    return b;
}

bi *bi_add(bi *a, bi *b) {
    bi *c = bi_new();
    // max possible size
    c->size = (a->size > b->size ? a->size : b->size) + 1;
    c->data = malloc(c->size * sizeof(int));
    int i = a->size - 1, j = b->size - 1;
    int k = c->size - 1;
    int carry = 0, tmp;

    while(i >= 0 || j >= 0 || carry > 0) {
        if(i >= 0 && j >= 0) {
            tmp = a->data[i] + b->data[j];
        } else if(i >= 0) {
            tmp = a->data[i];
        } else if(j >= 0) {
            tmp = b->data[j];
        } else {
            tmp = 0;
        }
        tmp += carry;
        carry = tmp / 10;
        c->data[k] = tmp % 10;
        i--; j--; k--;
    }

    // this is definitely leaking memory
    if(c->data[0] == 0) { c->size--; c->data++; }
    return c;
}

bi *bi_multiply(bi *a, bi *b) {
    bi *c = bi_new();
    // max size
    c->size = a->size + b->size;
    c->data = malloc(c->size * sizeof(int));
    { int i; for(i = 0; i < c->size; i++) { c->data[i] = 0; } }

    int i = a->size - 1, j = b->size - 1, k = c->size - 1;
    int carry = 0, tmp, push_left = 0;
    while(i >= 0) {
        k = c->size - 1 - push_left++;
        j = b->size - 1;
        while(j >= 0 || carry > 0) {
            if(j >= 0) {
                tmp = a->data[i] * b->data[j];
            } else {
                tmp = 0;
            }
            tmp += carry;
            carry = tmp / 10;
            c->data[k] += tmp % 10;
            carry += c->data[k] / 10;
            c->data[k] = c->data[k] % 10;
            j--; k--;
        }
        i--;
    }

    // Leaking memory for sure
    while(c->data[0] == 0) { c->size--; c->data++; }
    return c;
}

Tests:

#include <assert.h>
#include "bi.c"


int main() {
    // Simple conversion
    char *a = "21739871283971298371298371289371298371298371298371298371293";
    assert(strcmp(a, bi_to_string(bi_from_string(a))) == 0);

    // Remove leading zeros
    char *b = "000123000";
    assert(strcmp("123000", bi_to_string(bi_from_string(b))) == 0);

    // But don't segfault on empty string or string consisting of only zeros
    assert(strcmp("0", bi_to_string(bi_from_string("000"))) == 0);
    assert(strcmp("0", bi_to_string(bi_from_string(""))) == 0);

    char *c = "11111111111111111111111111111111111111111111111111111111111000";
    char *d = "33333333333333333333333333333333333333333333333333333333333789";
    char *e = "44444444444444444444444444444444444444444444444444444444444789";
    assert(strcmp(e, bi_to_string(bi_add(bi_from_string(c),
                        bi_from_string(d)))) == 0);

    assert(strcmp("1024", bi_to_string(bi_add(bi_from_string("512"),
                        bi_from_string("512")))) == 0);

    // Starting with 1 digit by n digit multiplication
    assert(strcmp("16384", bi_to_string(bi_multiply(bi_from_string("2048"),
                        bi_from_string("8")))) == 0);
    // Now multiple
    assert(strcmp("16384", bi_to_string(bi_multiply(bi_from_string("1024"),
                        bi_from_string("16")))) == 0);

    char *f = "781239128739123";
    char *g = "902183901283901283019283012938120";
    char *h = "704821365001497990452726836222051105131222068760";
    assert(strcmp(h, bi_to_string(bi_multiply(bi_from_string(f),
                        bi_from_string(g)))) == 0);

    printf("Reached the end!\n");
}

Oh and, I'd appreciate some extra comments on the two places in the code I've written "leaking memory".

Answer 1

The good part is that without any real modifications, I can compile your code with lots of the extra compiler flags to detect errors: -Wall, -Wextra, -Werror, -pedantic under -std=c99. That's a good start. There are a few problems, though:

Memory Leaking

You provide a bi_new() function, but nothing to free any of the memory that you allocate. Any time you have something returning a pointer to a heap-allocated struct, you should probably provide a convenience function for deallocation.

void bi_free(bi* a)
{
    free(a->data);
    free(a);
}

This is evident in the fact that nothing in your main function cleans up any of the memory you've allocated - thus leaking memory (until the OS kills your process and reclaims it, anyway). For the comments where state you're leaking memory, the fix is to simply modify only size and leave the actual data alone.

Includes

When you start writing larger programs, you should try to break them up into a header file and an implementation file. Here, you #include a .c file. This is very bad practice. It (probably) won't hurt you now, but if you ever move to C++, it can cause a lot of problems. Pull out all of your function prototypes and structs into a header file, and include that into the implementation.

When you're doing this, you'll also want to surround your header file with an include guard.

Strings

Converting to a string with char* bi_to_string(bi *a) works, but in C, it's generally better to take a char * as a parameter into which you can put something, so int bi_to_string(bi *a, char *str). The reason for this is you dynamically (malloc) allocate a string which you then return. This places the onus on the programmer to remember to free it later. If they pass in a char *, they are either already responsible for freeing it later, or can stack allocate it and have it cleaned up automatically. This does mean the user can pass in a string that is too short, however, either an assert(...) or returning an error_code (hence the int return) can catch that.

A similar argument can be made for your add and multiply functions to take a 3rd parameter which is the result value.

NULL-Terminating Strings

You've been bitten by the oldest (C) bug in the book - not NULL-terminating your strings. It's an easy fix:

char *bi_to_string(bi *a) 
{
    //Remember to allocate an extra spot for the NULL terminator
    //Also, you don't need a sizeof(char). The standard says it is guaranteed 
    //to be 1. 
    char *b = malloc(a->size + 1); 
    int i;
    for(i = 0; i < a->size; i++) {
        b[i] = a->data[i] + '0';
    }
    b[a->size] = '\0';  //NULL terminate
    return b;
}

That fixes your first assert: assert(strcmp(a, bi_to_string(bi_from_string(a))) == 0);. However, assert(strcmp(e, bi_to_string(bi_add(bi_from_string(c), bi_from_string(d)))) == 0); fails for me. I'd look into debugging that :)

Naming

This is a minor thing. I know everything in C is generally terse, but the name bi really isn't descriptive at all. Maybe big_int if you still want to be terse, but make it completely unambiguous as to what it is.

Answer 2

Dogbert, I have some comments to add to those from other commenters (use of free, naming)

• minor quibbles: put the opening { of a function on a new line, column 0; put a space after keywords such as for, while, if, etc; make functions static where possible; make parameters const where possible; avoid multiple statements on the same line.
• negative numbers are not handled

• your type bi uses an allocated integer array to store values in the range [0..9]. This seems wasteful. A signed char would do. Also, you have to allocate twice to create a bi when once would be preferable. Here I have rearranged the structure so that the array is at the end and can be expanded by allocating more memory that is needed just for the struct:

  typedef struct {
      size_t size;
      signed char data[1];  // you can also use just data[] and adjust calloc call
  } Bigint;
  
  static Bigint* bigint_new(size_t size) 
  {
      Bigint *b = calloc(sizeof(*b) + size - 1, 1); /* calloc zeroes allocated memory */
      if (b) {
          b->size = size;
      }
      return b;
  }
  

• you have no error checking in your input routine - ie. there is no check for characters not in the range '0'..'9'.

• skipping leading zeroes could be better done with strspn. Also, I think you should store your values in the opposite order. This simplifies the loops in add and multiply (see below), so bi_from_string becomes this (note also the const)

  static Bigint* bi_from_string(const char *s)
  {
      s += strspn(s, "0");
      size_t size = strlen(s);
      int min = (size == 0) ? 1 : 0;
  
      Bigint *b = bi_new(size + min);
      for (int i = 0; i < size; ++i) {
          b->data[size - i - 1] = s[i] - '0';
      }
      return b;
  }
  

• your bi_add is a mess. You have too many loop variables and they count downward, which is normally a bad idea. By reversing the storage order of the data in the bi type you can also reverse the loops and avoid so many loop variables. Notice how much simpler the loop is now

  static Bigint* bi_add(const Bigint *a, const Bigint *b)
  {
      size_t max = (a->size > b->size ? a->size : b->size);
      Bigint *c = bi_new(max + 1);
  
      int carry = 0;
      int i;
      for (i=0; i<max; ++i) {
          int tmp = carry;
  
          if (i < a->size) {
              tmp += a->data[i];
          }
          if (i < b->size) {
              tmp += b->data[i];
          }
          carry = tmp / 10;
          c->data[i] = tmp % 10;
      }
      if (carry) {
          c->data[i] = 1;
      } else {
          c->size--; //extra space added for growth of value was not used
      }
      return c;
  }
  

• your bi_multiply is also rather messy. It suffers the same problems as bi_add but compounds this with a nested loop. Nested loops are sometimes necessary but more often than not can be usefullly split into two functions. Here is an example of multiplying with two separate functions:

  static signed char* bi_multiply_by_n(const Bigint *a, int n, signed char *result)
  {
      int carry = 0;
      for (int i=0; i<a->size; ++i) {
          int tmp = carry + (a->data[i] * n) + *result;
          carry = tmp / 10;
          *result++ = tmp % 10;
      }
      if (carry) {
          *result++ = carry;
      }
      return result; // pointer to char beyond end of result
  }
  
  static Bigint* bi_multiply(const Bigint *a, const Bigint *b)
  {
      size_t max = a->size + b->size;
      Bigint *c = bi_new(max);
      signed char *end;
  
      for (int i=0; i<b->size; ++i) {
          end = bi_multiply_by_n(a, b->data[i], c->data + i);
      }
      c->size = end - c->data; // actual space used
      return c;
  }
  

Note that I tested these functions, so they should be ok.

Answer 3

You're right to suspect the data++, data-- lines, but I'm not sure "leaking memory" is the worst of your problems. If you pass one of these "offset from the original allocation" addresses into realloc or free, for example, you're likely to get crashes. The way it usually works under the hood is that at an address just before the buffer, malloc and friends sneak in things like the allocation size, so it can maintain its own data structures ahead of "your" buffer. (It's not guaranteed to work that way, but this is most often the case.) The important takeaway is that if you call malloc, save the original pointer so that you have something to pass to free.

For that particular issue I would recommend one of the following:

• Option A: Store the original allocation (what was returned from malloc) in your struct alongside any pointers derived from it (data).

• Option B: Instead of doing pointer arithmetic on data, store the current index in the struct as an integer, and access with p->data[p->idx]. Thinking about it some more I think this is the cleaner approach. For example you wouldn't need to re-calculate the offset again after a realloc.

Which brings me to the next point. I don't see any calls to free. For a structure like this I think it's good practice to have a single alloc function (which is good, you already have that) and a single free function. So let's write the latter:

void bi_free(bi *b)
{
   if (b)
   {
      free(b->data);
      free(b);
   }
}

While on the topic of your alloc function, it'd be a good idea to initialize the struct.

bi *bi_new() {
    bi *a = malloc(sizeof(bi));
    if (a)
    {
       a->data = NULL;
       a->size = 0;
    }
    return a;
}

Note that malloc can fail, so we don't initialize anything in that case. (Callers of bi_new() should do the same check.)

Actually your allocation also highlights something:

    bi *a = malloc(sizeof(bi));

See the part where you type "bi" twice? Let's say you wanted to change the type of a later on to some other struct. Now there's two places you have to update it. I would much prefer:

    bi *a = malloc(sizeof(*a));

On the topic of heap allocations... It seems like every bi operation takes 2 bis and does a new allocation for a return value. This is a bit subjective, but that seems tedious. What about an interface which takes two operands, where one is also a destination? (Like many assembly languages..) Or perhaps 2 source operands and 1 destination. (Like RISC.) Each operation could see if the destination is big enough and possibly call realloc to grow the buffer. But the caller would decide to free the operands, and you'd probably get plenty of buffer re-use.

Answer 4

Couple of other comments:

1) How are you handling negative numbers?

2) Since the numbers per digit stored is in the range 0-9 does it require to be an int type? Why it can't be unsigned char type?

Considering above this is my suggestion for the bigint struct (assuming c99 standard):

struct bigint {
    bool negative;
    size_t num_digits;
    unsigned char *digits;
};