大整数乘法(Comba 乘法 (Comba  Multiplication)原理)

Comba 乘法以(在密码学方面)不太出名的 Paul G. Comba 得名。上面的笔算乘法,虽然比较简单, 但是有个很大的问题:在 O(n^2) 的复杂度上进行计算和向上传递进位,看看前面的那个竖式,每计算一次单精度乘法都要计算和传递进位,这样的话就使得嵌套循环的顺序性很强,难以并行展开和实现。Comba 乘法则无需进行嵌套进位来计算乘法,所以虽然其时间复杂度和基线乘法一样,但是速度会快很多。还是以计算 123 * 456 为例:

1            2            3

x        4             5            6

-----------------------------------------------

6           12          18

5          10         15

4           8          12

------------------------------------------------

4          13          28         27         18

4          13          28         28           8

4          13          30          8

4          16           0

5          6

0         5

------------------------------------------------------

5           6             0            8             8

和普通的笔算乘法很类似,只是每一次单精度乘法只是单纯计算乘法,不计算进位,进位留到每一列累加后进行。所以原来需要 n * n 次进位,现在最多只需要 2n 次即可。

以上就是 Comba 乘法的原理,不过这里有个比较严重的问题:如何保证累加后结果不溢出。上面的例子,假设单精度数 1  位数,双精度是两位数,那万一累加后的结果超过两位数则么办?那没办法,只能用三精度变量了。在大整数算法中,单精度能表示的最大整数是 2^n - 1(n 是单精度变量的比特数),用三个单精度变量 c2,c1,c0 连在一起作为一个三精度变量(高位在左,低位在右),则 c2 || c1 || c0 能表示的最大整数是 2^(3n) - 1,最多能存放 (2^(3n) - 1) / ((2^n - 1)^2) 个单精度乘积结果。当 n = 32 时,能够存放 4294967298 个单精度乘积结果;当 n = 64 时,能够存放约 1.845 * 10^19 个单精度乘积结果,而我一开始规定 bignum 不能超过 25600 个数位,这样使用三精度变量就可以保证累加结果不会溢出了。

有了上面的铺垫,下面就把 Comba 乘法的思路列出来:

1.先将俩个字符数组从后面开始转换为整数数组;

2.乘以后的数组就是c[i+j]+=a[i]*b[j];

3.c数组从小到大依次进位

4.输出,注意c数组是的0是个位,所以从最后一位开始输出,用ok标志不为0的时候开始输出

 #include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
int main()
{
char a[],b[];
cin>>a>>b;
int x[],y[],c[];
int flag=;
for(int i=;i<;i++)
c[i]=;
for(int i=strlen(a)-;i>=;i--)
x[flag++]=a[i]-'';
int key=;
for(int i=strlen(b)-;i>=;i--)
y[key++]=b[i]-'';
for(int i=;i<flag;i++)
for(int j=;j<key;j++)
c[i+j]+=x[i]*y[j]; for(int i=;i<;i++)
{
if(c[i]>=)
{
c[i+]+=c[i]/;
c[i]%=; }
}
int ok=;
for(int i=-;i>=;i--)
{
if(ok) cout<<c[i];
else if(c[i])
{
cout<<c[i];
ok=; } } return ; }
上一篇:[转]大整数算法[11] Karatsuba乘法


下一篇:N!的阶乘附带简单大整数类的输入输出(暂时没有深入的了解)