計算スピードの比較

ライプニッツ級数

$$
\sum_{n=0}^{\infty}\frac{(-1)^n}{2n+1} = \frac{\pi}{4}
$$

は収束が遅い.それを利用して言語毎に計算要する時間を評価する.和の上限を$10^8$(bashを除く)とする.
(別にfor文で回すだけなのでこの計算でなくても良いのだが,作ってしまったものは仕方がない)

$ cat /proc/cpuinfo  
model name  : Intel(R) Xeon(R) CPU E5-1680 v3 @ 3.20GHz

gnu版のtimeはメモリーの使用量も計測できるのでgnu版を使う

注意としてubuntu(bash)のtimeコマンドにはbash版gnu版がありgnu版を使うためには

$ /usr/bin/time

もしくは

\time

とすれば良いようだ.フォーマットは以下のようにして出力する

$ fmt="\nreal:%e[sec]\nuser:%U[sec]\nsys:%S[sec]\nMemory:%M[KB]"
\time -f ${fmt} ./LeibnizFormula

どの言語を学ぶべきかは,このひとの解説が楽しい.

計算速度は実装の仕方にも依存するので,必ずしも最適なコードを書いたわけではないが,素朴にコードを書いた結果を以下に示す.

(修正)
ご指摘頂きありがとうございます.頂いたコメントに基づき逐次修正したいと思います.

C言語

なんだかんだ慣れ死んだC言語

LeibnizFormula.c
# include <stdio.h>
# include <math.h>
int main(void){
  int i;
  double s = 0.0;
  for(i = 0; i<=1e8; i++){
    s += pow(-1.0, i) / (2.0 * i + 1.0);
  };
  printf("Ans:%.16f\n",4*s);
  return 0;

}
$ gcc -o LeibnizFormula LeibnizFormula.c -lm
$ \time -f ${fmt} ./LeibnizFormula
Ans:3.1415926635893259

real:3.68[sec]
user:3.67[sec]
sys:0.00[sec]
Memory:624[KB]

(加筆)
最適化の有無.最適化すると速度の誤差が大きくなる気がするので適当な試行での結果

