コラッツ予想がとけたらいいな2

自分の考察を書いていきます。

Go,C++,F#,Haskellでコラッツを計算してみた

こんな感じで。

  • 3から79999999で4x+3のみおこなう。
  • 初期値を下回ったらそのxは終了する。
  • 多倍長整数を使う。
  • 並列計算する。相互作用はしない。
  • 反例があった時のケアはしない。
  • 出力はしたりしなかったり。
  • 実行時間を出力する。

CPUはCOREi7-4770です。

Go

go version go1.4.2 windows/amd64

package main

import (
  //"fmt"
  "log"
  "math/big"
  "runtime"
)

var one = big.NewInt(1)
var two = big.NewInt(2)
var three = big.NewInt(3)

func divv(x *big.Int) *big.Int {
    for {
        if new(big.Int).Mod(x,two).Cmp(one)==0 {
            return x
        }else {
            x = new(big.Int).Div(x,two)
        }
    }
}

// odd only!
func col2(x,y *big.Int) *big.Int {
    for {
        if x.Cmp(y)==-1 {
            return x
        }else {
            x = divv(new(big.Int).Add(new(big.Int).Mul(x,three),one))
        }
    }
}

func col(x *big.Int) *big.Int {
  return col2(x,x)
}

func main(){
    log.Printf("started.")

    // CPU数を取得
    cpus := runtime.NumCPU()
    // ランタイムが使用するCPU数を指定
    runtime.GOMAXPROCS(cpus)

    quit := make(chan bool)

    x := big.NewInt(0)
    for i := 0; i<8000; i++ {
        go func(i int) {
            for j := 3; j<=9999; j+=4 {
                x = big.NewInt(int64(j+i*10000))
                col(x)
            }
            //fmt.Println(x)
            quit <- true
        }(i)
    }

    for i := 0; i<8000; i++ {
        <-quit
    }

    log.Printf("end.")
}
■実行結果
C:\me\Haskell\CollatzPatt\比較\Go>go run CollatzGo.go
2017/02/08 01:56:59 started.
2017/02/08 02:00:05 end.

180sぐらい。
ゴルーチン8人くらいだとCPU使用率が20%くらいだったので8000人発行した。
Goは再帰を使わない方が良いらしいのでそうした。
ちなみに再帰でやると300sくらいかかった。

C++

Target: x86_64-w64-mingw32
gcc version 5.2.0 (Rev3, Built by MSYS2 project)

#include <iostream> // cout
#include <gmpxx.h>
#include <time.h> // clock()
using namespace std;
#define BASE 10

mpz_class divv( mpz_class x ){
    while(1){
        if( x%2==1 ){ return x; } else{ x/=2; }
    }
}

// odd only!
void col( mpz_class x, mpz_class y ){
    while(1){
        if( x < y ){
            return;
        }
        else{
            x = divv(3*x+1);
        }
    }
}

void oneThread( mpz_class x1, mpz_class x2 ){
    while( x1 <= x2 ){
        col(x1, x1);
        x1 += 4;
    }
}

int main(){
    mpz_class XMIN1, XMIN2, XMIN3, XMIN4, XMIN5, XMIN6, XMIN7, XMIN8;
    mpz_class XMAX1, XMAX2, XMAX3, XMAX4, XMAX5, XMAX6, XMAX7, XMAX8;
    clock_t t1, t2;

    XMIN1.set_str("3", BASE); XMAX1.set_str("9999999", BASE);
    XMIN2.set_str("10000003", BASE); XMAX2.set_str("19999999", BASE);
    XMIN3.set_str("20000003", BASE); XMAX3.set_str("29999999", BASE);
    XMIN4.set_str("30000003", BASE); XMAX4.set_str("39999999", BASE);
    XMIN5.set_str("40000003", BASE); XMAX5.set_str("49999999", BASE);
    XMIN6.set_str("50000003", BASE); XMAX6.set_str("59999999", BASE);
    XMIN7.set_str("60000003", BASE); XMAX7.set_str("69999999", BASE);
    XMIN8.set_str("70000003", BASE); XMAX8.set_str("79999999", BASE);

    t1 = clock();

    #pragma omp parallel sections num_threads(8)
    {
        #pragma omp section
        oneThread( XMIN1, XMAX1 );
        #pragma omp section
        oneThread( XMIN2, XMAX2 );
        #pragma omp section
        oneThread( XMIN3, XMAX3 );
        #pragma omp section
        oneThread( XMIN4, XMAX4 );
        #pragma omp section
        oneThread( XMIN5, XMAX5 );
        #pragma omp section
        oneThread( XMIN6, XMAX6 );
        #pragma omp section
        oneThread( XMIN7, XMAX7 );
        #pragma omp section
        oneThread( XMIN8, XMAX8 );
    }

    t2 = clock();
    cout << XMIN1.get_str() << " to " << XMAX8.get_str() << " check end." << endl;
    cout << "running time: " << t2-t1 << "[ms]" << endl;

}
■実行結果
g++ -I"C:/mingw/msys/local/include/" -L"C:/mingw/msys/gmp-6.0.0/.libs" -O3 CollatzCpp.cpp -lgmp -lgmpxx -fopenmp -W -Wall
C:\me\Haskell\CollatzPatt\比較\C++>a.exe
3 to 79999999 check end.
running time: 18843[ms]

