Create a gist now

Instantly share code, notes, and snippets.

@jmoiron /Makefile
Last active Dec 23, 2015

What would you like to do?
monte carlo pi estimation in different languages

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

Requires:

  • rustc
  • go
  • gcc
  • python2
  • pypy
  • python3
  • ruby
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
/* 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;
}
// 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)
}
<?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)));
#!/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))
#!/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}"
// 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);
}

abpin commented Oct 20, 2014

// 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
*/

catwell commented Oct 20, 2014

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);

fijal commented Oct 23, 2014

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.

Owner

jmoiron commented Mar 24, 2015

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment