こんな感じで。
- 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までやってみたけど、そんなに変わらなかった。