18sぐらい。
最速かと思ったけどそうではなかった。
最適化はしてるんだけどなー

F#

Microsoft Visual F# 2015 RC

open System
open System.Numerics

let rec divv (x:BigInteger) :BigInteger = if x%2I = 1I then x else divv(x/2I)
// odd only!
let rec col' (x:BigInteger,y:BigInteger) : BigInteger = if x<y then x else col'(divv(3I*x+1I),y)
let col (x:BigInteger) = col' (x,x)

[<EntryPoint>]
let main argv = 
    let beginTime = DateTime.Now

    let p1 = [for x in 0I..7I -> async {
                let min = 3I + 10000000I * x
                let max = 9999999I + 10000000I * x
                return (Array.map col [|min..4I..max|]) |> Array.sum } ]
             |> Async.Parallel
             |> Async.RunSynchronously
    printfn "%A" p1

    let ts = DateTime.Now.Subtract(beginTime)
    printfn "経過時間:%A[ms]" ts.TotalMilliseconds
    0 // 整数の終了コードを返します
■実行結果
[|6082629653800; 18247089777562; 30403796412308; 42572482194120; 54751121127056;
  66902101501010; 79051298672422; 91230769132854|]
経過時間:20812.7121[ms]

このコードの短さよ。21sぐらい。
ちなみに最適化をしないと230sもかかった。

Haskell

Haskell Platform 8.0.1

import Control.Concurrent
import Data.Time

divv :: Integer -> Integer
divv n | odd n     = n
       | otherwise = divv (n `div` 2)

-- odd only!
col' :: Integer -> Integer -> Integer
col' 1 _ = 1
col' x y = if x<y then x else col' (divv( 3*x + 1 )) y
col :: Integer -> Integer
col x = col' x x

main :: IO ()
main = do
  ref <- newMVar False
  t1 <- getZonedTime
  print t1
  forkIO $ print $ sum $ map col [3,7..9999999]
  forkIO $ print $ sum $ map col [10000003,10000007..19999999]
  forkIO $ print $ sum $ map col [20000003,20000007..29999999]
  forkIO $ print $ sum $ map col [30000003,30000007..39999999]
  forkIO $ print $ sum $ map col [40000003,40000007..49999999]
  forkIO $ print $ sum $ map col [50000003,50000007..59999999]
  forkIO $ print $ sum $ map col [60000003,60000007..69999999]
  forkFinally (print $ sum $ map col [70000003,70000007..79999999]) (\_ -> ending ref)
  wait t1 ref
    where
      wait t1 ref = do
        refi <- takeMVar ref
        if refi == True
          then do t2 <- getCurrentTime
                  putStrLn $ "time: " ++ show(diffUTCTime t2 $ zonedTimeToUTC t1)
          else wait t1 ref
      ending ref = do putMVar ref True
■実行結果
ghc -threaded --make CollatzHS.hs -O
C:\me\Haskell\CollatzPatt\比較\Haskell>CollatzHS.exe +RTS -N
2017-02-04 23:43:57.528311 東京 (標準時)
18247089777562
66902101501010
79051298672422
30403796412308
42572482194120
6082629653800
54751121127056
91230769132854
time: 5.7740676s

なんと6sぐらい!
爆速じゃないですか!
関数型言語だし。

感想

Haskellびいきの自分としては嬉しい結果になった。
しかし、これが全てという自信はないので、違う環境でやれば違う結果が出るかもしれない。

18/12/02追記


計算値がIntの範囲内だったから、
2000京を足して、20000000000000000003から20000000000079999999までやってみたけど、そんなに変わらなかった。