开发平台(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/cn.aspx?n=bbs/C_and_CPP/M.1483435022.A.D71.html 谢谢nick大，会使用CUDA是为了实现论文上的大整数数乘法（65536点的FFT,大整数可达2 的786432次方），是为了加速运算没错。想用这个程式去改的原因是，作者有注明可以支 援到30万位元整数乘法，这个运算量对GPU来说，应该也不算小才是阿，为什麽会变慢呢 ？ 谢谢p大，不过这个fft程式似乎也是使用复数的方式做运算，不是用整数的方式。 ※ 编辑: tmbyksdG (59.115.156.82), 01/05/2017 00:55:46 ※ 编辑: tmbyksdG (59.115.156.82), 01/05/2017 01:01:23 之前学完C之後，的确有一段时间没有继续碰它，这学期修资料结构，才又开始恶补这样 。我想请教nick大，如何在具有C的基本知识条件下，进一步去加强写C的能力。平行化相 关的知识有没有推荐的书籍？我的研究必须用CUDA来实现来实现，利用其他途径目前是不 考虑的。 是的，我的确没学过CPP。我想请教a大，如何在具有C的基本知识条件下，进一步去加强 写C的能力。平行化相关的知识有没有推荐的书籍？ ※ 编辑: tmbyksdG (114.136.66.135), 01/09/2017 12:55:00