作者latinboy (暱稱)
看板C_and_CPP
標題Re: [問題] 請問關於大數運算 乘法的問題
時間Wed Jul 26 17:40:20 2006
※ 引述《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); //進位
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.23.251
1F：→ sunbig:我也想過用UNSIGNED LONGLONG 可是VC INCLUDE不到LIB 07/26 19:37
2F：→ sunbig:請問要INCLUDE哪一個 Q_Q 07/26 19:37
3F：→ latinboy:VC裡面的64bit整數不是long long 是 _int64 07/26 20:59