在C中将数字数组乘以int

Question

我有一个非常大的数字（>100 位），所以它不能存储为 int 甚至 unsigned long long (aka uint64_t)。该数组如下所示：
{5, 1, 2 ... 8, 6}
该数组必须包含单个数字 ints.

问题

将此 'number'（将其保存为数组）乘以一个数字的简单且最重要的有效方法是什么？

我试过的

由于我是 C 的新手，所以这段代码不是杰作。差远了。

struct returnpointer { int * pointer; int length; };

returnpointer mul_arrays(int * x, int y, int lengthof_x) {
    returnpointer result_end;
    int result[lengthof_x * 2 + 1];
    int final_result[lengthof_x * 2 + 1];
    int carry = 0;
    int j = 0;
    //multiply 'y' by all digits of x, which creates multidigit ints
    //and also reverses the direction of the array (to allow carrying)
    for (int i = lengthof_x; i >= 0; i--) {
        result[j] = x[i] * y;
        j++;
    }
    int i = 0;
    j = lengthof_x
    //this is the bit that doesn't work: it attempts to work out the carry
    //however after hours of debugging I can't get it to work.
    while (carry > 0 || i < lengthof_x + 1) {
        if (result[j] > 9) {
            carry = result[j] / 10;
            final_result[i] = result[j] % 10;
            final_result[i + 1] = carry;
        } else {
            final_result[i] = result[j];
            carry = 0;
        }
        i++;
        j--;
    }
    result_end.pointer = result;
    result_end.length  = i + 1;
    return result_end;
}

此代码无法正常工作。这只是我尝试过的示例（如果有效，我就不会发布）。

此外，很高兴知道我正在（尝试）使用的方法是否最有效，因为它将合并到的程序非常耗时，因此功能越快，时间越短整个程序将需要。

提前致谢。

编辑：

我的编译器是g++。

Answer 1

所以一些观察：

1) 我觉得没必要倒数组。只需从最低有效位到最高有效位处理即可。

2) 没有理由存储大于您允许的数字范围的临时值。边走边做，就像你用手做的那样：

carry = 0
for i in all_the_digits:
    product = x[i]*y + carry
    x[i] = product%10
    carry = product/10

3) 您可以将数字存储为 uint8_t 而不必担心溢出 - 这将使您的数组成为当前大小的 1/4，由于缓存效应，这应该会提高速度。

Answer 2

根据要求，这是一个将数组乘以单个数字的代码示例。该数组是小端的。举一个简单的例子，我假设数组是固定长度的，一个更复杂的例子会分配数组内存并在数组增长太大时扩展它。

#include <stdio.h>

#define BIGLEN 20

typedef struct {
    int length;
    int array[BIGLEN];
} biggy_t;

void bigmul(biggy_t *big, int mul)
{
    int carry = 0, partial;
    for(int i = 0; i < big->length; i++) {
        partial = big->array[i] * mul + carry;
        big->array[i] = partial % 10;
        carry = partial / 10;
    }
    if(carry) {
        big->array[big->length] = carry;
        big->length++;
    }
}

void bigout(biggy_t *big)
{
    for(int i = big->length-1; i >= 0; i--) {
        printf("%d", big->array[i]);
    }
}

int main(int argc, char *argv[])
{
    biggy_t big = { 6, { 5, 1, 2, 3, 8, 6 }};   // reverse order
    bigout(&big);
    printf(" * 7 = ");

    bigmul(&big, 7);
    bigout(&big);
    printf("\n");
}

程序输出

683215 * 7 = 4782505

我写了一个 bignum 实现，我可以在其中选择基数。 10 或 100 字节存储，32 位存储更多。坚持 10 的幂比 2 基数的幂更容易转换为十进制输出，但由于未使用存储类型的全部容量而导致的时间损失很小。

Answer 3

您的代码中存在多个问题。不确定我是否发现了所有这些，但这里有一些可以开始。

这个循环：

for (int i = lengthof_x; i >= 0; i--) {
    result[j] = x[i] * y;
    j++;
}

执行"lengthof_x + 1"次。换句话说 - 一次太多了！您想将其更改为：

for (int i = lengthof_x - 1; i >= 0; i--) {  // notice the "- 1"
    result[j] = x[i] * y;
    j++;
}

你还有：

result_end.pointer = result;

但您似乎已经在变量 final_result 中计算了结果，所以您 return 输入了错误的数组。

但是 - 在任何情况下你都不允许到return一个指向本地数组的指针！当函数 returns 时它将超出范围。所以即使你这样做：

result_end.pointer = final_result;

仍然是无效代码。您需要 malloc 数组（这会影响性能）。

那么你有：

result_end.length  = i + 1;

所以你在所有个案例中增加了长度。那是错误的。你应该只在有进位时增加。

下面我已尝试修复您的代码，即我已尝试保留您代码的整体结构，以便您可以看到哪里出错了。

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

struct returnpointer { int * pointer; int length; };

void print_num(struct returnpointer * num)
{
        printf("len=%d\nvalue=", num->length);
    for(int i = 0; i <num->length; i++) {
        printf("%d", num->pointer[i]);
    }
}

struct returnpointer mul_arrays(int * x, int y, int lengthof_x) {
    struct returnpointer result_end;
    int result[lengthof_x + 1];

    // Multiply all element and revert array
    int j = 0;
    for (int i = lengthof_x-1; i >= 0; i--) {
        result[j] = x[i] * y;
        j++;
    }

    // Handle carry 
    int carry = 0;
    for (j = 0; j < lengthof_x; j++) {
        result[j] = result[j] + carry;
        carry = result[j] / 10;
        result[j] = result[j] % 10;
    }

    // Did length increase
    if (carry)
    {
        lengthof_x++;
        result[j] = carry;
    }

    // malloc result and revert back to desired format
    j = 0;
    int* final_result = malloc(lengthof_x * sizeof *final_result);
    for (int i = lengthof_x-1; i >= 0; i--) {
        final_result[j] = result[i];
        j++;
    }

    result_end.pointer = final_result;
    result_end.length  = lengthof_x;
    return result_end;
}


int main(int argc, char *argv[])
{
    int arr[] = { 5, 1, 2, 3, 8, 6}; 
    struct returnpointer num = mul_arrays(arr, 2, 6);  // 512386 * 2 -> 1024772
    print_num(&num);
}

输出：

len=7
value=1024772

但是请注意，这不是最佳解决方案...

在C中将数字数组乘以int

Multiply a digit array by int in C

c

arrays

multiplication