monte carlo pi estimation in different languages

README.md

montecarlo pi estimations in various languages. Just a bit of fun.

Requires:

• rustc
• go
• gcc
• python2
• pypy
• python3
• ruby

Makefile

all: monte-c monte-go monte-rs monte-gccgo

monte-go:
	go build montepi.go && mv montepi monte-go

monte-rs:
	rustc -O -o monte-rs montepi.rs

monte-c:
	gcc -std=c99 -O2 -o monte-c montepi.c -lm
	gcc -std=c99 -o monte-c-unop montepi.c -lm

monte-gccgo:
	gccgo -g -O2 -c montepi.go
	gccgo -g -O2 -o monte-gccgo montepi.o
	rm -f montepi.o
	gccgo -g -c montepi.go
	gccgo -g -o monte-gccgo-unop montepi.o
	rm -f montepi.o

clean:
	rm -f monte-c monte-go monte-rs monte-gccgo monte-gccgo-unop monte-c-unop

fast: all
	@gcc --version 2>/dev/null |grep -E "(gcc|LLVM)"
	/usr/bin/time -p ./monte-c
	@echo ""
	@go version
	/usr/bin/time -p ./monte-go
	@echo ""
	@echo gccgo --version |grep "gcc"
	/usr/bin/time -p ./monte-gccgo
	@echo ""
	@echo gccgo --version |grep "gcc"
	/usr/bin/time -p ./monte-gccgo-unop
	@echo ""
	@rustc --version
	/usr/bin/time -p ./monte-rs

slow: fast
	@echo ""
	@ruby --version
	/usr/bin/time -p ./montepi.rb
	@echo ""
	@python -V
	/usr/bin/time -p ./montepi.py
	@echo ""
	@pypy -V
	/usr/bin/time -p pypy ./montepi.py
	@echo ""
	@python3 -V
	/usr/bin/time -p python3 ./montepi.py
	@echo ""
	@php --version |grep cli
	/usr/bin/time -p php ./montepi.php

montepi.c

/* montecarlo approximation of pi in c */
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>

#define ITERATIONS 100000000

int in_circle(float x, float y) {
    if (sqrt(x*x + y*y) <= 1.0) {
        return 1;
    }
    return 0;
}

int main() {
    srand(time(NULL));
    rand();

    int hits=0;

    for (int i=0; i<ITERATIONS; i++) {
        float r1 = (float)rand()/(float)RAND_MAX;
        float r2 = (float)rand()/(float)RAND_MAX;
        if (in_circle(r1, r2)) {
            hits++;
        }
    }
    printf("Pi: %0.6f\n", (4 * ((float)hits / ITERATIONS)));
    return 0;
}

montepi.go

// montecarlo approximation of pi in go
package main

import (
	"math"
	"math/rand"
	"time"
)

const iterations = 100000000

func inCircle(x, y float64) bool {
	return math.Sqrt(x*x+y*y) <= 1.0
}

func main() {
	source := rand.NewSource(time.Now().Unix())
	r := rand.New(source)
	var h int
	for i := 0; i <= iterations; i++ {
		if inCircle(r.Float64(), r.Float64()) {
			h++
		}
	}
	pi := 4 * float64(h) / float64(iterations)
	println("Pi:", pi)
}

montepi.php

<?php
 
$iterations = isset($argv[1]) ? (int) $argv[1] : 100000000;
$randmax = mt_getrandmax();
$hits = 0;

function inCircle($x, $y) {
  return sqrt($x * $x + $y * $y) <= 1.0;
}

for ($i = 0; $i < $iterations; ++$i) {
    $x = mt_rand() / $randmax;
    $y = mt_rand() / $randmax;
    if (inCircle($x, $y)) {
        ++$hits;
    }
}
 
printf("Pi: %0.6f\n", (4 * ($hits / $iterations)));

montepi.py

#!/usr/bin/env python

from time import time
from random import random, seed
from math import sqrt

seed(time())
iterations = 100000000

if 'xrange' not in dir(__builtins__):
    __builtins__.xrange = range

def in_circle(x, y):
    return sqrt(x*x + y*y) <= 1.0

hits = 0
for i in xrange(1, iterations):
    if in_circle(random(), random()):
        hits += 1

pi = 4 * (hits / float(iterations))
print("pi = %0.6f" % (pi))

montepi.rb

#!/usr/bin/env ruby

def in_circle(x, y)
    return Math.hypot(x, y) <= 1.0
end

iterations = 100000000
h = 0
(0..iterations).each do |i|
    if in_circle(rand(), rand())
        h+=1
    end
end

