作者sunbig (hi)
看板C_and_CPP
标题Re: [问题] 请问关於大数运算 乘法的问题
时间Thu Jul 27 16:06:41 2006
※ 引述《latinboy (昵称)》之铭言：
: ※ 引述《sunbig (hi)》之铭言：
: : 现在我已经将 加法与减法实做完
: : 本来很天真的以为
: : 如果要让一个数
: : 0x0000000f*0x0000000e
: : 我就是把乘数连加倍成数的次数
: : 後来发现
: : 只要超过1byte 时间根本不能看
: : 不知道有没有高手知道 大数运算乘法比较有效率的方式
: : btw 我的数是使用 unsigned long
: : 一个byte由 0~0xffffffff还要考虑很多byte的问题
: : 我今天卡一添了
: : 不知道有没有人有经验 请指导一下
: 用2*2乘法来讲解一下最简单的16进位直式大数乘法
: a[1] a[0] b[1] b[0] c[0~3]
: ffffffff-ffffffff * aaaaaaaa-aaaaaaaa = ?
: ffffffff-ffffffff
: X aaaaaaaa-aaaaaaaa
: ----------------------------------------------
: AAAAAAA9-55555556 --> (long long) a[0]*b[0]
: AAAAAAA9-55555556 --> (long long) a[1]*b[0]
: AAAAAAA9-55555556 --> (long long) a[0]*b[1]
: AAAAAAA9-55555556 --> (long long) a[1]*b[1]
: ----------------------------------------------
: AAAAAAAA-AAAAAAA9-55555555-55555556
: 以上是概念
: 程式码:
: unsigned long a[2],b[2],c[4];
: unsigned long long temp;
: for( i = 0; i < 2; i++ )
: for( j = 0; j < 2; j++ ) {
: temp = c[i+j];
: temp += a[i] * (unsigned long long) b[j];
: c[i+j] = (unsigned long) temp;
: c[i+j+1] += (unsigned long) (temp >> 32); //进位
: }
: }
这段程式有bug 我把他 处理掉了
回馈一下 给大家
他没有处理 如果再进行加法时候 产生溢位的问题
所以 上面的程式 跑完 最前面的aaaaaaaa=>aaaaaaa9
不过还是很感谢 提供方式 太感恩了
void mul(unsigned long *a,unsigned long *b,unsigned long *c,int lena,int lenb,int lenc){
int i,j ;
unsigned __int64 temp,temp2;
for(i = 0;i < lena;i++){
for(j = 0;j < lenb ; j++){
temp = c[i+j];
temp += a[i] * (unsigned __int64) b[j];
printf("after added is %x",temp);
c[i+j] = (unsigned long) temp;
printf("in c[%d] is %x\n",i+j,c[i+j]);
temp2 = c[i+j+1] + (temp>>32);
c[i+j+1] = (unsigned long)(temp2);
printf("the temp latter is %x\n",temp);
printf("the temp former is %x\n",(temp>>32));
c[i+j+1+1] = (temp2>>32);
}
}
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.124.166.19
1F：→ latinboy:我只是示意一下 进位问题不是重点 XD 07/27 16:12