[問題] 大整數乘法改寫（C++ to CUDA C）

看板C_and_CPP作者tmbyksdG (雨神妹妹的男朋友)時間7年前 (2017/01/03 17:17)推噓5(5推 0噓 21→)

留言26則, 7人參與討論串1/1

開發平台(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://www.ptt.cc/bbs/C_and_CPP/M.1483435022.A.D71.html

推