VBGood网站全文搜索 Google

搜索VBGood全站网页(全文搜索)

VB爱好者乐园(VBGood)

 找回密码
 立即注册
搜索
楼主: 八戒2

第70期源码[acme_pjz VS X0oo]

  [复制链接]
发表于 2011-4-18 19:43:07 | 显示全部楼层
本帖最后由 XOoo 于 2011-4-18 20:15 编辑

回复 Igawk 的帖子

刚再仔细想来一下,发觉很有问题哈,真对不起啊大家!

证明过程(有些步骤不知道怎么描述哈...将就一下...)

原函数改为等价的形式: f(X) = IIf(X And 1, (X * 3 + 1) / 2, X / 2)
定义一种描述方式:Fn(X),代表连续进行n次函数运算。如F3(X)=F(F(F(X)))

设H和L分别是X的高m位和低n位: X = H + L
定义函数:
F(H, L) = IIf(L And 1, H * 3 / 2 + (L * 3 + 1) / 2, H / 2 + L / 2)
[  即F(H, L)=f(H + L)  ]

再在F()的基础上定义函数FH()、FL():
F(H, L)=FH(H, L)+FL(L, L),其中
FH(H, RND) = IIf(RND And 1, H * 3 / 2, H / 2)
FL(L, RND) = IIf(RND And 1, (L * 3 + 1) / 2, L / 2)

对于任意一个正整数K显然有:
FH(K,RND)<=FL(K,RND)
进一步可以推出,对于任意随机数列RNDi,有(这一步不会用数学的语言说明,可能是有问题的):
FHn(K, RNDi) <= FLn(K, RNDi)  ,i=1...n

且当数列RNDi满足
FLn(K, RNDi) <= K   ,i=1...n
有FHn(K, RNDi)  <= K
当满足上式时(注意FH是只由乘法构成的函数,FHn(K, RNDi)等价于K乘以一个未知数#),对于任意的其它正整数A都有
FHn(A, RNDi) <= A  ,i=1...n

对于原命题,当
fn(X) < X = H + L
有等价的形式:
fn(X) = Fn(H, L) = FHn(H, L) + FLn(L, L) < H + L
而当
FLn(L, L)< L 时,
必然满足
FHn(H, L)< H
所以
FLn(L, L) + FHn(H, L) < H + L

点评

怎么又自动粗体了,我说的是c[ b ],d[ b ]的递推公式……  发表于 2011-4-18 22:41
要严格的话,对n用数学归纳法,这样顺便得出c和d的递推公式,我那个程序就用了这个公式……  发表于 2011-4-18 22:40
那个数学高手帮助看一下  发表于 2011-4-18 22:33
回复

使用道具 举报

发表于 2011-4-18 21:26:19 | 显示全部楼层
来看看这个……
回复

使用道具 举报

发表于 2011-4-18 22:37:37 | 显示全部楼层
[ 本帖最后由 acme_pjz 于 2011-4-18 22:39 编辑 ]

维基百科上面不是有么:http://en.wikipedia.org/wiki/Collatz_conjecture#Optimizations

Optimizations

====================================================================

The As a parity sequence section above gives a way to speed up simulation of the sequence. To jump ahead k steps on each iteration (using the f function from that section), break up the current number into two parts, b (the k least significant bits, interpreted as an integer), and a (the rest of the bits as an integer). The result of jumping ahead k steps can be found as:

f^k(a 2^k+b) = a 3^c[b]+d[b].
The c and d arrays are precalculated for all possible k-bit numbers b, where d [b]is the result of applying the f function k times to b, and c [b]is the number of odd numbers encountered on the way. For example, if k=5, you can jump ahead 5 steps on each iteration by separating out the 5 least significant bits of a number and using:

c [0...31] = {0,3,2,2,2,2,2,4,1,4,1,3,2,2,3,4,1,2,3,3,1,1,3,3,2,3,2,4,3,3,4,5}
d [0...31] = {0,2,1,1,2,2,2,20,1,26,1,10,4,4,13,40,2,5,17,17,2,2,20,20,8,22,8,71,26,26,80,242}.
This requires 2^k precomputation and storage to speed up the resulting calculation by a factor of k (see space-time tradeoff)

For the special purpose of searching for a counterexample to the Collatz conjecture, this precomputation leads to an even more important acceleration which is due to Tomás Oliveira e Silva and is used in the record confirmation of the Collatz conjecture. If, for some given b and k, the inequality

f^k(a 2^k+b) = a 3^c[b]+d[b] < a 2^k+b
holds for all a, then the first counterexample, if it exists, cannot be b modulo 2^k. For instance, the first counterexample must be odd because f(2n) = n; and it must be 3 mod 4 because f^3(4n+1) = 3n+1. For each starting value a which is not a counterexample to the Collatz conjecture, there is a k for which such an inequality holds, so checking the Collatz conjecture for one starting value is as good as checking an entire congruence class. As k increases, the search only needs to check those residues b that are not eliminated by lower values of k. On the order of 3^(k/2) residues survive. For example, the only surviving residues mod 32 are 7, 15, 27, and 31; only 573,162 residues survive mod 225 = 33,554,432.

其中f(k)=k/2如果k是偶数,(3k+1)/2如果k是奇数,f^n表示f迭代n次……
回复

使用道具 举报

头像被屏蔽
发表于 2011-4-19 10:05:18 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

发表于 2011-4-19 15:23:11 | 显示全部楼层
学习一下源码。
回复

使用道具 举报

发表于 2011-4-20 15:47:36 | 显示全部楼层
本帖最后由 XOoo 于 2011-4-20 15:48 编辑

总算又闲下来了,刚看过acme_pjz的代码,好些处理方法我没想到,学习了~ :clap:
我也投了acme_pjz一票
回复

使用道具 举报

发表于 2011-4-20 17:05:51 | 显示全部楼层
acme_pjz 也算是老法师了。XOo。 比较认真,投他一票

回复

使用道具 举报

发表于 2011-4-20 23:35:57 | 显示全部楼层
下来研究研究
回复

使用道具 举报

发表于 2011-4-23 16:44:17 | 显示全部楼层
恩。看看。学习下
回复

使用道具 举报

发表于 2011-4-25 18:53:55 | 显示全部楼层
学习学习,看看先
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

文字版|手机版|小黑屋|VBGood  

GMT+8, 2022-7-1 04:28

VB爱好者乐园(VBGood)
快速回复 返回顶部 返回列表