数字乘积

gxqcn

再回头阅读无心人自己在107#的优化， 发现我的算法优化原理与之类似。 但我的 filter() 函数虽然代码多些，但应该更高效一点。

gxqcn

原帖由 无心人 于 2009-3-3 21:35 发表 确实很快 GMP的二进制内核的输出太慢了 导致过滤函数成为瓶颈

这就是 HugeCalc 双进制内核的优势所在。 另外，我的代码中不含任何浮点指令，无论什么平台，效率更有保障。

无心人

我这里发现似乎96#并不比107#差很多 可能要考虑用unsigned int数组实现了 你的HugeCalc还是效率稍微差点 呵呵 用数组，就是有个如何更高效的取得10^9位上的数字的问题 乘以2很好做，乘以3大不了减两次 乘以7的难道要减六次？？？？

无心人

我这里128似乎输出了1082组呃 用的96#代码，因为这个代码的输出顺序性好

无心人

这里是我的结果 p128.txt (10.58 KB, 下载次数: 3)

2009-3-3 21:47 上传

点击文件名下载附件

gxqcn

我把我的运行结果附在了 108# 。 我搜索到的比你多 1105-1082=23 组， 可能与边界判定有关。比如我的前33组数据如下：

1. 00:00:00.000 No.1 exp( 2, 3, 7 ) = ( 0, 0, 0 )
2. 00:00:00.000 No.2 exp( 2, 3, 7 ) = ( 1, 0, 0 )
3. 00:00:00.000 No.3 exp( 2, 3, 7 ) = ( 2, 0, 0 )
4. 00:00:00.000 No.4 exp( 2, 3, 7 ) = ( 3, 0, 0 )
5. 00:00:00.000 No.5 exp( 2, 3, 7 ) = ( 4, 0, 0 )
6. 00:00:00.000 No.6 exp( 2, 3, 7 ) = ( 5, 0, 0 )
7. 00:00:00.000 No.7 exp( 2, 3, 7 ) = ( 6, 0, 0 )
8. 00:00:00.000 No.8 exp( 2, 3, 7 ) = ( 7, 0, 0 )
9. 00:00:00.000 No.9 exp( 2, 3, 7 ) = ( 13, 0, 0 )
10. 00:00:00.000 No.10 exp( 2, 3, 7 ) = ( 14, 0, 0 )
11. 00:00:00.000 No.11 exp( 2, 3, 7 ) = ( 15, 0, 0 )
12. 00:00:00.000 No.12 exp( 2, 3, 7 ) = ( 18, 0, 0 )
13. 00:00:00.000 No.13 exp( 2, 3, 7 ) = ( 24, 0, 0 )
14. 00:00:00.000 No.14 exp( 2, 3, 7 ) = ( 27, 0, 0 )
15. 00:00:00.000 No.15 exp( 2, 3, 7 ) = ( 31, 0, 0 )
16. 00:00:00.000 No.16 exp( 2, 3, 7 ) = ( 32, 0, 0 )
17. 00:00:00.000 No.17 exp( 2, 3, 7 ) = ( 34, 0, 0 )
18. 00:00:00.000 No.18 exp( 2, 3, 7 ) = ( 36, 0, 0 )
19. 00:00:00.000 No.19 exp( 2, 3, 7 ) = ( 0, 1, 0 )
20. 00:00:00.000 No.20 exp( 2, 3, 7 ) = ( 1, 1, 0 )
21. 00:00:00.000 No.21 exp( 2, 3, 7 ) = ( 2, 1, 0 )
22. 00:00:00.000 No.22 exp( 2, 3, 7 ) = ( 3, 1, 0 )
23. 00:00:00.000 No.23 exp( 2, 3, 7 ) = ( 4, 1, 0 )
24. 00:00:00.000 No.24 exp( 2, 3, 7 ) = ( 5, 1, 0 )
25. 00:00:00.000 No.25 exp( 2, 3, 7 ) = ( 6, 1, 0 )
26. 00:00:00.000 No.26 exp( 2, 3, 7 ) = ( 7, 1, 0 )
27. 00:00:00.000 No.27 exp( 2, 3, 7 ) = ( 8, 1, 0 )
28. 00:00:00.000 No.28 exp( 2, 3, 7 ) = ( 11, 1, 0 )
29. 00:00:00.000 No.29 exp( 2, 3, 7 ) = ( 12, 1, 0 )
30. 00:00:00.000 No.30 exp( 2, 3, 7 ) = ( 17, 1, 0 )
31. 00:00:00.000 No.31 exp( 2, 3, 7 ) = ( 18, 1, 0 )
32. 00:00:00.000 No.32 exp( 2, 3, 7 ) = ( 39, 1, 0 )
33. 00:00:00.000 No.33 exp( 2, 3, 7 ) = ( 73, 1, 0 )

复制代码

无心人

恩， 明天再比较吧 估计得到12阶结果的希望不大 GxQ你算其中的几个就知道了 基本2步内归零 呵呵

无心人

512十进制位以下得到的结果和128位以下一致 可以断定，找到12阶的希望不大了

mathe

一个任意的n位数，其中所有位都不出现0和5的概率可以认为是$(4/5)^n$ 所以一个数字连续变换k次，每次变换后各位上都不出现0,5的概率大概为$(4/5)^{n_1+n_2+...+n_k}$ 其中$n_i$为第i次变换之前的位数。我们就算这些位数平均来说为$n/2$ 那么连续变换k次都不出现0和5的概率大概再$(4/5)^{{nk}/2}$ 现在如果选择k=10,那么出现0,5后在两次变换就可能停止了，所以一个n位数12阶以上的概率大概为 $(4/5)^{5n}~=exp(-n)$ 同样，我们可以估计出不超过n位的因子只有2,3,7的数字数目大概为$1/{3!}{n^3}/{log(2)log(3)log(7)}~=1.37n^3$ 所以我们可以估计出12阶以上的数字出现数目的期望大概在 $int_{n0}^{infty}exp(-n)d1.37n^3=4.11int_{n0}^{infty}x^2exp(-x)dx=(2+2n0+n0^2)exp(-n0)$ 而对于这个积分，只要n0稍微大一些，显然是个非常非常小的数。 比如 n0=10时大概为0.0055 n0=20时大概为$9.1*10^{-7}$ n0=100时大概为$3.8*10^{-40}$ 所以现在继续向上找能找到一个满足条件的数的概率几乎可以忽略不计,小于$3.8*10^{-40}$。

无心人

我想用我得到的结果分析 结果haskell玩不转了 呵呵