关于新项目的想法

gameboybf2142

今天遇到一个同学，他在考虑用分布式计算来找beal‘s conjecture的反例。关于beal’s conjecture， 参见http://en.wikipedia.org/wiki/Beal's_conjecture
不知道我们能不能就这个猜想做一个boinc项目，看起来并不复杂，而且貌似wiki说如果ABC猜想是正确的话，这个猜想应该有有限个反例，所以.....
@fwjmath @arthur200000

不知道大家认为怎么样?

fwjmath

据说Beal Conjecture反例不好找……有人甚至说大家都知道这个是真的，所以就不要验证直接考虑怎么证明就好了，参见 http://mersenneforum.org/showthread.php?t=11756 这个帖子的六楼。

顺便说一下，因为他们提到Tate所以这个应该是代数数论的范畴。而据我一位做代数数论的朋友说，有个叫standard conjecture的东西，大家都知道是对的，但是不知道怎么证。一旦这个证出来，很多很强的东西都能证出来，我觉得Beal conjecture大概也在这个可以证出来的范畴（不过不是很确定）。从另一个方面看，Beal Conjecture显然是费马大定理的推广，所以可能证明要用模形式甚至是自守形式之类的东西，而这类东西一般能猜想出来（没有小反例）的都是对的，但是不知道怎么证明而已……

不过要做的话也可以，感觉稍弱一点而已。我之前也考虑过一下，没有想到特别好的算法或者GPU实现方法，所以就搁置一边了。如果能有很好的算法的话还是可以考虑一下做的~~~

fwjmath

可以先看看这个吧：
http://norvig.com/beal.html

当然这个算法很直白，应该很有优化的余地，但是要做成分布式的话还要考虑一下怎么优化才能很好地分割任务。我当时考虑的时候就是觉得我自己想的算法如果分割的话反而会变慢……

fwjmath

顺便一说，有人更加喜欢把它称为Tijdeman-Zagier conjecture，因为这两位都是真正的数学家，而据说Beal只是一个出钱悬赏的土豪……

gameboybf2142

@fwjmath
看了一下，那个算法感觉其实没什么特别好的优化方法，能做到的优化也只有直接跳过少数能够判断的不可能的数，但这样的数应该不多吧。
感觉这种找反例的项目很多都是暴力搜索（比如CC），除非能找到好的代数、数论优化法。

fwjmath

那个方法有一点不太好的就是要查一个比较大的表……不过这个问题也不算特别大，除非我们找到特别好的优化方法……

我的想法是，因为我们要验证的r的值是有范围的（实际上只需要验证r是素数的情况），所以对于不同的r值我们可以选取适当的模，快速筛选合适的x,y,m,n值。这个至少是一个常数的加速，选取多个模的话加速更大。然后就是可以用对数算出开头几位来比较，不过这个跟hash值其实差不多，可能更有针对性一些。可能选取一个随机的素数来计算带模高次方（用费马小定理），也可以有一个可观的加速，不过这方面不是特别确定。

肯定还有别的优化，我这些都是凭过去经验猜的，实际写出来的话，profile一下可能会有更多收获。

fwjmath

先不说做分布式项目，有人有兴趣写这个么？有兴趣的话，我可以在Google Code上开一个项目什么的，先做一下，然后看能不能变成分布式，虽然我觉得意义不是特别大，但是练一下手还是可以的。

或者可以搞成一个计算密集程序优化的教程，以这个猜想的程序作例子，展示一些常用的优化方面的做法和想法。

gameboybf2142

fwjmath 发表于 2014-4-1 08:54
先不说做分布式项目，有人有兴趣写这个么？有兴趣的话，我可以在Google Code上开一个项目什么的，先做一下 ...

这个是指？

fwjmath

gameboybf2142 发表于 2014-4-2 07:34
这个是指？

就是Beal猜想的验证程序……不过最近也不是特别有空，不知道能做到哪一步……

gameboybf2142

fwjmath 发表于 2014-4-1 22:42
就是Beal猜想的验证程序……不过最近也不是特别有空，不知道能做到哪一步……
...

可以啊，我半期考试考完以后应该有时间写吧

fwjmath

写了一个：
https://github.com/fwjmath/beal-optimize

其实wiki才是重点，问题是现在除了一个很小很小的优化（~10%）以外，没有特别好的想法……