c - 将字符串中的两个任意数字相乘

Question

我编写了以下代码来执行 C 中 char * 中存储的 2 个任意数字之间的乘法:

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

void    mult(char *n1, char *n2)
{
  char  *res;
  int   mul, i, j;

  res = malloc(sizeof(*res) * (strlen(n1) + strlen(n2) + 1));
  memset(res, '0', strlen(n1) + strlen(n2));
  res[strlen(n1) + strlen(n2)] = 0;
  for (i = strlen(n1) - 1; i >= 0; i--)
  {
     for (j = strlen(n2) - 1; j >= 0; j--)
     {
        mul = (n1[i] - '0') * (n2[j] - '0');
        res[i + j] += ((res[i + j + 1] + mul - '0') / 10);
        res[i + j + 1] = ((res[i + j + 1] + mul - '0') % 10) + '0';
      }
    }
  printf("%s\n", res);
  free(res);
}

我使用 -O3 标志编译它，但对于 86 k 位的大数字大约需要 30 秒。 我怎样才能让它更快？

Answer 1

总结评论:

• 尽量避免整数除法。例如。与查找表。两位数的乘积意味着最大为 9^2。使用/10 或 %10 的结果作为另一个。
• 确保存储 strlen() 调用，并为其显式指定变量。
• 单独执行 +/-'0' trafo。
• 考虑以 10000 为基数的建议。

也许使用专用结构(动态数组+维护的大小信息)会比字符串更好。仅当需要进行数字 I/O 时才执行长度和 +/-'0'。