难道是Bug？（我感觉很大程度上是）

mathematica · 发表于 2010-7-25 12:12:54

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

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

×

问题很简单，求比10^2000大的最小的素数.
用mathematica7.0写的代码如下
Timing[NextPrime[10^2000]]
我用mathematica计算出来了结果,结果准备贴在回复中

mathematica · 发表于 2010-7-25 12:13:31

mathematica的求解结果是
{300.859, \
1000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000004561}

mathematica · 发表于 2010-7-25 12:17:34

我用hugecalc8.0.0.0,也就是最新版本,算了1000秒,都没有算出结果,不知道为什么,不过我想郭老大肯定知道为什么,请郭老大一定要给出个详细的回复(越详细越好),我的直觉告诉我是郭的算法出问题了!

mathematica用300秒能算出来的结果,我不相信hugecalc8.0.0.0用1000秒都算不出来.我把这个问题反馈一下.奇怪的是我用pari/gp算了近半个小时,居然也没有算出结果,我想肯定这两个软件都出问题了!(指的是hugecalc8.0.0.0和pari/gp2.3.4)

mathematica · 发表于 2010-7-25 12:19:01

我的直觉告诉我是郭的素性判定的lucas算法出现问题了,还请郭出来一下吧

mathematica · 发表于 2010-7-25 12:53:55

从10^2000+3000到10^2000+4561,hugecalc用了312秒,那么从10^2000到10^2000+3000差不多应该用600秒,两者的时间加起来应该不会超过1000秒,由此可以推测出问题的应该是在10^2000到10^2000+3000之间

mathematica · 发表于 2010-7-25 13:24:43

我晕，我重新计算了一下，hugecalc用了937.85秒，但是上次我计算1000秒为什么没有出来呢？
为什么Mathematica计算300秒就出来了，而hugecalc却需要900多秒呢？

mathe · 发表于 2010-7-25 16:09:34

我估计Mathematics先将那些含有较小素因子的候选数事先通过筛法去除了。而Pari/Gp和HugeCalc可能老老实实的每个数用相同算法去判断是否是素数（这个对x小的时候没有关系，但是如果x很大，那么x到NextPrime距离相对比较大，那么事先筛选很重要）。

qianyb · 发表于 2010-7-26 07:36:03

小素数因子,郭肯定是有先筛除了,可能是筛的个数不同吧

gxqcn · 发表于 2010-7-26 07:56:33

以前我也发现了Mathematics在判定超大素数时快于HugeCalc，
我自己分析，应该只是模幂算法效率的问题，
当前我的模幂算法与大数算法结合并不紧密。
我老早有一个构想，针对超大模时，有一个快速模幂算法，
其提速的效果将随模的增大而显著。
只是近期非常忙，一直无暇顾及。

gxqcn · 发表于 2010-7-26 07:58:11

在回复间，我用HugeCalc测试了下，寻找比10^2000大的最小素数，用时450.345736s，结果为10^2000+4561，不存在bug.

测试环境：WinXP SP3，AMD Athlon(tm) 64 Processor 3200+ 2.01GHz, 960 MB RAM
期间同时还打开数个网页。

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

[BUG] 难道是Bug？（我感觉很大程度上是）

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