c - 处理帕斯卡三角形的数字溢出

Question

我正在尝试创建一个最多可打印 70 行的大型帕斯卡三角形。我的代码起初工作正常，但当它到达第 65 行时开始打印出错误的输出。我知道它的问题并且我尝试过使用 GMP。不幸的是，我用来编码的软件不支持 GMP。有没有其他方法可以在不使用 GMP 的情况下做到这一点？

char str;
int value;    
int pascal(int n)
{

    for (int i = 1; i < n + 2; i++)
    {
        unsigned long number = 1;
        for (int j = 1; j < i + 1; j++)  
        {
            if(j == i)
            {
                printf("%lu\n", number);
            }
            else
            {
                printf("%lu ", number);
            }
            number = (number * (i - j) / j);  
        }
    }
    return 0;

}

Answer 1

Is there any other ways that i can do this without using GMP?

在形成诸如 109069992321755544170 之类的数字时，所需的整数数学运算超出了基本的 64 位数学运算，这是一个具有超过 64 个前导有效位的 67 位数字。

虽然最宽的整数 uintmax_t 可能满足超过 64 位的数学需求，但通常只有 64 位。

long double 通常具有相当高的精度(在我的平台上只有 64 位)，但这并不是为了满足 OP 的需要而指定的，并且会调用解决 的通常的 FP 问题整数问题。

幸运的是，所需的扩展数学只是乘法和除法。一个简单但效率不高的字符串乘法和除法可以满足需要。

void string_mult(char *y, unsigned x) {
  size_t len = strlen(y);
  unsigned acc = 0;
  size_t i = len;
  while (i > 0) {
    i--;
    acc += (y[i] - '0') * x;
    y[i] = acc % 10 + '0';
    acc /= 10;
  }
  while (acc) {
    memmove(&y[1], &y[0], ++len);
    y[0] = acc % 10 + '0';
    acc /= 10;
  }
}

unsigned string_div(char *y, unsigned x) {
  size_t len = strlen(y);
  unsigned acc = 0;
  for (size_t i = 0; i < len; i++) {
    acc *= 10;
    acc += y[i] - '0';
    y[i] = acc / x + '0';
    acc %= x;
  }
  while (y[0] == '0' && len > 1) {
    memmove(&y[0], &y[1], len);
    len--;
  }
  return acc;
}

void pascal(unsigned n) {
  printf("%u: ", n);
  for (unsigned i = 1; i < n + 2; i++) {
    char s[100] = "1";
    for (unsigned j = 1; j <= i; j++) {
      printf("%s ", s);
      string_mult(s, i - j);
      string_div(s, j);
    }
    printf("\n");
  }
}

int main() {
  for (unsigned i = 0; i <= 70; i++)
    pascal(i);
}

输出

...
1 70 2415 54740 916895 12103014 131115985 1198774720 9440350920 65033528560 396704524216 2163842859360 10638894058520 47465835030320 193253756909160 721480692460864 2480089880334220 7877932561061640 23196134763125940 63484158299081520 161884603662657876 385439532530137800 858478958817125100 1791608261879217600 3508566179513467800 6455761770304780752 11173433833219812840 18208558839321176480 27963143931814663880 40498346384007444240 55347740058143507128 71416438784701299520 87038784768854708790 100226479430802391940 109069992321755544170 112186277816662845432 109069992321755544170 100226479430802391940 87038784768854708790 71416438784701299520 55347740058143507128 40498346384007444240 27963143931814663880 18208558839321176480 11173433833219812840 6455761770304780752 3508566179513467800 1791608261879217600 858478958817125100 385439532530137800 161884603662657876 63484158299081520 23196134763125940 7877932561061640 2480089880334220 721480692460864 193253756909160 47465835030320 10638894058520 2163842859360 396704524216 65033528560 9440350920 1198774720 131115985 12103014 916895 54740 2415 70 1 

---

经过进一步审查，long double 可能会起作用，但我的努力在 pascal(69) 上失败了。