作者tmbyksdG (雨神妹妹的男朋友)
看板C_and_CPP
標題[問題] 大整數乘法改寫(C++ to CUDA C)
時間Tue Jan 3 17:16:59 2017
開發平台(Platform): (Ex: Win10, Linux, ...)
Linux上安裝CUDA環境 (CUDA版本為8.0 運算能力為3.7)(Tesla K80)
編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出)
NVCC
額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
問題(Question):
研究上要作大整數乘法,我找到一個可以成功執行的程式,只不過這個程式是用C++寫的
,並且其中的fft是使用複數的方式來做計算。我想把它改成CUDA C版本,並且其中的fft
是用整數來做運算,請問這樣是可行的嗎?程式我自己有先看過了,大概了解每一個func
tion的動作,但是其中還有一些小細節看不太懂(不懂的地方我有註解),請各位大大幫
我看看,謝謝。
餵入的資料(Input):
預期的正確結果(Expected Output):
錯誤結果(Wrong Output):
程式碼(Code):(請善用置底文網頁, 記得排版)
#include <iostream>
#include <cmath>
#include <complex>
#include <cstring>
using namespace std;
const double PI = acos(-1.0);
typedef complex<double> cp;
typedef long long int64;
const int N = 1 << 16;
int64 a[N], b[N], c[N << 1];
void bit_reverse_copy(cp a[], int n, cp b[])
{
int i, j, k, u, m;
for (u = 1, m = 0; u < n; u <<= 1, ++m);
for (i = 0; i < n; ++i)
{
j = i; k = 0;
for (u = 0; u < m; ++u, j >>= 1)
k = (k << 1) | (j & 1);
b[k] = a[i];
}
}
void FFT(cp _x[], int n, bool flag) // bool flag怎麼改成c版本參數?
{
static cp x[N << 1];
bit_reverse_copy(_x, n, x);
int i, j, k, kk, p, m;
for (i = 1, m = 0; i < n; i <<= 1, ++m);
double alpha = 2 * PI;
if (flag) alpha = -alpha; //這行是什麼意思?
for (i = 0, k = 2; i < m; ++i, k <<= 1)
{
cp wn = cp(cos(alpha / k), sin(alpha / k));
for (j = 0; j < n; j += k)
{
cp w = 1, u, t;
kk = k >> 1;
for (p = 0; p < kk; ++p)
{
t = w * x[j + p + kk];
u = x[j + p];
x[j + p] = u + t;
x[j + p + kk] = u - t;
w *= wn;
}
}
}
memcpy(_x, x, sizeof(cp) * n);
}
void polynomial_multiply(int64 a[], int na, int64 b[], int nb, int64 c[], int
&nc)
{
int i, n;
i = max(na, nb) << 1;
for (n = 1; n < i; n <<= 1);
static cp x[N << 1], y[N << 1];
for (i = 0; i < na; ++i) x[i] = a[i];
for (; i < n; ++i) x[i] = 0;
FFT(x, n, 0);
for (i = 0; i < nb; ++i) y[i] = b[i];
for (; i < n; ++i) y[i] = 0;
FFT(y, n, 0);
for (i = 0; i < n; ++i) x[i] *= y[i];
FFT(x, n, 1);
for (i = 0; i < n; ++i)
{
c[i] = (int64)(x[i].real() / n + 0.5);
}
for (nc = na + nb - 1; nc > 1 && !c[nc - 1]; --nc);
}
const int LEN = 5, MOD = 100000;
void convert(char *s, int64 a[], int &n)
{
int len = strlen(s), i, j, k;
for (n = 0, i = len - LEN; i >= 0; i -= LEN)
{
for (j = k = 0; j < LEN; ++j)
k = k * 10 + (s[i + j] - '0');
a[n++] = k;
}
i += LEN;
if (i)
{
for (j = k = 0; j < i; ++j)
k = k * 10 + (s[j] - '0');
a[n++] = k;
}
}
void print(int64 a[], int n)
{
printf("%I64d", a[--n]);
while (n) printf("%05I64d", a[--n]);
puts("");
}
char buf[N + 10];
int main()
{
int na, nb, nc;
while (scanf("%s", buf) != EOF)
{
bool sign = false; //這行是什麼意思?
if (buf[0] == '-')
{
sign = !sign; // 這行是什麼意思?
convert(buf + 1, a, na);
}
else convert(buf, a, na);
scanf("%s", buf);
if (buf[0] == '-')
{
sign = !sign;
convert(buf + 1, b, nb);
}
else convert(buf, b, nb);
polynomial_multiply(a, na, b, nb, c, nc);
int64 t1, t2;
t1 = 0;
for (int i = 0; i < nc; ++i)
{
t2 = t1 + c[i];
c[i] = t2 % MOD;
t1 = t2 / MOD;
}
for (; t1; t1 /= MOD) c[nc++] = t1 % MOD;
if (sign) putchar('-');
print(c, nc);
}
return 0;
}
補充說明(Supplement):
大整數乘法中有一個mod p(質數)的運算,論文上選擇的p=0xFFFFFFFF00000001,我該
怎麼在程式中定義一個這麼大的變數呢?如果我只要讓GPU作fft運算,是否只要將fft那
個function改寫成cuda函式就可以了呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.136.45.205
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1483435022.A.D71.html
1F:推 nick5130: sign是為了處理負數01/03 18:3
2F:推 nick5130: flag也是為了處理負數01/03 18:45
3F:→ nick5130: c沒有bool你用int 0跟1就可以處理了01/03 18:45
4F:→ nick5130: 然後我不懂你是為了什麼要用CUDA01/03 18:46
5F:→ nick5130: 如果你是為了加速運算,這種程度的運算改成CUDA只會變慢01/03 18:47
6F:→ nick5130: 如果你是為了交差就當我沒說就好01/03 18:47
謝謝nick大,會使用CUDA是為了實現論文上的大整數數乘法(65536點的FFT,大整數可達2
的786432次方),是為了加速運算沒錯。想用這個程式去改的原因是,作者有註明可以支
援到30萬位元整數乘法,這個運算量對GPU來說,應該也不算小才是阿,為什麼會變慢呢
?
謝謝p大,不過這個fft程式似乎也是使用複數的方式做運算,不是用整數的方式。
8F:→ Sylveon: 不想小數運算可以用數論變換ntt來做,可是大量的取模以01/03 19:51
9F:→ Sylveon: 防及溢位的細結放一起後,實測上沒fft快01/03 19:51
10F:推 lc85301: 我記得沒錯的話fft 要到1000 bit 以上才有競爭力01/04 11:38
※ 編輯: tmbyksdG (59.115.156.82), 01/05/2017 00:55:46
※ 編輯: tmbyksdG (59.115.156.82), 01/05/2017 01:01:23
11F:推 nick5130: CUDA可能比較慢的原因是在PCIE的頻寬01/05 09:21
12F:→ nick5130: 加上個人認為你對C不太熟01/05 09:23
13F:→ nick5130: 如果這只是你其中一部分研究 可以考慮改multi thread就01/05 09:23
14F:→ nick5130: 好01/05 09:23
15F:→ nick5130: 如果真的還是覺得慢再評估要不要改成CUDA 01/05 09:24
16F:→ nick5130: 一樣project改成multi thread跟cuda所需時間絕對不同 01/05 09:25
17F:→ nick5130: 也不是說改成CUDA就一定會比multi thread快的 01/05 09:25
18F:→ nick5130: 其他比較慢的原因就是演算法的問題了 這邊你可以翻看看 01/05 09:31
19F:→ nick5130: 一般cuda的tutorial看看再和你這個比比看 01/05 09:31
20F:→ nick5130: 簡單說就是平行化的問題 大概就這樣 01/05 09:32
之前學完C之後,的確有一段時間沒有繼續碰它,這學期修資料結構,才又開始惡補這樣
。我想請教nick大,如何在具有C的基本知識條件下,進一步去加強寫C的能力。平行化相
關的知識有沒有推薦的書籍?我的研究必須用CUDA來實現來實現,利用其他途徑目前是不
考慮的。
21F:→ pttworld: 實數、虛數計算和整數定義不一樣,感覺難以達成。 01/05 10:50
22F:→ a1u1usul3: 樓主好像對C/CPP也不熟,對平行化也不熟 01/05 12:37
是的,我的確沒學過CPP。我想請教a大,如何在具有C的基本知識條件下,進一步去加強
寫C的能力。平行化相關的知識有沒有推薦的書籍?
23F:→ a1u1usul3: 先用openmp加速,熟悉這個程式,想好相依性和可平行化 01/05 12:38
24F:→ a1u1usul3: 的部分,再改cuda吧。 01/05 12:38
25F:推 friends29: 是可以用cuda啦 只是你的寫法不好的話 效率不會比較好01/06 20:57
※ 編輯: tmbyksdG (114.136.66.135), 01/09/2017 12:55:00
26F:→ sunneo: 你乾脆用cufft ... 02/02 21:30