整数分解包括大数
这个擂台我写不出程序的...不过希望众位高手试试.我看了整个论坛,没有发现任何人发过大数分解的擂台... HugeCalc demo 的PrimeNumber程序对数字大小有限制...
不知有没有人想试试写出最快的整数分解程序?
我没有见过什么对比的程序,所以并不知道Mathematica里面的整数分解是否已经是领先水平...
我每天的乐趣就是看到一个数字...记录下来...回到家里...分解掉... 第二天到那里,贴个纸条,写个被分解的模式.:lol 你就知道数学软件包里的分解程序都不行就可以了
我在这论坛发了个专门帖子里面是大部分的大数分解程序
可以分解到100位整数 最新的分解程序可以分解到多少位整数了? 整数的大数分解是非常困难的好不好? 我倒是用C#写过MPQS用作大数分解,分解2个15位质数的乘积大概2-3s,可能比Mathematica优化过的方法要慢一些。再大的需要用大数,效率下降的比较多。
估计10^30左右的大数分解,用这种方法应该是最快的了。还有种连分数分解以及椭圆分解的方法,我没有试过。据说110位以内的数,MPQS比较有优势,再大就需要用数域筛法了。 反正现有方法都不能说谁好谁坏
一般经过试除去除小因子的数字,先过椭圆曲线,然后,过MPQS,再过NFS
偶尔也用其他一些随机算法 5# litaoye
能共享一下你的代码吗? 主要是我代码写的比较烂,不太好读,对于比较小的数可能还有些Bug。另外有几道ACM题都是靠这个算法坑人的,贴出来怕就成为水题了。但MPQS主要就涉及3个算法:
1、求平方剩余。
2、质数筛法。
3、高斯消元。
另外在选数的范围上有些细节需要注意,此外就没啥特别的了。写MPQS之前可以先从普通的二次筛法开始写,原理一样。也没有选数的问题,写起来还容易。复杂一点的平方剩余那部分也可以用枚举先凑合实现。如果你对于原理和实现上有啥问题,我知道的一定都不会保留。
5# litaoye
能共享一下你的代码吗?
mathematica 发表于 2013-3-18 14:55 http://bbs.emath.ac.cn/images/common/back.gif
页:
[1]