教你用Ruby算命！

不多解释，请直接看结果：

require 'benchmark'

def lucasLehmer_sequence n, m
  raise(ArgumentError, "lucasLehmer seq must larger than 0.") if n < 0
  (n == 0 ? 4 : (lucasLehmer_sequence(n - 1, m) ** 2 - 2)) % m # 注意这里
end

def lucasLehmer_test n
  m = mersenne n
  lucasLehmer_sequence(n - 2, m) == 0
end

def mersenne(n)
  n >= 1 ? (2 ** n - 1) : (raise ArgumentError,"Mersenne seq must larger than 0.")
end

stat = nil

(2..1000).each do |n|
  rt = Benchmark::realtime{stat = lucasLehmer_test(n)}
  p ("M(#{n}) => #{mersenne(n)} | realtime : #{rt}") if stat
end

"M(3) => 7 | realtime : 0.0"
"M(5) => 31 | realtime : 0.0"
"M(7) => 127 | realtime : 0.0"
"M(13) => 8191 | realtime : 0.0"
"M(17) => 131071 | realtime : 0.0"
"M(19) => 524287 | realtime : 0.0"
"M(31) => 2147483647 | realtime : 0.0"
"M(61) => 2305843009213693951 | realtime : 0.0"
"M(89) => 618970019642690137449562111 | realtime : 0.0"
"M(107) => 162259276829213363391578010288127 | realtime : 0.0"
"M(127) => 170141183460469231731687303715884105727 | realtime : 0.0"
"M(521) => 6864797660130609714981900799081393217269435300143305409394463459185543183397656
052122559640661454554977296311391480858037121987999716643812574028291115057151 | realtime
: 0.0320000648498535"
"M(607) => 5311379928167670986895882065524686273295931177270319231994441382004035598608522
427391625022652292856688893294862465010153465793376527072394095199787665873519438312708353
93219031728127 | realtime : 0.0150001049041748"

靠，彪悍啊！

代码经过你修改后，我瞬间由M(19)飙升至M(607),瞬间！

我计算到M(1279)之后，还是出了Bignum太长无法计算的问题：

"M(3) => 7 | realtime : 8.29696655273438e-05"
"M(5) => 31 | realtime : 7.79628753662109e-05"
"M(7) => 127 | realtime : 0.000104904174804688"
"M(13) => 8191 | realtime : 7.89165496826172e-05"
"M(17) => 131071 | realtime : 0.000146865844726562"
"M(19) => 524287 | realtime : 0.00018000602722168"
"M(31) => 2147483647 | realtime : 0.000385046005249023"
"M(61) => 2305843009213693951 | realtime : 0.000309944152832031"
"M(89) => 618970019642690137449562111 | realtime : 0.000612020492553711"
"M(107) => 162259276829213363391578010288127 | realtime : 0.000727176666259766"
"M(127) => 170141183460469231731687303715884105727 | realtime : 7.79628753662109e-05"
"M(521) => 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151 | realtime : 0.00815606117248535"
"M(607) => 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127 | realtime : 0.0123329162597656"
"M(1279) => 10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087 | realtime : 0.106499195098877"
./mersenne.rb:7:in `%': Bignum can't be coerced into Fixnum (TypeError)
        from ./mersenne.rb:7:in `lucasLehmer_sequence'
        from ./mersenne.rb:7:in `lucasLehmer_sequence'
        from ./mersenne.rb:12:in `lucasLehmer_test'
        from ./mersenne.rb:22
        from /usr/lib/ruby/1.8/benchmark.rb:308:in `realtime'
        from ./mersenne.rb:22
        from ./mersenne.rb:21:in `each'
        from ./mersenne.rb:21

Ruby 长整数的底层实现是一个链表（可以看做变长数组），当然越短越快。

#define RBIGNUM_EMBED_LEN_MAX ((sizeof(VALUE)*3)/sizeof(BDIGIT))
struct RBignum {
    struct RBasic basic;
    union {
        struct {
            long len;
            BDIGIT *digits;
        } heap;
        BDIGIT ary[RBIGNUM_EMBED_LEN_MAX];
    } as;
};

而 BDIGIT 是一个 unsigned int （视不同平台而定）

这个数组第一位保存长度，后面是一串无符号整数。

当 len 达到一定程度时，就会说 maybe too big 了。

2**(2**18);nil
# => ok
2**(2**18+1);nil
# => warning: in a**b, b may be too big

Haskell 做科学计算自然得强悍点， Haskel实现一些逻辑，编译成共享库，让 Ruby 调用也不错……

还是我上面那个卢卡斯莱莫的算法，写了个JS版的，用Chrome跑，

结果不知道为什么只能跑到M(19)就自动停了，

