probabilistic pi algorithm

After hearing the idea of a probabilistic algorithm that is calculating pi
I decided to implement it in perl,and the following is what I obtained:

 23 #
 24 # pi*($d/2)**2    in circle
 25 # ------------ ~ ----------- ~ pi/4
 26 #  $d**2          in total
 27 #
 28 
 29 
 30 
 31 use strict;
 32 use warnings;
 33 
 34 my $d = 1000;#diameter
 35 my $no_total = 1000000;#number of points
 36 my $no_in=0;
 37 
 38 sub gen_xy { ( int(rand($d)),int(rand($d)) ); }
 39 
 40 sub in_circle {
 41     my ($x,$y) = @_;
 42     ($x - $d/2)**2 + ($y - $d/2)**2 <= ($d/2)**2
 43     ? 1
 44     : 0;
 45 }
 46 
 47 
 48 $no_in += in_circle gen_xy
 49     for 1..$no_total;
 50 
 51 warn "Pi approx: ". (  $no_in/$no_total ) *4  ;
[download]

I'm ignoring the fact that this code is useless,it's really slow and there are
C programs which can be found through google which are able to get pi to 10000 decimals
It does confirm that pi is ~3.14 after 10 seconds of running time

Comment on probabilistic pi algorithm Download Code

Replies are listed 'Best First'.
Re: probabilistic pi algorithm by FunkyMonk (Bishop) on Feb 15, 2008 at 15:58 UTC
You can simplify this quite a bit if you use a radius of 1, rather than a diameter of 1000. When R = 1, the test becomes `$x * $x + $y * $y <= 1`. (Very) Old Habits Die Hard. Hence my use of `$x$x` rather than `$x2`. I doubt there's much difference on modern processors. Update: s/\^/*/. Thanks to kyle for pointing it out	[reply] [d/l] [select]
Re^2: probabilistic pi algorithm by bart (Canon) on Feb 16, 2008 at 09:30 UTC
Hence my use of $x$x rather than $x*2. I doubt there's much difference on modern processors. Oh yes it does make a difference. `$x$x` does a multiplication of two numbers, while `$x2` goes the long route of `exp(log($x)2)`, as `**` is a very generic power raising operator. Not only will it take longer (maybe negligible these days, like you say), but most of all: its result will be less precise: both log and exp have quite large margins of error.	[reply] [d/l] [select]
Re^2: probabilistic pi algorithm by spx2 (Deacon) on Feb 16, 2008 at 09:34 UTC
hi, Your ideea is very nice,I thought about it so if we take $d=2 then the radius which in this case is $d/2=1 so now we can have the formula `($x-1)2 + ($y-1)2 <= 1` exactly as you write in your comment. About the difference between $x$x and $x*2,what optimisations do you think could be made ?	[reply] [d/l]
Re^3: probabilistic pi algorithm by FunkyMonk (Bishop) on Feb 16, 2008 at 10:07 UTC
Subroutine calls in Perl are expensive, especially when there's a few million of them, so inline as much as you can. Benchmarking 3 variants reveals... `Rate original multiply powers original 0.405/s -- -72% -76% multiply 1.45/s 257% -- -14% powers 1.69/s 317% 17% --` [download] Read more... (1179 Bytes)	[reply] [d/l] [select]
Re^3: probabilistic pi algorithm by starbolin (Hermit) on Feb 20, 2008 at 06:35 UTC
Further optimization is of little value in terms of convergence. The problem is in the random-walk nature of the convergence. While the quotient is guaranteed to eventually converge, over a given interval the quotient can diverge. While convergence is guaranteed the time over which it converges is not guaranteed. s//----->\t/;$~="JAPH";s//\r<$~~/;{s\|~$~-\|-~$~\|\|\|s \|-$~~\|$~~-\|\|\|s,<$~~,<~$~,,s,~$~>,$~~>,, $\|=1,select$,,$,,$,,1e-1;print;redo}	[reply] [d/l]