自己想写个大数库,怎么写效率高？
请论坛的出出主意~~~~~~~~~ 呵呵，期待mathe和gxqcn的注意力，转啊转到这里来:) 从算法复杂度上来看，加法没什么可以优化的，主要在于乘法，而其他算法基本可以由乘法得出。对于两个长度为n位的整数来说，现在已知的最快的乘法时间复杂度可以接近O(nlog(n)), 通过离散傅立叶变换或数论变换可以达到。
这个是需要仔细琢磨的主要方向。
其实我过去也自己写过大数乘法，不过当初的目的是为了实现RSA算法，所以处理的整数对象不大。所以后来发现，通过数论变换得到的算法反而比直接相乘还要慢:) 所以说，即使实现了各种不同的方法以后，实际计算中可能还要根据计算数据的规模不同，挑选不同的算法，来达到提高效率。
此外，还有可以优化的就是使用汇编语言。比如郭老大说他自己用过SSE等指令，这些可以提高指令级的并发度。还有数据量很大时，还可以通过使用多线程来计算（多核情况）。 我最近用pascal写了个，很烂
除了乘法用四位，其他都没优化
使用汇编优化速度，通常还可以加入SSE2等指令更优化，这需要侦测CPU类型，同时多线程也可以提高计算速度 大数算法非常考验人，要求软硬通吃，还要求会根据情况自己推导数学公式，优化算法。
对硬件必须大致了解，具体到用什么指令集，每条指令周期数、延时数等，哪些指令组合可以并行执行，哪些不能？如何充分利用 CPU 的 cache？多核内部如何处理？
软件方面，采用什么数据结构？内存如何分配管理？接口如何组织？如何复用扩展？
当然，对于一般的应用也不必了解那么清楚，但这是开发顶尖级大数算法必备的素质，毕竟计算机是该过程的载体。
只有比较清楚计算机是如何运作的，才能准确评估当前算法的优劣，才能进一步提出改进方案，这就要求有一定的数学功底了。
对于一般的加解密算法，受实时性的要求，计算的规模一般不会太大，对算法本身的要求不多，更多在于代码的质量。 关于编译器的优化，可参考 mathe 发的：http://bbs.emath.ac.cn/thread-173-1-1.html
我在该帖 4# 给出了一些相关文档。 小数字直接乘
稍微大的 用Karatsuba算法
3-Toom算法也可以
再大的使用FFT
再大的是FNT
超大的还是用FFT
核心的短函数一律用SSE2汇编实现
包括FFT
尽量避免使用浮点指令
因为SSE2浮点比FPU浮点快很多很多 还要自己实现内存的管理
否则容易影响算法的效率 如果感觉对算法不很熟悉
建议下载GMP代码看
在gmplib.org有
页:
[1]
2