我把代码贴出来，哪个同学Copy->Paste之后也可以试试。

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
 <HEAD>
  <TITLE> Mersenne(LucasLehmer) </TITLE>
  <META NAME="Generator" CONTENT="EditPlus">
  <META NAME="Author" CONTENT="">
  <META NAME="Keywords" CONTENT="">
  <META NAME="Description" CONTENT="">
  <SCRIPT LANGUAGE="JavaScript">
  <!--
	/**
	 *寻找梅森数
	 *采用LucasLehmer算法
	 *zheng.cuizh@gmail.com
	 */
	function lucasLehmer_sequence(n, m){
	  if(n < 0){
		throw "lucasLehmer seq must larger than 0."
	  }
	  return (n == 0 ? 4 : (Math.pow(lucasLehmer_sequence(n - 1, m),2) - 2)) % m
	}

	function lucasLehmer_test(n){
	  m = mersenne(n)
	  return (lucasLehmer_sequence(n - 2, m) == 0)
	}

	function mersenne(n){
	  return (n >= 1 ? (Math.pow(2,n) - 1) : (alert("Mersenne seq must larger than 0.")))
	}

	function run(){
		var m=parseInt(document.getElementById("iteration").value)
		document.getElementById("Mersennes").innerHTML=""
		for(n=2;n<m;n++){
			stat = lucasLehmer_test(n)
			if(stat){
				document.getElementById("Mersennes").innerHTML+="M("+n+") => "+mersenne(n)+"<br/>"
			}		
		}
	}
  //-->
  </SCRIPT>
 </HEAD>

 <BODY>
  <INPUT TYPE="button" VALUE="Compute Mersennes" ONCLICK="run();"><p/>
  M(n)：请输入n->
  <INPUT TYPE="text" NAME="iteration" id="iteration"></INPUT><p/>
  <div id="Mersennes"></div>
 </BODY>
</HTML>

计算结果截图

溢出了吧，我在C#中用double的结果和你一样

这个C#版本可以算nnnnn大，（说实话，我不知道能算到多大）

using System;
using Microsoft.FSharp.Math;
using System.Threading;



namespace LucasLehmer
{
    class Program
    {
        static void Main(string[] args)
        {
            int range=20000;
            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            Parallel.For(2, range, delegate(int i)
            {

                if (LucasLehmerTest(i))
                {
                    System.Console.WriteLine("M({0})={1}", i, Mersenne(i));
                }
            });
            sw.Stop();

            System.Console.WriteLine("It take {0} seconds to caculate Mersenne in {1}", sw.ElapsedMilliseconds, range);

        }

        public static BigInt LucasLehmerSequence(BigInt n, BigInt m)
        {
            //if(n<BigInt.Zero)
                //throw new ArgumentOutOfRangeException("LucasLehmer seq must larger than 0.");

            return (n.Equals(BigInt.Zero) ? BigInt.FromInt32(4): BigInt.Pow(LucasLehmerSequence(n - BigInt.One, m), BigInt.FromInt32(2)) - BigInt.FromInt32(2)) % m;

        }

        public static BigInt Mersenne(int n)
        {   
          
           //if(n < 0)
               //throw new ArgumentOutOfRangeException("Mersenne seq must larger than 0.")  ;

            return BigInt.Pow(BigInt.FromInt32(2),BigInt.FromInt32(n))-BigInt.One;
        }
        
        public static bool LucasLehmerTest(int n){

            BigInt m = Mersenne(n);   
            return (LucasLehmerSequence(BigInt.FromInt32(n - 2), m) == BigInt.Zero);
        }
  
    
    }
}

C#也不见得比Haskell弱，而且充分利用了2个CPU。

楼上的，你怎么做到写那么多文章却只有这么点积分的？传授一下。

PS：你上面的代码用到F#的一个库是么？
能否用纯F#写一个，看看Erlang，Haskell和F#的对比，不过感觉Haskell明显有优势。

这里是我上面算法的Erlang版本，大家也可以拿去优化下，看看如何跑的更深。

Erlang我只跑到M(19)，和之前的js还有ray_linn的C#版本一样，

原因是这个问题：

http://www.iteye.com/problems/14560


Erlang做大数幂运算的时候也报错，所以只能算到M(19)，但非常快，瞬间的事情，所以速度不会很慢。至于怎么修复这个大数计算的问题，我还要找找Erlang有没有别的类型支持。

Erlang代码在这里：

-module(mersenne).  
-export([run/1,mersenne/1,lucasLehmer_sequence/2]).  
  
lucasLehmer_sequence (0, M) -> 4 rem M;  
lucasLehmer_sequence (N, M) when N>0 ->  
        erlang:round((math:pow(lucasLehmer_sequence(N-1,M),2)-2)) rem M.  
  
mersenne(N) when N>0 ->  
   erlang:round(math: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 ->  
                1+1  
    end;  
run(N) ->  
    case lucasLehmer_test(N) of  
        true ->  
                io:format("M(~w) => ~w~n", [N,mersenne(N)]);  
        false ->  
                1+1  
    end,  
    run(N-1).  

http://charlescui.iteye.com/blog/364620

F#速度不如C#,而且算这个东西的关键是实现BigInt,本来我用C#实现了一个，后来看到F#里有，就直接拿过来用了。
这里就用了F#的BigInt,因此是不会产生溢出的。

算到M(1279)都是不花什么力气的，我正在算20000万内的。。。（ps:算的同时还上网听音乐聊QQ)


要分数低太简单了，你就逮着robbin等等那些大佬，专挑着他们的漏洞骂，三下两下就会被隐藏。

明白了，原来积分低是这么搞的。

ruby版本我只能算到M(1279)了，
明后天搞搞Erlang的，看看能不能也能算到无限大，到时候大家拿起Benchmark来PK一下速度，看谁一天或者多久之内能算到多少位。