pi = 4.0 * h / iterations.to_f
puts "Pi: #{pi}" 

montepi.rs

// montecarlo approximation of pi in rust

use std::rand;
use std::rand::{Rng, XorShiftRng};

fn in_circle(x :f64, y :f64) -> bool {
    let f = (x*x + y*y).sqrt();
    f <= 1.0
}

fn main() {
    let iterations = 100000000i;
    
    let mut rng: XorShiftRng = rand::random();
    let mut hits = 0i;

    for _ in range(0i, iterations) {
        let x = rng.gen::<f64>();
        let y = rng.gen::<f64>();
        if in_circle(x, y) {
            hits+=1;
        } 
    }

    let pi :f64 = 4.0 * hits as f64 / iterations as f64;
    println!("Pi: {}", pi);
}

// On my machine the javascript version took 1.452 seconds using exact same algorithm.
// Without Math.sqrt you get the same result faster (1.327 sec) since x and y are between 0 and 1
// and sqrt(n) <= 1 ==> n<=1

function inCircle (x,y) {
return Math.sqrt(x_x +y_y) <= 1.0
};

function calcwithsqrt(){
var iterations = 100000000;
var t1 = Date.now();
var h = 0;
for (var i =0; i <= iterations; i++ ) {
if (inCircle(Math.random(), Math.random())){
h++}
};
var pi = 4.0 *h/iterations;
var t2 = Date.now();
console.log('----With SQRT-----');
console.log(pi);
console.log((t2-t1) + ' ms')
};

function calc(){
var iterations = 100000000;
var t1 = Date.now();
var h = 0,x=0,y=0;
for (var i =0; i <= iterations; i++ ) {
x = Math.random();
y = Math.random();
if (x_x + y_y <= 1.0){
h++}
};
var pi = 4.0 *h/iterations;
var t2 = Date.now();
console.log('----WithOUT SQRT-----');
console.log(pi);
console.log((t2-t1) + ' ms')
};

calcwithsqrt();
calc();

/* results
----With SQRT-----
3.14170776
1452 ms
----WithOUT SQRT-----
3.14153456
1327 ms
*/

To put PyPy's performance into perspective, here is Lua:

local random = math.random
local sqrt = math.sqrt

math.randomseed(os.clock())

local iterations = 100000000

local in_circle = function(x, y)
    return sqrt(x*x+y*y) <= 1
end

local hits = 0
for i=1,iterations do
    if in_circle(random(), random()) then
        hits = hits + 1
    end
end

local pi = 4 * (hits / iterations)
print("pi = " .. pi)

I left the useless sqrt in to avoid comparing apples to bananas.

On my machine (Vaio Pro 13) I get:

Lua 5.2           0m17.321s
LuaJIT 2.0.3      0m1.887s
Python 2.7.8      0m45.222s
Python 3.4.2      1m6.372s
PyPy 2.4.0        0m6.723s
Ruby 2.1.3        0m22.804s
rubinius 2.2.10   0m47.471s
GCC 4.9.1 O0      0m3.415s
GCC 4.9.1 O2      0m2.233s
GCC 4.9.1 Os      0m2.307s
GCC 4.9.1 O3      0m2.161s
clang 3.5.0 O0    0m3.469s
clang 3.5.0 O2    0m2.280s
clang 3.5.0 Os    0m2.293s
clang 3.5.0 O3    0m2.311s
php 5.6.2         0m42.297s
rustc 0.13.0      0m1.666s
go 1.3.3          0m4.673s
v8 3.29.88.8      0m2.292s

LuaJIT is the second fastest of all, just behind Rust (with diabolic performance :p), and it blows PyPy out of the water :)

Of course this is clearly not the most significant of benchmarks...

EDIT: adding JavaScript (v8, using d8, code below adapted from @abpin):

function inCircle (x,y) {
  return Math.sqrt(x*x +y*y) <= 1.0
};

var iterations = 100000000;
var h = 0;
for (var i =0; i <= iterations; i++ ) {
    if (inCircle(Math.random(), Math.random())) {
        h++
    }
};
var pi = 4.0 * h/iterations;
print(pi);

I improved pypy performance a bit (about 20%), however the random algorithm used by pypy (and python) is much more powerful than the one used by C (and hence more computationally expensive). It's possible to improve "a bit", but I doubt we can match the C performance.

I didn't realize this gist had comments ^_^;

Once you get down to it, these are mostly about the rngs; especially the fastest ones. It's by far the most expensive part of the computation once you've got rid of all the dumb stuff.

Also, luajit, v8 and pypy are pretty incredible pieces of software.