教你用Ruby算命！

C# 的tail优化得自己修改il，明天再看。。。

Ruby 没有尾递归优化的，何况递归的位置在数列那里……

tail call 版本：

ll_seq' 0 m res = res
ll_seq' n m res = ll_seq' (n - 1) m ((res ^ 2 - 2) `mod` m)

ll_seq  n m = ll_seq' n m (4 `mod` m)

没有 +RTS -K来制定栈空间的话，hasksell也崩溃了.

很奇怪它的CPU利用率很低，才50%，没办法全力进行计算...如果算法完全一样的话，hasksell应该会比较慢。。。


hasksell好像还没算完第一个数。。。。大数的时候，都是龟速。

你上面给ruby那个版本做的优化叫什么？
这个方法很好，直接减少了堆栈的长度，否则原始版本还会一个函数一个函数的往里面扔。

编译使用 -O2 和 -threaded 参数(-O3 似乎更牛？)

ghc -O2 -threaded --make messen.hs

双核的使用2个本地线程运行可以吃到 100%：

messen +RTS -N2

我用的是  -O3 ,不过运算速度真的快不起来，这还是个中等长度的数。。

唔，由于延迟求值特性，虽然尾递归了，但是还有一个巨大的 data thunk ..

需要用 $! 强制求值。

不会爆栈的双线程版本如附件。

我看不太懂haskell，你的尾递归写成java是如何的？

这个版本消耗多少内存？？

BigInteger 写着太麻烦，给伪码(和迭代很接近了)：

//tail call sequence
int tcs(int n, int m, int result) {
  if(n == 0){
    return result;
  }
  return tcs((n - 1), m, ((result ^ 2 - 2 ) % m));
}

//L-L sequence
int seq(int n, int m) {
  return tcs(n, m, 4 % m);
}

吃内存也不少，算M(20996011)的时候 280 多M，由于爱惜本本，没算出来就给我停了……

楼上的同学们，看下我修改好的Erlang版的计算Mersenne(LucasLehmer)第二版
跟第一版比较，重写了math:pow/2方法，这个方法可以支持很大的幂运算。


http://charlescui.iteye.com/admin/blogs/365159

-module(mersenne).  
-export([run/1,mersenne/1,lucasLehmer_sequence/2,pow/2]).  
  
-spec pow(integer(), non_neg_integer()) -> integer()  
      ; (float(), non_neg_integer()) -> float().  
  
pow(X, N) when is_integer(N), N >= 0 -> pow(X, N, 1).  
  
pow(_, 0, P) -> P;  
pow(X, N, A) -> pow(X, N-1, A*X).  
  
lucasLehmer_sequence (0, M) -> 4 rem M;  
lucasLehmer_sequence (N, M) when N>0 ->  
        erlang:round((pow(lucasLehmer_sequence(N-1,M),2)-2)) rem M.  
  
mersenne(N) when N>0 ->  
   erlang:round(pow(2,N))-1.  
  
lucasLehmer_test(N) ->  
   lucasLehmer_sequence(N - 2, mersenne(N)) =:=0.  
  
run(2) ->  
    case lucasLehmer_test(2) of  
        true ->  
                io:format("M(~w) => ~w~n", [2,mersenne(2)]);  
        false ->  
                false  
    end;  
run(N) ->  
    case lucasLehmer_test(N) of  
        true ->  
                io:format("M(~w) => ~w~n", [N,mersenne(N)]);  
        false ->  
                false  
    end,  
    run(N-1).  

计算梅森数可以算好多，只是效率还有待提高，因为算到M(2281)还是花了一点时间的，不知道Haskell和C#算到M(2281)花了多少时间，ps：这个Erlang版本还是单进程，只用到CPU的一个核。 有空再修改下，让Erlang并行运算的优势发挥下。