大整数乘法(Java)
程序员文章站
2022-07-15 10:29:41
...
先看代码再解释:
public static int [] bigMulti(int a[], int b[])
{
int alen = a.length;int blen = b.length;
int result[] = new int[alen+blen];
for(int i = b.length - 1; i>=0; i--)
{
for(int j = a.length - 1; j>=0; j--)
{
result[i+j] += b[i]*a[j];
}
}
for(int n = result.length - 1; n > 0 ; n--)
{
int c = result[n]/10;
result[n] = result[n]%10;
result[n-1] += c;
}
int trueres[] = new int[result.length -1];
System.arraycopy(result, 0, trueres, 0, result.length -1);
return trueres;
}
原理和小学学的多位乘法是一样的。
例如:
体现分治法就是:把两个长整数的乘法拆分成多个每个位对应的乘法,然后求和。
上面的算法实现就是基于上图原理。至于能不能对无限长的整数相乘,留待网友验证。
上面的算法并没有对负数进行处理,博友可以自己进行预处理。