【C语言】大数相乘

今天抽空复习了一下，用C语言实现的大数相乘的相关算法。

算法代码如下：

<span style="font-size:18px;"># include<stdio.h>
# include<string.h>
# include<malloc.h>

void multiply(char* a,char* b,char* c)
{
	int i,j,ca,cb,* s;
	ca = strlen(a);
	cb = strlen(b);

	s = (int*)malloc(sizeof(int)*(ca+cb));

	for ( i = 0; i < ca+cb; i++)
	{
		s[i] = 0;
	}

	for ( i = 0; i < ca; i++)
	{
		for ( j = 0; j < cb; j++)
		{
			s[i+j+1] += (a[i]-'0')*(b[j]-'0');
		}
	}

	for ( i = ca+cb-1; i >= 0; i--)
	{
		if ( s[i] >= 10)
		{
			s[i-1] += s[i]/10;
			s[i] %= 10;
		}
	}

	i = 0;
	while ( s[i] == 0)
	{
		i++;
	}

	for ( j = 0; i < ca+cb; i++,j++)
	{
		c[j] = s[i] + '0';
	}

	c[j] = '';
	free(s);
}</span>

用字符数组存储大数字， a 和 b 数组分别代表两个相乘的数字，c 是最终的返回结果。

这段程序通过模拟我们运算的过程达到运算的目的。最精髓的地方在于

s[i+j+1] += (a[i]-'0')*(b[j]-'0');

在我们做数字运算的时候，可以参考一下过程：

? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ?1 ? ? ? ?2 ? ? ? 3?
? ? X ? ? ? ? ? ? ? ? ? ??1 ? ? ? ? 2 ? ? ? ?3 ? ? ? 4
—————————————————————
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 4*1 ? ?4*2 ? ?4*3 ??
? ? ? ? ? ? ? ? ? ? ? ? ? 3*1 ? ? 3*2 ? ?3*1
? ? ? ? ? ? ? ? 2*1 ? ? 2*2 ? ? 2*3
? ? ?1*1 ? ? ?1*2 ? ? 1*3

—————————————————————

之后判断大于 10 进位，加和，得到最终的结果。

疑问：为什么最多就是 i+j 位数呢？ 两个数相乘 一个 n 位 * m 位 ? 结果的位数为 [n+m-1,n+m]

而之所以从 1 开始是为了预留最高位。