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

123456789 · 发表于 2024-2-12 09:26:38

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

iniogateln · 发表于 2024-2-12 09:27:08

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

Jeninslots · 发表于 2024-2-12 09:28:02

从算法复杂度上来看，加法没什么可以优化的，主要在于乘法，而其他算法基本可以由乘法得出。
对于两个长度为n位的整数来说，现在已知的最快的乘法时间复杂度可以接近O(nlog(n)), 通过离散傅立叶变换或数论变换可以达到。
这个是需要仔细琢磨的主要方向。
其实我过去也自己写过大数乘法，不过当初的目的是为了实现RSA算法，所以处理的整数对象不大。所以后来发现，通过数论变换得到的算法反而比直接相乘还要慢所以说，即使实现了各种不同的方法以后，实际计算中可能还要根据计算数据的规模不同，挑选不同的算法，来达到提高效率。
此外，还有可以优化的就是使用汇编语言。比如郭老大说他自己用过SSE等指令，这些可以提高指令级的并发度。还有数据量很大时，还可以通过使用多线程来计算（多核情况）。

ukirhayexasi · 发表于 2024-2-12 09:28:30

我最近用pascal写了个，很烂
除了乘法用四位，其他都没优化
high.rar(1.69 KB, 下载次数: 4)2008-2-8 21:21 上传
点击文件名下载附件
high.pp

uzmedafacof · 发表于 2024-2-12 09:28:52

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

Sherryufas · 发表于 2024-2-12 09:29:08

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

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

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

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

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

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

uliaxoxujiq · 发表于 2024-2-12 09:29:50

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

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

icakeekohude · 发表于 2024-2-12 09:30:37

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

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

DJWilliamstada · 发表于 2024-2-12 09:31:36

还要自己实现内存的管理

否则容易影响算法的效率

igikzari · 发表于 2024-2-12 09:31:50

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

		自动登录	找回密码
密码			立即注册

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

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源