长整数－－乘法

代码下载：

git clone git://git.code.sf.net/p/cutility/code cutility-code

长整数总共有两个文件一个为big_integer.h，一个为big_integer.c

在看这一篇文章这前你需要了解长整数的数据结构

(一)简介

在长整数数据结构与接口中提到了，长整用一个一维的数组来保存数值，数组类型为unsigned short，在c语言中unsigned short为16位，但是只使用了当中的低15位，这是因为做加法运算的时候，可以把最高位用于进制标志，以减少加法运算处理的复杂度。但是还没有说明为什么使用unsigned short类型的数组来存储数值。下面来解释

在32位机，一次能处理的最大位宽为32位。两个16位的数相乘，得到的结果最大为32位，不会超过处理器的最大位宽，更何况在BGInteger中，只使用了b_val数组中每一个元素的低15位，意为着，得到的结果不会超过30位。这样就可以用一个long或者是int型的变量来存储结果，而不会产生数值溢出，这样有利于乘法的处理。

例如，a与b相乘，结果为c

其中：

1. a的数值为'3555'，转换为二进制为'110111100011'，总共12位，即a.b_val[0]='110111100011'
2. b的数值为'6789'，转换为二进制为'1101010000101'，总共13位，即b.b_val[0]='1101010000101'

a与b相乘，如下图：

结果为'1011100000100010011101111'，总共25位，把低15位保存在c.b_val[0]中，即c.b_val[0]='100010011101111' 高10位保存在c.b_val[1]中，即c.b_val='1011100000'

用c语言实现为：

twob_unit result=(twob_unit)a.b_val[0]*b.b_val[0]
c.b_val[0]=result&MASK
c.b_val[1]=(result>>SHIFT)MASK

把结果'1011100000100010011101111'用十进制表示为'24134895'，刚好为3555*6789的值。

(二)乘法

(1)两长整数绝对值相乘

就像在初中时代时，要计算两个数相乘的结果，当时没有不能用计算器，也没有电脑，唯一能用的就是一张草稿纸和一只笔。当在草稿纸让计算时，通常会有以几个步骤。

例如233*45，会先计算233*5的值如下

再计算233*4值：

最后在把两数相加

两个长整数相乘的算法与上面讲的在草稿纸上做运算的方法类似，算法描述为：

上面的算法要求两个乘数都为正数，x与y相乘后保存的结果保存于w中。

代码实现为：

static BGInteger* abs_mul(BGInteger* l,BGInteger* r)
{

    int l_len=abs(l->b_len);  /*因为数值使用原码方法来表示*/
    int r_len=abs(r->b_len);  /*求绝对值只需要忽略符号位即可*/
    if(l_len==0||r_len==0)   /*如果当中有一个数为0，那么直接返回0*/
    {
        return bg_create_zero();
    }
    int t_len=l_len+r_len;   /*两长整数分别为k位和n位，他们相乘的结果不会超进k+n位*/
    BGInteger* ret=bg_malloc(t_len); /*所以最多需要分配t_len个数组空间*/
                                     /*t_len=l_len+r_len*/

    b_unit* l_val=l->b_val;
    b_unit* r_val=r->b_val;
    b_unit* t_val=ret->b_val;

    int i,j;
    for(i=0;i<r_len;i++)        /*上图中算法步骤2*/
    {
        b_unit c=0;             /*步骤2.1 c<-0 */
        for(j=0;j<l_len;j++)    /*步骤2.2 j from 0 to n */
        {
            /*Compute(uv)=w[i+j]+x[i]y[i]+c */

            twob_unit val=(twob_unit)t_val[i+j]+l_val[j]*r_val[i]+c;

            t_val[i+j]=val&MASK; /*w[i+j]<-v*/
            c=val>>SHIFT;        /*set c<-u */
        }
        t_val[i+l_len]=c;      /*步骤2.3 w[i+n+1]<-u*/
    }

    bg_format_len(ret);
    return ret;
}

(2)长整数乘法

上面只是实现了两长整数绝对值相乘，要实现长整数相乘，还需要处理符号：

1. 两正数相乘，结果为正
2. 正数与负数相乘，结果为负
3. 两负数相乘，结果为正

代码实现为：

BGInteger* bg_mul(BGInteger* l,BGInteger* r)
{
    BGInteger* ret=abs_mul(l,r);    /*绝对值相乘*/
    if((l->b_len<0)!=(r->b_len<0))   /*判断两数符号是否相同*/
    {
        self_negative(ret);         /*如果一正一负，则结果置负*/
    }
    return ret;
}