自己想写个大数库,怎么写效率高？

troy · 发表于 2008-2-6 21:54:24

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

请论坛的出出主意~~~~~~~~~

kofeffect · 发表于 2008-2-6 22:14:31

呵呵，期待mathe和gxqcn的注意力，转啊转到这里来

mathe · 发表于 2008-2-7 09:02:20

从算法复杂度上来看，加法没什么可以优化的，主要在于乘法，而其他算法基本可以由乘法得出。
对于两个长度为n位的整数来说，现在已知的最快的乘法时间复杂度可以接近O(nlog(n)), 通过离散傅立叶变换或数论变换可以达到。
这个是需要仔细琢磨的主要方向。
其实我过去也自己写过大数乘法，不过当初的目的是为了实现RSA算法，所以处理的整数对象不大。所以后来发现，通过数论变换得到的算法反而比直接相乘还要慢

所以说，即使实现了各种不同的方法以后，实际计算中可能还要根据计算数据的规模不同，挑选不同的算法，来达到提高效率。
此外，还有可以优化的就是使用汇编语言。比如郭老大说他自己用过SSE等指令，这些可以提高指令级的并发度。还有数据量很大时，还可以通过使用多线程来计算（多核情况）。

cauchy · 发表于 2008-2-8 21:21:17

我最近用pascal写了个，很烂
除了乘法用四位，其他都没优化

high.rar (1.69 KB, 下载次数: 4)

kenmark · 发表于 2008-2-9 22:01:31

使用汇编优化速度，通常还可以加入SSE2等指令更优化，这需要侦测CPU类型，同时多线程也可以提高计算速度

gxqcn · 发表于 2008-2-11 10:57:11

大数算法非常考验人，要求软硬通吃，还要求会根据情况自己推导数学公式，优化算法。

对硬件必须大致了解，具体到用什么指令集，每条指令周期数、延时数等，哪些指令组合可以并行执行，哪些不能？如何充分利用 CPU 的 cache？多核内部如何处理？

软件方面，采用什么数据结构？内存如何分配管理？接口如何组织？如何复用扩展？

当然，对于一般的应用也不必了解那么清楚，但这是开发顶尖级大数算法必备的素质，毕竟计算机是该过程的载体。

只有比较清楚计算机是如何运作的，才能准确评估当前算法的优劣，才能进一步提出改进方案，这就要求有一定的数学功底了。

对于一般的加解密算法，受实时性的要求，计算的规模一般不会太大，对算法本身的要求不多，更多在于代码的质量。

gxqcn · 发表于 2008-2-11 16:49:33

关于编译器的优化，可参考 mathe 发的：http://bbs.emath.ac.cn/thread-173-1-1.html

我在该帖 4# 给出了一些相关文档。

无心人 · 发表于 2008-2-20 20:22:59

小数字直接乘
稍微大的用Karatsuba算法
3-Toom算法也可以
再大的使用FFT
再大的是FNT
超大的还是用FFT

核心的短函数一律用SSE2汇编实现
包括FFT
尽量避免使用浮点指令
因为SSE2浮点比FPU浮点快很多很多

无心人 · 发表于 2008-2-20 20:23:36

还要自己实现内存的管理

否则容易影响算法的效率

无心人 · 发表于 2008-2-20 20:25:46

如果感觉对算法不很熟悉
建议下载GMP代码看
在gmplib.org有

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 自己想写个大数库,怎么写效率高？

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。