数学研发论坛

 找回密码
 欢迎注册
查看: 3887|回复: 10

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

[复制链接]
发表于 2008-2-6 21:54:24 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
请论坛的出出主意~~~~~~~~~
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-6 22:14:31 | 显示全部楼层
呵呵,期待mathe和gxqcn的注意力,转啊转到这里来
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-7 09:02:20 | 显示全部楼层
从算法复杂度上来看,加法没什么可以优化的,主要在于乘法,而其他算法基本可以由乘法得出。
对于两个长度为n位的整数来说,现在已知的最快的乘法时间复杂度可以接近O(nlog(n)), 通过离散傅立叶变换或数论变换可以达到。
这个是需要仔细琢磨的主要方向。
其实我过去也自己写过大数乘法,不过当初的目的是为了实现RSA算法,所以处理的整数对象不大。所以后来发现,通过数论变换得到的算法反而比直接相乘还要慢 所以说,即使实现了各种不同的方法以后,实际计算中可能还要根据计算数据的规模不同,挑选不同的算法,来达到提高效率。
此外,还有可以优化的就是使用汇编语言。比如郭老大说他自己用过SSE等指令,这些可以提高指令级的并发度。还有数据量很大时,还可以通过使用多线程来计算(多核情况)。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-8 21:21:17 | 显示全部楼层
我最近用pascal写了个,很烂
除了乘法用四位,其他都没优化
high.rar (1.69 KB, 下载次数: 4)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-9 22:01:31 | 显示全部楼层
使用汇编优化速度,通常还可以加入SSE2等指令更优化,这需要侦测CPU类型,同时多线程也可以提高计算速度
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-11 10:57:11 | 显示全部楼层
大数算法非常考验人,要求软硬通吃,还要求会根据情况自己推导数学公式,优化算法。

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

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

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

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

对于一般的加解密算法,受实时性的要求,计算的规模一般不会太大,对算法本身的要求不多,更多在于代码的质量。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-11 16:49:33 | 显示全部楼层
关于编译器的优化,可参考 mathe 发的:/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有
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-9-15 18:28 , Processed in 0.062240 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表