hrefspace

 找回密码
 立即注册
搜索
热搜: PHP PS 程序设计
查看: 533|回复: 9

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

[复制链接]

446

主题

446

帖子

1368

积分

大司空

Rank: 5Rank: 5

积分
1368
发表于 2024-2-12 09:26:38 | 显示全部楼层 |阅读模式
请论坛的出出主意~~~~~~~~~
回复

使用道具 举报

0

主题

169

帖子

29

积分

新手上路

Rank: 1

积分
29
发表于 2024-2-12 09:27:08 | 显示全部楼层
呵呵,期待mathe和gxqcn的注意力,转啊转到这里来

本帖子中包含更多资源

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

x
回复

使用道具 举报

0

主题

171

帖子

67

积分

关内侯

Rank: 2

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

本帖子中包含更多资源

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

x
回复

使用道具 举报

0

主题

192

帖子

66

积分

关内侯

Rank: 2

积分
66
发表于 2024-2-12 09:28:30 | 显示全部楼层
我最近用pascal写了个,很烂
除了乘法用四位,其他都没优化
high.rar(1.69 KB, 下载次数: 4)2008-2-8 21:21 上传
点击文件名下载附件
high.pp

本帖子中包含更多资源

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

x
回复

使用道具 举报

0

主题

196

帖子

2

积分

新手上路

Rank: 1

积分
2
发表于 2024-2-12 09:28:52 | 显示全部楼层
使用汇编优化速度,通常还可以加入SSE2等指令更优化,这需要侦测CPU类型,同时多线程也可以提高计算速度
回复

使用道具 举报

0

主题

169

帖子

2

积分

新手上路

Rank: 1

积分
2
发表于 2024-2-12 09:29:08 | 显示全部楼层
大数算法非常考验人,要求软硬通吃,还要求会根据情况自己推导数学公式,优化算法。

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

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

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

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

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

使用道具 举报

0

主题

184

帖子

170

积分

关内侯

Rank: 2

积分
170
发表于 2024-2-12 09:29:50 | 显示全部楼层
关于编译器的优化,可参考 mathe 发的:http://bbs.emath.ac.cn/thread-173-1-1.html

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

使用道具 举报

0

主题

201

帖子

2

积分

新手上路

Rank: 1

积分
2
发表于 2024-2-12 09:30:37 | 显示全部楼层
小数字直接乘
稍微大的 用Karatsuba算法
3-Toom算法也可以
再大的使用FFT
再大的是FNT
超大的还是用FFT

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

使用道具 举报

1

主题

175

帖子

5

积分

新手上路

Rank: 1

积分
5
发表于 2024-2-12 09:31:36 | 显示全部楼层
还要自己实现内存的管理

否则容易影响算法的效率
回复

使用道具 举报

0

主题

169

帖子

2

积分

新手上路

Rank: 1

积分
2
发表于 2024-2-12 09:31:50 | 显示全部楼层
如果感觉对算法不很熟悉
建议下载GMP代码看
在gmplib.org有
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|hrefspace

GMT+8, 2024-3-5 08:03 , Processed in 0.116822 second(s), 22 queries .

Powered by hrefspace X3.4 Licensed

Copyright © 2022, hrefspace.

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