我有一个非常大的数字（> 100位数字长）所以它不能存储为int甚至unsigned long long (aka uint64_t)。该数组如下所示：
{5, 1, 2 ... 8, 6}
该数组必须包含单个数字ints。
题
将这个“数字”（保持为数组）乘以一个数字的简单，最重要的有效方法是什么？
我试过了什么
因为我对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 ++。
根据要求，这是一个代码示例，它将数组乘以一个数字。该数组是little-endian。举一个简单的例子，我假设数组是固定长度的，一个更复杂的数组将分配数组内存并在数组变得太大时扩展它。
#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基数的功率更容易，并且不使用存储类型的全部容量会有很小的时间损失。
所以有一些观察：
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，这可以提高由于缓存效果的速度。
您的代码中存在多个问题。不确定我是否发现了所有这些，但这里有一些开始。
这个循环：
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中计算了结果，所以你返回了错误的数组。
但是 - 在任何情况下都不允许返回指向本地数组的指针！函数返回时，它将超出范围。即使你这样做：
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
但请注意，这不是最佳解决方案......