$ gcc --version
gcc (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4
$ gcc -Ofast -o LeibnizFormula LeibnizFormula.c -lm
$ \time -f ${fmt} ./LeibnizFormula
Ans:3.1415926635893259

real:3.39[sec]
user:3.39[sec]
sys:0.00[sec]
Memory:620[KB]

$ gcc -Ofast -march=native -o LeibnizFormula LeibnizFormula.c -lm
$ \time -f  ${fmt} ./LeibnizFormula
Ans:3.1415926635893259

real:3.23[sec]
user:3.23[sec]
sys:0.00[sec]
Memory:620[KB]

fortran

fortranは良い言語.優しく見守りたい.

LeibnizFormula.f90
program LeibnizFormula
  implicit none
  integer :: i = 0
  real(8) :: s = 0.0
  do i=0, 10**8
     s = s + (-1.0)**i /(2.0*i + 1.0)
  end do
  print *, 'Ans:', s*4
end program LeibnizFormula
$ \time -f ${fmt} ./LeibnizFormula
 Ans:   3.1415926653536932     

real:4.99[sec]
user:4.99[sec]
sys:0.00[sec]
Memory:936[KB]

意外とCの方が早い

(加筆)
最適化の有無.最適化すると速度の誤差が大きくなる気がするので適当な試行での結果

$ gfortran --version
GNU Fortran (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4

$ gfortran -Ofast -o LeibnizFormula LeibnizFormula.c -lm
$ \time -f ${fmt} ./LeibnizFormula
 Ans:   3.1415926653536932     

real:4.83[sec]
user:4.83[sec]
sys:0.00[sec]
Memory:936[KB]

$ gfortran -Ofast -march=native -o LeibnizFormula LeibnizFormula.c -lm
$ \time -f ${fmt} ./LeibnizFormula
 Ans:   3.1415926653536932     

real:4.67[sec]
user:4.67[sec]
sys:0.00[sec]
Memory:936[KB]

python

本命だけど浮気中

LeibnizFormula.py
import math
import numpy as np
import numba

def LeibnizFormula1(nmax):
    s = 0
    for i in range(0,nmax+1):
        a = (-1)**i * 1/(2*i + 1)
        s += a
    return 4*s

def LeibnizFormula2(nmax):
    s = np.array([(-1)**i * 1/(2*i + 1) for i in range(0,nmax+1)])
    return 4*np.sum(s)

def LeibnizFormula3(nmax):
    s = np.sum([(-1)**i * 1/(2*i + 1) for i in range(0,nmax + 1)])
    return 4*s

@numba.jit
def LeibnizFormula4(nmax):
    s = 0
    for i in range(nmax+1):
        s += (-1)**i * 1/(2*i + 1)
    return 4*s



if __name__ == "__main__":
    import sys 
    f = eval(sys.argv[1])
    pi = f(10**8)
    print(pi)

結果 numbaが早い

$ \time -f ${fmt} python LeibnizFormula.py LeibnizFormula1
3.141592663589326
real:49.65[sec]
user:49.60[sec]
sys:0.03[sec]
Memory:44316[KB] = 43[MB]

$ \time -f ${fmt} python LeibnizFormula.py LeibnizFormula2
3.14159266359
real:51.82[sec]
user:50.76[sec]
sys:1.03[sec]
Memory:3990024[KB] = 3896[MB] = 3.8[GB]

$ \time -f ${fmt} python LeibnizFormula.py LeibnizFormula3
3.14159266359
real:50.18[sec]
user:49.13[sec]
sys:1.02[sec]
Memory:3989640[KB] = 3896[MB] = 3.8[GB]

$ \time -f ${fmt} python LeibnizFormula.py LeibnizFormula4
3.141592663589326
real:3.93[sec]
user:3.89[sec]
sys:0.03[sec]
Memory:52848[KB] = [51MB]

Wolfram言語 (Mathematica)

本妻

LeibnizFormula.wl
pi = 4*Sum[N[ (-1)^n / (2*n+1) ],{n,0,10^8}];
Print@pi
$ \time -f ${fmt} wolframscript -script LeibnizFormula.wl
3.141592663589326

real:4.99[sec]
user:4.88[sec]
sys:0.13[sec]
Memory:80456[KB] = 78[MB]

ParallelSumに書き直すともっと早くなるけどここでは試さない

Haskell

お堅い

LeibnizFormula.hs
main = do
  print $ 4 * sum [ (-1)**n /(2*n+1) | n <- [0..10^8] ]

listを作ると,大量のメモリを食らってしまうのでlistを作らない書き方の方が良いと思う.
もっと賢い実装があると思うけど,まだ勉強中・・・

$ ghc -O -rtsopts -with-rtsopts=-K20G LeibnizFormula.hs
$ \time -f ${fmt} ./LeibnizFormula
3.141592663589326

real:36.90[sec]
user:32.70[sec]
sys:4.11[sec]
Memory:16264736[KB] = 15883[MB] = 15[GB]

(加筆)
メモリー大喰らいを回避する方法を教えて頂いた.コードをコピペで申し訳ないがこの方法では非常に早くまたメモリー使用量も申し分ない.

import Data.List (foldl')

main = do
  print $ 4 * sum' [ (-1)**n /(2*n+1) | n <- [0..10^8] ]
  where
    sum' = foldl' (+) 0
$ \time -f ${fmt} ./LeibnizFormula2
3.141592663589326

real:13.16[sec]
user:13.10[sec]
sys:0.04[sec]
Memory:2284[KB]

Julia

このまとめきっかけを与えてくれた言語.現在勉強中.

(加筆)
コメントにもあるとおり,実行の方法や実装によって速度に影響が出そうなのでもう少しjuliaについて勉強します

LeibnizFormula.jl
s = 0
for n = 0:1:10^8
    s += (-1)^n /(2n + 1)
end
print(4*s,"\n")
$ \time -f ${fmt} julia LeibnizFormula.jl
3.141592663589326

real:8.76[sec]
user:8.70[sec]
sys:0.89[sec]
Memory:182372[KB] = 178[MB]

噂通りCの2倍程度遅い.

Java

知らない言語

LeibnizFormula.java
public class LeibnizFormula {
  public static void main(String[] args){
      int i;
      double s=0d;
      for(i=0; i<=1e8; i++){
        s += Math.pow(-1.0, i)/(2.0*i+1.0);
      }
      System.out.println("Ans:" + 4*s);
    }
}
$ javac LeibnizFormula.java
$ \time -f ${fmt} java -cp . LeibnizFormula 
Ans:3.141592663589326

real:8.18[sec]
user:8.18[sec]
sys:0.02[sec]
Memory:22596[KB]

Javascript

意外と早い娘

LeibnizFormula.js
var s = 0.0;
for (var i = 0; i<=1e8; i++){
  s += Math.pow(-1.0, i) / (2*i + 1);
}
console.log('%d',4*s);
$ \time -f ${fmt} node LeibnizFormula.js
3.141592663589326

real:4.94[sec]
user:4.95[sec]
sys:0.02[sec]
Memory:10956[KB] = 10[MB]

bash

じつは計算できる娘だけど,めちゃくちゃ遅い.ここでは和の上限を$10^4$とした.

LeibnizFormula.sh
i=0
s=0
while [ ${i} -le `echo 10^4 | bc` ]; do
  s=`echo "scale=18; ${s} + (-1)^${i}/(2*${i} + 1)" | bc`
  i=$(( i + 1 ))
done
echo "scale=18; 4*$s" | bc
$ \time -f ${fmt} bash LeibnizFormula.sh
3.141692643590542976

real:44.47[sec]
user:4.99[sec]
sys:50.23[sec]
Memory:1548[KB]

演算の回数を減らした方が早い

LeibnizFormula.sh
s=0
#while [ ${i} -le `echo 10^4 | bc` ]; do
nmax=`echo 10^4 | bc`
for i in `seq 0 $nmax`; do
  s=`echo "scale=18; ${s} + (-1)^${i}/(2*${i} + 1)" | bc`
done
echo "scale=18; 4*$s" | bc
$ \time -f ${fmt} bash LeibnizFormula.sh 
3.141692643590542976

real:23.80[sec]
user:2.49[sec]
sys:27.27[sec]
Memory:2480[KB]

Lisp

かっこかっこかっこ

LeibnizFormula.lsp
(setq s 0.0)

(dotimes (n (+ (expt 10 8) 1))
  (setq s (+ s (/ (expt -1 n) (+ (* n 2) 1) )    ))
)
(print (* 4 s))

$ \time -f ${fmt} clisp LeibnizFormula.lsp

3.1415968

real:177.54
user:174.38
sys:3.05
Memory:6832[KB]

Scala

遅いかと思いきや案外そうでもない

LeibnizFormula.scala
var s=0.0;
for( n <- ( 0 to scala.math.pow(10,8).toInt ) ) s += scala.math.pow(-1.0,n)/(2.0*n + 1.0)
println(4*s)

$ \time -f ${fmt} scala LeibnizFormula.scala
3.141592663589326

real:8.14
user:7.97
sys:0.03
Memory:41892[KB]

Go

早いかと思いきやそーでもない

LeibnizFormula.go
package main

import "fmt"
import "math"

func main(){
  n := 0
  s := 0.0
  nmax := int(math.Pow(10,8))
  for n < nmax {
    s += math.Pow(-1.0, float64(n))/ float64(2 * n + 1)
    n += 1
  }
  fmt.Println(4 * s)
}
$ \time -f ${fmt} go run LeibnizFormula.go 
3.141592643589326

real:13.15[sec]
user:12.91[sec]
sys:0.06[sec]
Memory:39628[KB]

実装が悪いのか?

C++

(指摘を頂きプログラムミスを修正)

LeibnizFormula.cpp
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
  double s=0.0;
  for(int n=0; n<=1e8; n++){
    s += pow(-1, n) /(2.0 * n + 1.0);
  }
  cout << 4*s << endl;
}
$ \time -f ${fmt} ./LeibnizFormula
3.14159

real:4.33[sec]
user:4.31[sec]
sys:0.00[sec]
Memory:1268[KB]

(加筆)
最適化の有無

$ g++ --version
g++ (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4

$ g++ -Ofast -o LeibnizFormula LeibnizFormula.c -lm
$ \time -f ${fmt} ./LeibnizFormula
3.14159

real:3.27[sec]
user:3.27[sec]
sys:0.00[sec]
Memory:1264[KB]

$ g++ -Ofast -march=native -o LeibnizFormula LeibnizFormula.c -lm
$ \time -f ${fmt} ./LeibnizFormula
3.14159

real:3.18[sec]
user:3.18[sec]
sys:0.00[sec]
Memory:1264[KB]

ruby

コメントにあったプログラムを実行すると,sumがundefinedだった.rubyは触ったことが無いので適当に書いてみた

LeibnizFormula.rb
puts (0..(10**8)).inject(0) {|sum, i| sum + ((-1.0)**i)/(2.0*i + 1.0) } * 4
$ \time -f ${fmt} ruby2.0 LeibnizFormula.rb 
3.141592663589326

real:16.90[sec]
user:16.88[sec]
sys:0.00[sec]
Memory:6956[KB]
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account log in.