|
|
|---|---|
|
|
我说一下我的思路，不知道可行否，还望大侠莫笑
 第一步： 9999999999 + 9999999999 ---------------------------- 值 8888888888 进位 1111111111 第二步： 进位左移1位 ，变为 11111111110 8888888888 + 11111111110 ---------------------------- 19999999998 进位 00000000000 依次类推，直到进位全为0，结束。
|
|
|
|
|
|
感谢回复。这个方法我也想过，首先每个线程分别计算 a[i] + b[i]，结果存入c[i]，然后保存每一位的进位情况，再把进位并行的加回去（如果进位部分用串行从低位循环加上去，第一步的拆分就没有意义了）。
问题是不一定刚好结果是 8888888888 + 11111111110 这样不会出现二次进位的结果，最糟糕的莫过于： 假设每个线程负责竖着将每一位相加： 嗯，分段计算可能是没有办法的办法。主要是怎么分段的问题，分过细了没有意义（比如一个n=2048的a[n]，按4分段计算的话，段间还是需要循环512次），但是分太粗了又没有有效利用起GPU的计算能力（比如按64分段的话，只有32个线程在同时工作，在一些高档显卡上能并行的线程数远远大于这个） 而且本来设计上就利用了32位处理器计算的特点，a[n] 数组使用4字节的DWORD类型，这样计算 c[i] = a[i] + b[i] 的速度有所提升不说，进位处理的次数也会减少到1/4（相对于用BYTE存储来说）。 我对这个并行加法比较纠结的原因是因为加法是后面大多数计算的基础，这个速度上有细微提升都会对整个大数计算带来很大帮助。 希望大家畅所欲言 
|
|
|
|
|
|
这个实现起来可能不是很方便，因为要是为了进位去操作别的线程负责的数据块（比如线程i为了进位，按你这个思路可能会去修改i+1、i+2、i+3...这些数据块），这个需要涉及读写同步的问题，因为可能 i+1 的线程刚计算出结果，还没写入 c[i+1] 里面，而低位线程i负责计算的 c[i] 发生进位，提前 c[i+1]++，这样数据就乱套了。
多线程限制其实也很多 
|
|
|
|
