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
在看这一篇文章这前你需要了解长整数的数据结构
- 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
- 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;
- }
- 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;
- }