对于超过long long int的数字，是怎么表示的？

cuihao · 发表于 2009-8-30 17:14:03

实在不明白，超过long long int（2^64）的数字，编程中是怎么表示和计算的。像PG计算非常大的质数，用的什么算法？数字又是怎样表示的？希望懂编程的人可以讲一下。

cuihao · 发表于 2009-8-30 17:31:57

我说的是超过2^64的数字！不是2^64以内的数字。

BiscuiT · 发表于 2009-8-30 18:51:27

http://mattmccutchen.net/bigint/

cuihao · 发表于 2009-8-30 18:58:40

有原理说明吗。

还要编译、连接库，好麻烦的说

。

Julian_Yuen · 发表于 2009-8-30 19:30:02

我个人观点是，如果没有这种类型，那么自己可以定义一个。
毕竟类型也是定义出来的。
不知道这么说你会不会开拓一下思路

cuihao · 发表于 2009-8-30 19:34:12

是的，如同高精度计算。

但是这样的话，除法、乘方种种运算就比较难实现了，并且效率很低。

我想那些大规模运算软件不会是使用这种方法吧。

Julian_Yuen · 发表于 2009-8-30 21:01:37

只有硬件支持的效率才会相对高。诸如减法变加法，除法变乘法之类的，对于效率的方面，需要你去考虑的有很多。

算法方面的优化是门大学问。如果你想更加深入，你需要了解更多。

给你个例子，http://www.changhai.org/contents ... _hypothesis_a1.html

cuihao · 发表于 2009-8-30 21:08:01

唉，算法。。。学海无涯啊。

20080030成电 · 发表于 2009-8-30 22:37:25

我以前去面试的时候碰过类似的问题你可以用数组来保存

lfk · 发表于 2009-8-31 01:15:57

ls+1...
以前OI学过...高精度加减乘除...全用数组实现的.......

yuan234yuan · 发表于 2009-8-31 10:00:52

固定精度扩展可以用定长数组。任意精度则可用malloc。
机器层硬件优化对单个字采用的算法在汇编层模拟一遍即可适用于短精度运算。
高精度运算则主要考虑乘法优化。效率是可以放心的，这方面的算法已经很成熟了。
中等规模精度的乘法主要是二路分治和三路分治，效率分别为O(n^1.79)和O(n^1.63)。
PG等大素数乘除多数是用FFT（Fast Fourier Transform）加速，效率为O(nlognloglogn...)。再大的数用快速数论变换，不过这样的数已经超出了现有硬件可以表示的范围。
PG用的肯定就是GMP（GNU Multi-Precition）的库。GMP是一个有关整数高精运算实现的高效函数库。
算法的具体细节可参考Knuth的The Art of Computer Programming。具体的实现上GMP网站可以看到成熟的代码。

cuihao · 发表于 2009-8-31 22:06:19

晕。。。还是要用高精度。

我目前会高精度加减乘，除法不太会。

问一下，CPU是怎样进行除法和模(mod)运算的？

Julian_Yuen · 发表于 2009-9-1 06:31:51

来学习。
前阵子折腾了一个乘除法运算，要求前前后后加起来，最多一次完整运算不超过10us，然后我快被折磨死了，还好leader很威能.....

yuan234yuan · 发表于 2009-9-1 09:27:34

高精度和长整数是一回事吧...
参见一般的计算机组成原理书籍。针对位运算的特点极大优化的算法。
你想优化你的Palcalc？加油~~~

cuihao · 发表于 2009-9-1 19:39:07

由于CPU计算精度原因，现在pascalc最大的问题就是精度了，尤其是复数范围的运算，一塌糊涂。

先学习一下吧。。。

		自动登录	找回密码
密码			新注册用户

对于超过long long int的数字，是怎么表示的？

回复 #2 zglloo 的帖子

回复 #3 BiscuiT 的帖子

回复 #5 Julian_Yuen 的帖子

回复 #6 cuihao 的帖子

回复 #1 cuihao 的帖子

评分

回复 #13 cuihao 的帖子

回复 #15 yuan234yuan 的帖子

浏览过的版块