使用C中的数组对非常大的数进行除法 [英] Division of very big numbers using arrays in C

问题描述

我正在尝试为一个非常大的数字(甚至比长整长的整数大)制作一个计算器，并且正在使用数组来使其工作.

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.

新进展.正如朋友提到的，我每次都需要将结果数组与除数进行比较，以便在除数大于被除数的任何时候都可以停止进度.我设法做出了一个很好的函数来每次进行比较.此功能经过单独测试，工作正常.好的.现在，我开始取得真正的进步.我有商.现在，我将尝试将商数放入数组中，以便我们可以处理更大的数字！

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
}

推荐答案

如果您将这些大数相减，最简单的解决方案是取两个数，并将一个数与另一个相减，直到剩下的东西小于零为止. .这是基本的解决方案，它可以工作，但速度有点慢.

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.

要使其更快，您可以执行以下操作:将除数乘以2，如果除数小于股息，则继续乘.当您到达的第一个数字更大时，则将相应的位设置为1，然后减去相乘后的结果，然后对结果进行相同的操作. 在 wiki 上也有很好的描述.

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.

为了使其工作，您需要实现自己的比较功能. 假设您将malloc分配的大小存储在文件结构len中，则可以执行以下操作:

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

这篇关于使用C中的数组对非常大的数进行除法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！