Division of very big numbers using arrays in C

Question

I'm trying to make a calculator for very big numbers (even bigger than long long) and I'm using arrays to make it work.

So far I have done addition, subtraction and multiplication. But I'm really stuck in division part.

EDIT: new progress. as a friend mentioned i need to compare result array with divisor each time so i can stop the progress any time divisor is larger than dividend. I managed to make a nice function to compare it every time. this function is tested separately and it's working fine. OK. now i'm starting to make REAL progress. i got the quotient. now i will try to put quotient in array so that we can work with LARGER numbers!

    #define MAX_SIZE 50
    #define SIZE_USE (MAX_SIZE-1)

    int div(int inum_first[], int inum_second[], int div_result[], int firstlen, int secondlen)
{
    int i;
    int check1 = 0, check2 = 0;

    int zeroC = 0;

    int tmp[MAX_SIZE];

    for (i = 0; i <= SIZE_USE; i++)
    {
        tmp[i] = 0;
    }

    int inum_firstCP[MAX_SIZE] = { 0 };

    for (i = 0; i <= 1; i++)
    {
        inum_firstCP[i] = inum_first[i]; // create a copy of inum_first
    }

    for (i = 0; i <= SIZE_USE; i++)
    {
        if (inum_first[i] != 0)
            check1++;

        if (inum_second[i] != 0)
            check2++;
    }

    if (secondlen > firstlen)
    {
        zeroC++;
        goto EOI;
    }

    if (check2 == 0)
    {
        puts("\nExpected error\n");
        return -1;
    }

    int j = 0, p = 0;

    int s = 0;
    int o = 1; // o is Quotient!

    do
    {
        for (i = SIZE_USE; i >= 0; i--)
        {
            if (tmp[i] = inum_firstCP[i] - inum_second[i] >= 0)
            {
                tmp[i] = inum_firstCP[i] - inum_second[i];
            }
            else
            {
                inum_firstCP[i - 1] = inum_firstCP[i - 1] - 1;
                tmp[i] = (inum_firstCP[i] + 10) - inum_second[i];
            }

            inum_firstCP[i] = tmp[i];

        }
    if (compare(inum_firstCP, inum_second, firstlen, secondlen) < 0) break;
    j++;
    o++;
    } while (j<MAX_SIZE); // anything else will also work

EOI:

    return 0;
}

int compare(int inum_firstCP[], int inum_second[], int firstlen, int secondlen)
{
    int c = 0, d = 0;
    int i;

    firstlen = MAX_SIZE, secondlen = MAX_SIZE; // temporary. will provide a better solution ASAP
    if (firstlen > secondlen)
    {
        return 1;
    }
    else if (secondlen > firstlen)
    {
        return -1;
    }
    else
    {
        for (i = 0; i < firstlen; i++)
        {
            if (inum_firstCP[i] > inum_second[i]) c++;
            else if (inum_second[i] > inum_firstCP[i]) d++;
        }
        if (c>d) return 1;
        else if (d>c) return -1;
    }

    return 0; // else
}

Answer 1

If you have the subtraction of those big numbers the easiest solution is to take the two numbers and substract one from the other until you are left with something less then zero. It is the basic solution, it works but is a bit slow.

To make it faster you can do the following, take the divisor, multiply it by 2, if it is less then the dividend, keep on multiplying. When you will reach the first number bigger then a dividend set the corresponding bit to 1, subtract the multiplied dividend then do the same for the result. There is the same thing nicely described on wiki.

In order to make it work you need to implement your own comparing function. Assuming you will store the size of the malloc allocation in your structure in filed len you can do something like this:

int compare( mynum &a, mynum &b){
  if (a.len() > b.len()){
     return 1;
  } else (if b.len() > a.len()){
   return -1;
  } else(){
    for(int i = b.len(); i > 0; i--){
      if (a[i] > b[i]){
        return 1;
      } else if(b[i] > a[i]){
        return -1;
      }
     }
   #if we get there the numbers are the same
   return 0;
  }
}