| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 31795 人关注过本帖
标题:各位老师好!求助编辑一个大整数的快速乘除法可调用程序
只看楼主 加入收藏
xianfajushi
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:8
帖 子:527
专家分:690
注 册:2007-9-8
收藏
得分:0 
梅森51个82589933求余=0?!运算后的位数经过计算是有24862048位,数组用量1381225,最前面一个数组存有16位数,1381224*18+16=24862048。能告诉我哪里错了?
图片附件: 游客没有浏览图片的权限,请 登录注册

将全面验证51个梅森素数

[此贴子已经被作者于2022-3-17 08:39编辑过]

2022-03-16 11:33
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
回复 381楼 xianfajushi
谢谢您!很好!我也不知道哪里错了,如果是用的卢卡斯莱墨法判定,应该是第p-1项余数为0,您的好像是前面有两项余数为0了,咋回事呢?
我是要求算一下2^99368963-1除以198737927余数是否为0?这个仅仅一步除法,比卢卡斯莱墨法计算量小的多。

谢谢您!您的方法效率高啊!如果结果可靠,且余数不为0,就基本可以断定2^99368963-1是素数,那你发表出来就可能会得到10万美元奖励!
那就是了不起的成果,意义重大!

期待您的结果!非常期待,祝愿您早日取得成果!
2022-03-17 09:42
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
回复 381楼 xianfajushi
用卢卡斯莱墨法来判断2^82589933-1前7项的余数应该是:
4(1)
14(2)
194(3)
37634(4)
1416317954(5)
2005956546822746114(6)
4023861667741036022825635656102100994(7)
不会有余数为0的情况的,直到被除数大于等于除数2^82589933-1为止都不会余数为0的。

注意:每一项都是前一项的余数的平方,减去2,再除以2^82589933-1的与余数,比如2005956546822746114^2=4023861667741036022825635656102100996,再减去2得到4023861667741036022825635656102100994,余数仍然是4023861667741036022825635656102100994.

[此贴子已经被作者于2022-3-17 10:11编辑过]

2022-03-17 10:06
xianfajushi
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:8
帖 子:527
专家分:690
注 册:2007-9-8
收藏
得分:0 
开我玩笑?不是有秒算的了?我只是发出疑问51个梅森是否被我证实是错的了,希望看到有兴趣的人一起来验证而已.甚至希望那个秒算的能出来证明我的算法是错的,包括次方运算的数据是错的,求余运算是错的,以便我发现我的算法错在哪里,据前面发出了的474次方数据核对次方算法应该是正确的,多或少1次方那么82589933数据就不会是有24862048位的对?因此可以推导证明次方演算是正确的,那么,就剩下求余运算值得怀疑.
如果你的要求算一下2^99368963-1除以198737927余数是否为0的被运算不为0是否真的就能确定?假若被其他质数求余为0了?就算我算出来了的结果,你也未必就能确定,甚至可能说我的算法有问题不可信等等.
梅森素数的前几个确实能确定,而数值一旦大了就只能靠程序去验证了,而程序的正确性显然是最重要的.
不过要验证我的求余算法是否正确也不难:77774777888888888888888888888888889999999999用198737927求余96610127,当然还可以多弄些数据来验证求余算法.

[此贴子已经被作者于2022-3-17 10:24编辑过]

2022-03-17 10:10
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
回复 384楼 xianfajushi
若程序靠谱,如果您算的2^99368963-1除以198737927余数不为0(仅仅用于这一个类型)就基本可以确定了,不能再用其他质数求余是否为0了,可以用卢卡斯莱墨法最后确定。

[此贴子已经被作者于2022-3-17 10:39编辑过]

2022-03-17 10:31
xianfajushi
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:8
帖 子:527
专家分:690
注 册:2007-9-8
收藏
得分:0 
如果不能再用其他质数求余是否为0了那就没任何意义了,因为这就直接说明我的数据和算法不正确,那么似乎可以看到有人在偷偷看我的笑话了.一个程序的正确性是不容置疑的,否则的话就算是算出来数值都是废话.

[此贴子已经被作者于2022-3-17 10:53编辑过]

2022-03-17 10:41
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
回复 386楼 xianfajushi
不是,这是一种对付特殊类型素数的素性判断的简便方法,与你的程序是否正确没有关系,如果你的程序判断余数不为0而用其他程序判断余数为0,那才能证明这两个程序有一个不对,跟是否用其他素数判断是否为0没有关系,不是一回事。

没人笑话你,您的程序速度够快,效率很高,非常欣赏!可惜不懂vc语言,没法学习!谢谢您,非常感谢!让我看到了希望,我们都继续努力!
2022-03-17 10:59
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
回复 387楼 ysr2857
用python吧,速度快,计算(2^99368963-1)mod 198737927的结果不超过1秒钟,结果是2^99368963-1可以整除198737927。第51个梅森素数mod 7的余数是3,验证了的素数,除任何数都会有余数,不可能为0。
另:楼主如果确实想自己写个大数快速乘法的话,建议使用表运算,用空间换时间,位数越多,效率越高,比如十进制数,常规算法时间复杂度是O(n^2),如果使用表,复杂度就是O(8*n)=O(n),空间复杂度也为O(8*n)=O(n)。为什么是8,是因为做乘法时0和1可以不需要做,也不需要空间存储,直接移位加0或加被乘数就可以了。
图片附件: 游客没有浏览图片的权限,请 登录注册

能编个毛线衣吗?
2022-03-17 16:16
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
回复 388楼 wmf2014
谢谢您关注和回复!计算(2^99368963-1)mod 198737927的结果不超过1秒钟,那这个程序速度快效率高!结果是2^99368963-1可以整除198737927,那就是说2^99368963-1是个合数,不是素数了。
结果很好,是个重要成果,可惜无法给你加分了,怎么能给你加分呢?

非常感谢!
2022-03-17 16:54
xianfajushi
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:8
帖 子:527
专家分:690
注 册:2007-9-8
收藏
得分:0 
200万都用不到,说过了月内确定,连续的运行。
图片附件: 游客没有浏览图片的权限,请 登录注册
2022-03-25 06:40
快速回复:各位老师好!求助编辑一个大整数的快速乘除法可调用程序
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.026202 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved