作者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