Re: [問題] 請問關於大數運算 乘法的問題
※ 引述《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
→
07/26 19:37, , 1F
07/26 19:37, 1F
→
07/26 19:37, , 2F
07/26 19:37, 2F
→
07/26 20:59, , 3F
07/26 20:59, 3F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
