Chinaunix首页 | 论坛 | 博客
  • 博客访问: 325862
  • 博文数量: 32
  • 博客积分: 424
  • 博客等级: 准尉
  • 技术积分: 465
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-02 10:23
文章分类

全部博文(32)

文章存档

2012年(32)

分类: C/C++

2012-03-11 20:01:50

代码下载:
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语言实现为:

  1. twob_unit result=(twob_unit)a.b_val[0]*b.b_val[0]
  2. c.b_val[0]=result&MASK
  3. c.b_val[1]=(result>>SHIFT)MASK
把结果'1011100000100010011101111'用十进制表示为'24134895',刚好为3555*6789的值。

(二)乘法

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

就像在初中时代时,要计算两个数相乘的结果,当时没有不能用计算器,也没有电脑,唯一能用的就是一张草稿纸和一只笔。当在草稿纸让计算时,通常会有以几个步骤。
例如233*45,会先计算233*5的值如下
再计算233*4值:
最后在把两数相加

两个长整数相乘的算法与上面讲的在草稿纸上做运算的方法类似,算法描述为:
上面的算法要求两个乘数都为正数,x与y相乘后保存的结果保存于w中。

代码实现为:

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

  13.     b_unit* l_val=l->b_val;
  14.     b_unit* r_val=r->b_val;
  15.     b_unit* t_val=ret->b_val;

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

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

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

  29.     bg_format_len(ret);
  30.     return ret;
  31. }

(2)长整数乘法

上面只是实现了两长整数绝对值相乘,要实现长整数相乘,还需要处理符号:
  1. 两正数相乘,结果为正
  2. 正数与负数相乘,结果为负
  3. 两负数相乘,结果为正
代码实现为:

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



阅读(4578) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~