25
\$\begingroup\$

Happy Pi Day everyone! For no reason at all, I'm trying to construct a Monte Carlo estimator of Pi that is as short as possible. Can we construct one that can fit in a tweet?

To clarify, what I have in mind is the typical approach of drawing random points from the unit square and calculating the ratio that fall within the unit circle. The number of samples can be hard coded or not. If you hardcode them, you must use at least 1000 samples. The result may be returned or printed as a floating point, fixed point or rational number.

No trig functions or Pi constants, must be a Monte Carlo approach.

This is code golf, so the shortest submission (in bytes) wins.

\$\endgroup\$
  • 2
    \$\begingroup\$ are trig functions allowed? I suggest you explicitly ban them. \$\endgroup\$ – Level River St Mar 14 '15 at 16:08
  • \$\begingroup\$ ((0..4e9).map{rand**2+rand**2<1}.to_s.sub(/./,"$1.") \$\endgroup\$ – John Dvorak Mar 14 '15 at 18:37
  • \$\begingroup\$ @JanDvorak How is that supposed to work? Doesn't the map give you an array of true and false? \$\endgroup\$ – Martin Ender Mar 14 '15 at 19:16
  • \$\begingroup\$ @MartinBüttner Ah, oops, sorry. .filter{...}.size should work, though. \$\endgroup\$ – John Dvorak Mar 14 '15 at 19:51
  • \$\begingroup\$ @JanDvorak Indeed. That's really neat :) \$\endgroup\$ – Martin Ender Mar 14 '15 at 19:53

35 Answers 35

17
\$\begingroup\$

80386 machine code, 40 38 bytes

Hexdump of the code:

60 33 db 51 0f c7 f0 f7 e0 52 0f c7 f0 f7 e0 58
03 d0 72 03 83 c3 04 e2 eb 53 db 04 24 58 db 04
24 58 de f9 61 c3

How to get this code (from assembly language):

    // ecx = n (number of iterations)
    pushad;
    xor ebx, ebx; // counter
    push ecx; // save n for later
myloop:
    rdrand eax; // make a random number x (range 0...2^32)
    mul eax; // calculate x^2 / 2^32
    push edx;
    rdrand eax; // make another random number y
    mul eax; // calculate y^2 / 2^32
    pop eax;
    add edx, eax; // calculate D = x^2+y^2 / 2^32 (range 0...2^33)
    jc skip; // skip the following if outside the circle
    add ebx, 4; // accumulate the result multiplied by 4
skip:
    loop myloop;
    push ebx; // convert the result
    fild dword ptr [esp]; // to floating-point
    pop eax;
    fild dword ptr [esp]; // convert n to floating-point
    pop eax;
    fdivp st(1), st; // divide

    popad;
    ret;

This is a function using MS fastcall calling convention (number of iterations is passed in register ecx). It returns the result in the st register.

Fun things about this code:

  • rdrand - just 3 bytes to generate a random number!
  • It uses (unsigned) integer arithmetic until the final division.
  • The comparison of squared distance (D) with squared radius (2^32) is performed automatically - the carry flag contains the result.
  • To multiply the count by 4, it counts the samples in steps of 4.
\$\endgroup\$
  • \$\begingroup\$ Comment should read "Calculate x^2 % 2^32" \$\endgroup\$ – Cole Johnson Mar 20 '15 at 23:31
  • \$\begingroup\$ @ColeJohnson No - the random number is in eax; the mul command multiples it by itself and puts the high part in edx; the low part in eax is discarded. \$\endgroup\$ – anatolyg Mar 22 '15 at 13:03
11
\$\begingroup\$

Matlab/Octave, 27 bytes

I know there already is a Matlab/Octave answer, but I tried my own approach. I used the fact that the integral of 4/(1+x^2) between 0 and 1 is pi.

mean(4./(1+rand(1,1e5).^2))
\$\endgroup\$
  • \$\begingroup\$ A different algorithm is always great! Also, more efficient! \$\endgroup\$ – anatolyg Mar 16 '15 at 9:44
7
\$\begingroup\$

R, 40 (or 28 or 24 using other methods)

mean(4*replicate(1e5,sum(runif(2)^2)<1))

mean(4*sqrt(1-runif(1e7)^2))

mean(4/(1+runif(1e7)^2))

Python 2, 56

Another Python one, if numpy is allowed, but pretty similar to Matlab/Octave:

import numpy;sum(sum(numpy.random.rand(2,8e5)**2)<1)/2e5
\$\endgroup\$
6
\$\begingroup\$

Mathematica, 42 40 39 bytes (or 31/29?)

I've got three solutions all at 42 bytes:

4Count[1~RandomReal~{#,2},p_/;Norm@p<1]/#&
4Tr@Ceiling[1-Norm/@1~RandomReal~{#,2}]/#&
4Tr@Round[1.5-Norm/@1~RandomReal~{#,2}]/#&

They are all unnamed functions that take the number of samples n andd return a rational approximating π. First they all generate n points in the unit square in the positive quadrant. Then they determine the number of those samples that lie within the unit circle, and then they divide by the number of samples and multiply by 4. The only difference is in how they determine the number of sampples inside the unit circle:

  • The first one uses Count with the condition that Norm[p] < 1.
  • The second one subtracts the norm of each point from 1 and then rounds up. This turns numbers inside the unit circle to 1 and those outside to 0. Afterwards I just sum them all up with Tr.
  • The third one does essentially the same, but subtracts the from 1.5, so I can use Round instead of Ceiling.

Aaaaaand while writing this up, it occurred to me that there is indeed a shorter solution, if I just subtract from 2 and then use Floor:

4Tr@Floor[2-Norm/@1~RandomReal~{#,2}]/#&

or saving another byte by using the Unicode flooring or ceiling operators:

4Tr@⌊2-Norm/@1~RandomReal~{#,2}⌋/#&
4Tr@⌈1-Norm/@1~RandomReal~{#,2}⌉/#&

Note that the three rounding-based solutions can also be written with Mean instead of Tr and without the /#, again for the same bytes.


If other Monte Carlo based approaches are fine (specifically, the one Peter has chosen), I can do 31 bytes by estimating the integral of √(1-x2) or 29 using the integral of 1/(1+x2), this time given as a floating point number:

4Mean@Sqrt[1-1~RandomReal~#^2]&
Mean[4/(1+1~RandomReal~#^2)]&
\$\endgroup\$
6
\$\begingroup\$

CJam, 27 23 22 or 20 bytes

4rd__{{1dmr}2*mhi-}*//

2 bytes saved thanks to Runner112, 1 byte saved thanks to Sp3000

It takes the iteration count from STDIN as an input.

This is as straight forward as it gets. These are the major steps involved:

  • Read the input and run the Monte Carlo iterations that many times
  • In each iteration, get sum of square of two random floats from 0 to 1 and see if it is less than 1
  • Get the ratio of how many times we got less than 1 by total iterations and multiply it by 4 to get PI

Code expansion:

4rd                     "Put 4 on stack, read input and convert it to a double";
   __{            }*    "Take two copies, one of them determines the iteration"
                        "count for this code block";
      {1dmr}2*          "Generate 2 random doubles from 0 to 1 and put them on stack";
              mh        "Take hypot (sqrt(x^2 + y^2)) where x & y are the above two numbers";
                i       "Convert the hypot to 0 if its less than 1, 1 otherwise";
                 -      "Subtract it from the total sum of input (the first copy of input)";
                    //  "This is essentially taking the ratio of iterations where hypot";
                        "is less than 1 by total iterations and then multiplying by 4";

Try it online here


If average value of 1/(1+x^2) is also considered as Monte Carlo, then this can be done in 20 bytes:

Urd:K{4Xdmr_*)/+}*K/

Try it here

\$\endgroup\$
  • 2
    \$\begingroup\$ I tried a CJam answer as well, and managed to come in 2 bytes under your score. But my code came out so similarly to yours, I'd feel dirty posting it as a separate answer. Everything was the same except for the variable choice and these two optimizations: get a random number from 0 to 1 with 1dmr instead of KmrK/, and check if the sum of the squares is greater than 1 with i instead of 1> (I thought this one was particularly clever). \$\endgroup\$ – Runer112 Mar 14 '15 at 21:27
  • \$\begingroup\$ @Runer112 Thanks. the i trick is really neat! And damn the lack of documentation for 1dmr \$\endgroup\$ – Optimizer Mar 14 '15 at 21:35
5
\$\begingroup\$

Python 2, 77 75 bytes

from random import*;r=random;a=0;exec"a+=r()**2+r()**2<1;"*4000;print a/1e3

Uses 4000 samples to save bytes with 1e3.

\$\endgroup\$
  • 5
    \$\begingroup\$ You could get a little more accuracy at no cost with ...*8000;print a/2e3. \$\endgroup\$ – Logic Knight Mar 15 '15 at 6:32
5
\$\begingroup\$

Commodore 64 Basic, 45 bytes

1F┌I=1TO1E3:C=C-(R/(1)↑2+R/(1)↑2<1):N─:?C/250

PETSCII substitutions: = SHIFT+E, / = SHIFT+N, = SHIFT+O

Generates 1000 points in the first quadrant; for each, adds the truthness of "x^2+y^2<1" to a running count, then divides the count by 250 to get pi. (The presence of a minus sign is because on the C64, "true" = -1.)

\$\endgroup\$
  • \$\begingroup\$ What does (1) do? \$\endgroup\$ – echristopherson Mar 16 '15 at 17:25
  • \$\begingroup\$ @echristopherson, you're misreading it. / isn't the division symbol, it's the character produced by typing SHIFT+N on a Commodore 64 keyboard. R/(1) is the shortcut form for RND(1), ie. "produce a random number between 0 and 1 using the current RNG seed". \$\endgroup\$ – Mark Mar 16 '15 at 19:45
  • \$\begingroup\$ Oh, you're right! Good old PETSCII graphics characters. \$\endgroup\$ – echristopherson Mar 16 '15 at 20:02
5
\$\begingroup\$

J, 17 bytes

Computes the mean value of 40000 sample values of the function 4*sqrt(1-sqr(x)) in the range [0,1].

Handily 0 o.x returns sqrt(1-sqr(x)).

   1e4%~+/0 o.?4e4$0
3.14915
\$\endgroup\$
4
\$\begingroup\$

><> (Fish), 114 bytes

:00[2>d1[   01v
1-:?!vr:@>x|  >r
c]~$~< |+!/$2*^.3
 .41~/?:-1r
|]:*!r$:*+! \
r+)*: *:*8 8/v?:-1
;n*4, $-{:~ /\r10.

Now, ><> doesn't have a built-in random number generator. It does however have a function that sends the pointer in a random direction. The random number generator in my code:

______d1[   01v
1-:?!vr:@>x|  >r
_]~$~< |+!/$2*^__
 __________
___________ _
_____ ____ _______
_____ ____~ ______

It basically generates random bits that make up a binary number and then converts that random binary number to decimal.

The rest is just the regular points in the square approach.

Usage: when you run the code you must make sure to prepopulate the stack (-v in python interpreter) with the number of samples, for example

pi.fish -v 1000

returns

3.164
\$\endgroup\$
4
\$\begingroup\$

Matlab or Octave 29 bytes (thanks to flawr!)

mean(sum(rand(2,4e6).^2)<1)*4

(I am no quite sure if <1 is OK. I read it should be <=1. But how big is the probability to draw exactly 1...)

Matlab or Octave 31 bytes

sum(sum(rand(2,4e3).^2)<=1)/1e3
\$\endgroup\$
  • 1
    \$\begingroup\$ Very nice idea! You could save two additional bytes with mean(sum(rand(2,4e6).^2)<1)*4. \$\endgroup\$ – flawr Mar 15 '15 at 22:20
4
\$\begingroup\$

Java, 108 bytes

double π(){double π=0,x,i=0;for(;i++<4e5;)π+=(x=Math.random())*x+(x=Math.random())*x<1?1e-5:0;return π;}

Four thousand iterations, adding 0.001 each time the point is inside the unit circle. Pretty basic stuff.

Note: Yes, I know I can shed four bytes by changing π to a single-byte character. I like it this way.

\$\endgroup\$
  • \$\begingroup\$ why not 9999 iterations ? \$\endgroup\$ – Optimizer Mar 14 '15 at 22:28
  • 1
    \$\begingroup\$ @Optimizer It makes the sum shorter. For 9999 iterations, I'd have to add a more precise number each time instead, which costs me digits. \$\endgroup\$ – Geobits Mar 14 '15 at 22:34
  • 1
    \$\begingroup\$ You could save another byte and improve precision by using "4e5" and "1e-5" for the numbers. \$\endgroup\$ – Vilmantas Baranauskas Mar 16 '15 at 9:12
  • \$\begingroup\$ @VilmantasBaranauskas Thanks! I always forget about that :) It's tempting to use 4e9 and 1e-9 instead, but that takes quite a while... \$\endgroup\$ – Geobits Mar 16 '15 at 13:38
  • \$\begingroup\$ Protip: when golfing, you should actually reduce the bytes, not artificially increase them \$\endgroup\$ – Destructible Lemon Oct 28 '16 at 2:13
3
\$\begingroup\$

Javascript: 62 Bytes

for(r=Math.random,t=c=8e4;t--;c-=r()**2+r()**2|0);alert(c/2e4)

I used the previous (now deleted) javascript answer and shaved 5 bytes.

\$\endgroup\$
  • \$\begingroup\$ You could link to cfern's answer to properly give credit. \$\endgroup\$ – Jonathan Frech Sep 30 '18 at 23:57
  • \$\begingroup\$ Your answer appears to be a snippet which is disallowed I/O. Please either fix or delete your post. \$\endgroup\$ – Jonathan Frech Oct 1 '18 at 3:08
  • \$\begingroup\$ Sorry, I'm new I didn't know how to put the link to the previous solution which now appears have been deleted. Regarding the snippet: I completely agree, but that was the code of the previous javascript solution which I also think it was invalid that reason. I modified mine to be a program. \$\endgroup\$ – Guzman Tierno Oct 2 '18 at 12:35
  • \$\begingroup\$ Yes; the previous answer was deleted as it was invalid -- I saw your answer before I recommended deletion, thus the comment. +1 for submitting a valid answer; welcome to PPCG! \$\endgroup\$ – Jonathan Frech Oct 2 '18 at 15:54
2
\$\begingroup\$

GolfScript (34 chars)

0{^3?^rand.*^.*+/+}2000:^*`1/('.'@

Online demo

This uses fixed point because GS doesn't really have floating point. It slightly abuses the use of fixed point, so if you want to change the iteration count make sure that it's twice a power of ten.

Credit to xnor for the particular Monte Carlo method employed.

\$\endgroup\$
2
\$\begingroup\$

Python 2, 90 85 81 bytes

from random import*;r=random;print sum(4.for i in[0]*9**7if r()**2+r()**2<1)/9**7

returns 3.14120037157 for example. The sample count is 4782969 (9^7). You can get a better pi with 9^9 but you will have to be patient.

\$\endgroup\$
  • \$\begingroup\$ You can save 3 by replacing range(9**7) with [0]*9**7 or something, since you don't use i. And the list isn't too long to run into memory issues. \$\endgroup\$ – Sp3000 Mar 15 '15 at 0:20
  • \$\begingroup\$ Thanks. I wanted to get rid of range() but I had completely forgotten that trick. \$\endgroup\$ – Logic Knight Mar 15 '15 at 6:26
  • \$\begingroup\$ I have a feeling [0]9**7 isn't valid syntax. \$\endgroup\$ – seequ Mar 15 '15 at 13:57
  • \$\begingroup\$ You are right. I have re-attached the lost asterix (it was under my desk). \$\endgroup\$ – Logic Knight Mar 15 '15 at 14:51
2
\$\begingroup\$

Ruby, 39 bytes

p (1..8e5).count{rand**2+rand**2<1}/2e5

One of the highlight is that this one is able to use 8e5 notation, which makes it extendable up to ~8e9 samples in the same program byte count.

\$\endgroup\$
2
\$\begingroup\$

Perl 6, 33 bytes

{4*sum((1>rand²+rand²)xx$_)/$_}

Try it online!

This is a function that takes the number of samples as an argument.

\$\endgroup\$
1
\$\begingroup\$

Scala, 87 77 66 bytes

def s=math.pow(math.random,2);Seq.fill(1000)(s+s).count(_<1)/250d
\$\endgroup\$
  • \$\begingroup\$ If you replace 1000 with 8000 and 250d with 2e4 you both save a byte and increase the number of samples by a factor of 8. \$\endgroup\$ – Dave Swartz Mar 15 '15 at 13:35
1
\$\begingroup\$

Pure Bash, 65 bytes

for((;i++<$1*4;a+=RANDOM**2+RANDOM**2<32767**2));{ :;}
echo $a/$1

Takes a single command-line parameter which is multiplied by 4 to give the number of samples. Bash arithmetic is integer-only, so a rational is output. This may be piped to bc -l for the final division:

$ ./montepi.sh 10000
31477/10000
$ ./montepi.sh 10000|bc -l
3.13410000000000000000
$ 
\$\endgroup\$
1
\$\begingroup\$

Joe, 20 19 bytes

Note: this answer is non-competing, because version 0.1.2, which added randomness, was released after this challenge.

Named function F:

:%$,(4*/+1>/+*,?2~;

Unnamed function:

%$,(4*/+1>/+*,?2~;)

These both take the sample count as an argument and return the result. How do they work?

%$,(4*/+1>/+*,?2~;)
   (4*/+1>/+*,?2~;) defines a chain, where functions are called right-to-left
               2~;  appends 2 to the argument, giving [x, 2]
              ?     create a table of random values from 0 to 1 with that shape
            *,      take square of every value
          /+         sum rows, giving a list of (x**2+y**2) values
        1>           check if a value is less than 1, per atom
      /+             sum the results
    4*               multiply by four
%$,                  divide the result by the original parameter

Example runs:

   :%$,(4*/+1>/+*,?2~;
   F400000
3.14154
   F400000
3.14302
\$\endgroup\$
1
\$\begingroup\$

dc, 59 characters (whitespace is ignored)

[? 2^ ? 2^ + 1>i]su
[lx 1+ sx]si
[lu x lm 1+ d sm ln>z]sz

5k
?sn
lzx
lx ln / 4* p
q

I tested this on Plan 9 and OpenBSD, so I imagine it will work on Linux (GNU?) dc.

Explanation by line:

  1. Stores code to [read and square two floats; execute register i if 1 is greater than the sum of their squares] in register u.
  2. Stores code to [increment register x by 1] in register i.
  3. Stores code to [execute register u, increment register m, and then execute register z if register m is greater than register n] in register z.
  4. Set the scale to 5 decimal points.

  5. Read the number of points to sample from the first line of input.
  6. Execute register z.
  7. Divide register x (the number of hits) by register n (the number of points), multiply the result by 4, and print.
  8. Quit.

However, I cheated:

The program needs a supply of random floats between 0 and 1.

/* frand.c */
#include <u.h>
#include <libc.h>

void
main(void)
{
    srand(time(0));

    for(;;)
        print("%f\n", frand());
}

Usage:

#!/bin/rc
# runpi <number of samples>

{ echo $1; frand } | dc pi.dc

Test run:

% runpi 10000
3.14840

Now with less cheating (100 bytes)

Someone pointed out that I could include a simple prng.
http://en.wikipedia.org/wiki/RANDU

[lrx2^lrx2^+1>i]su[lx1+sx]si[luxlm1+dsmln>z]sz[0kls65539*2 31^%dsslkk2 31^/]sr?sn5dksk1sslzxlxlm/4*p

Ungolfed

[
Registers:
u - routine : execute i if sum of squares less than 1
i - routine : increment register x
z - routine : iterator - execute u while n > m++
r - routine : RANDU PRNG
m - variable: number of samples
x - variable: number of samples inside circle
s - variable: seed for r
k - variable: scale for division
n - variable: number of iterations (user input)
]c
[lrx 2^ lrx 2^ + 1>i]su
[lx 1+ sx]si
[lu x lm 1+ d sm ln>z]sz
[0k ls 65539 * 2 31^ % d ss lkk 2 31 ^ /]sr
? sn
5dksk
1 ss
lzx
lx lm / 4*
p

Test run:

$ echo 10000 | dc pigolf.dc
3.13640
\$\endgroup\$
1
\$\begingroup\$

Pyth, 19

c*4sm<sm^OQ2 2*QQQQ

Give the desired number of iterations as input.

Demonstration

Since Pyth doesn't have a "Random floating number" function, I had to improvise. The program choose two random positive integers less than the input, squares, sums, and compared to the input squared. This performed a number of times equal to the input, then the result is multiplied by 4 and divided by the input.

In related news, I will be adding a random floating point number operation to Pyth shortly. This program does not use that feature, however.


If we interpret "The result may be returned or printed as a floating point, fixed point or rational number." liberally, then printing the numerator and denominator of the resulting fraction should be sufficient. In that case:

Pyth, 18

*4sm<sm^OQ2 2*QQQQ

This is an identical program, with the floating point division operation (c) removed.

\$\endgroup\$
1
\$\begingroup\$

Julia, 37 bytes

4mean(1-floor(sum(rand(4^8,2).^2,2)))

The number of samples is 65536 (=4^8).

A sligthly longer variant: a function with number of samples s as the only argument:

s->4mean(1-floor(sum(rand(s,2).^2,2)))
\$\endgroup\$
1
\$\begingroup\$

C, 130 bytes

#include<stdlib.h>f(){double x,y,c=0;for(int i=0;i<8e6;++i)x=rand(),y=rand(),c+=x*x+y*y<1.0*RAND_MAX*RAND_MAX;printf("%f",c/2e6);}

Ungolfed:

#include <stdlib.h>
f(){
 double x,y,c=0;
 for(int i=0; i<8e6; ++i) x=rand(), y=rand(), c+=x*x+y*y<1.0*RAND_MAX*RAND_MAX;
 printf("%f",c/2e6);
}
\$\endgroup\$
  • \$\begingroup\$ of course, you should still probably post the version without the whitespace (keep the current version with the header "ungolfed/with whitespace" or something) \$\endgroup\$ – Destructible Lemon Oct 28 '16 at 0:46
  • \$\begingroup\$ @DestructibleWatermelon done! \$\endgroup\$ – Karl Napf Oct 28 '16 at 1:33
  • \$\begingroup\$ The solution doesn't work in GCC without a newline before f(). What compiler did you use? See tio.run/##Pc49C4JAHIDx3U9xGMG9ZdYgwWkgtNbQ1BZ6L/UHO8M07hA/… \$\endgroup\$ – eush77 Oct 18 '18 at 4:04
  • \$\begingroup\$ 101 bytes \$\endgroup\$ – ceilingcat Mar 21 at 16:59
1
\$\begingroup\$

Actually, 14 bytes (non-competing)

`G²G²+1>`nkæ4*

Try it online!

This solution is non-competing because the language post-dates the challenge. The number of samples is given as input (rather than hard-coded).

Explanation:

`G²G²+1>`nkæ4*
`G²G²+1>`n      do the following N times:
 G²G²+            rand()**2 + rand()**2
      1>          is 1 greater?
          kæ    mean of results
            4*  multiply by 4
\$\endgroup\$
  • 2
    \$\begingroup\$ Why the downvote? \$\endgroup\$ – Destructible Lemon Dec 6 '16 at 7:12
1
\$\begingroup\$

Racket 63 bytes

Using method of R language answer by @Matt :

(/(for/sum((i n))(define a(/(random 11)10))(/ 4(+ 1(* a a))))n)

Ungolfed:

(define(f n)
   (/
    (for/sum ((i n))
      (define a (/(random 11)10))
      (/ 4(+ 1(* a a))))
    n))

Testing:

(f 10000)

Output (fraction):

3 31491308966059784/243801776017028125

As decimal:

(exact->inexact(f 10000))

3.13583200307849
\$\endgroup\$
1
\$\begingroup\$

Fortran (GFortran), 84 83 bytes

CALL SRAND(0)
DO I=1,4E3
X=RAND()
Y=RAND()
IF(X*X+Y*Y<1)A=A+1E-3
ENDDO
PRINT*,A
END

Try it online!

This code is very bad wrote. It will fail if gfortran decide to initialize variable A with other value then 0 (which occurs 50% of the compilations, approximately) and, if A is initialized as 0, it will always generate the same random sequence for the given seed. Then, the same value for Pi is printed always.

This is a much better program:

Fortran (GFortran), 100 99 bytes

A=0
DO I=1,4E3
CALL RANDOM_NUMBER(X)
CALL RANDOM_NUMBER(Y)
IF(X*X+Y*Y<1)A=A+1E-3
ENDDO
PRINT*,A
END

Try it online!

(One byte saved in each version; thanks Penguino).

\$\endgroup\$
  • 1
    \$\begingroup\$ In each version you can save a byte by changing 'DO I=1,1E3' to 'DO I=1,4E3', changing 'A=A+1' to 'A=A+1E-3', and changing 'PRINT*,A/250' to 'PRINT*,A' \$\endgroup\$ – Penguino Apr 2 '18 at 22:14
  • \$\begingroup\$ Yes, you are sure! Thank for the suggestion! \$\endgroup\$ – rafa11111 Apr 2 '18 at 22:24
1
\$\begingroup\$

Japt, 26 or 18 bytes

o r_+ÂMhMr p +Mr p <1Ã*4/U

Try it online!

Analogous to Optimizer's answer, mainly just trying to learn Japt.
Takes the number of iterations to run for as the implicit input U.

o                           Take the input and turn it into a range [0, U),
                            essentially a cheap way to get a large array.
  r_                        Reduce it with the default initial value of 0.
    +Â                      On each iteration, add one if
      MhMr p +Mr p          the hypotenuse of a random [0,1)x[0,1) right triangle
                   <1       is smaller than one.
                     Ã*4/U  Multiply the whole result by four and divide by input.

If 1/(1+x^2) is allowed (instead of two separate randoms), then we can achieve 18 bytes with the same logic.

o r_Ä/(1+Mr pÃ*4/U
\$\endgroup\$
  • 1
    \$\begingroup\$ You can save a few bytes by letting Mh calculate the hypotenuse rather than doing it yourself ;-) Also, you can use x to take the sum of an array, rather than reducing by addition: o x@MhMr Mr)<1Ã*4/U \$\endgroup\$ – ETHproductions Apr 6 '18 at 14:32
  • \$\begingroup\$ @ETHproductions Neat, I didn't know you can use Mh like that, thanks! Your two-random answer is nearly as short as my answer with only one random, that's pretty cool. I'll keep x in mind, I tend to use reduction a lot when trying to golf stuff, so this will come in very handy. \$\endgroup\$ – Nit Apr 6 '18 at 14:44
1
\$\begingroup\$

F#, 149 bytes

open System;
let r=new Random()
let q()=
 let b=r.NextDouble()
 b*b
let m(s:float)=(s-Seq.sumBy(fun x->q()+q()|>Math.Sqrt|>Math.Floor)[1.0..s])*4.0/s

Try it online!

As far as I can make out, to do this kind of running total in F# it's shorter to create an array of numbers and use the Seq.sumBy method than use a for..to..do block.

What this code does it that it creates a collection of floating-point numbers from 1 to s, performs the function fun x->... for the number of elements in the collection, and sums the result. There are s elements in the collection, so the random test is done s times. The actual numbers in the collection are ignored (fun x->, but x is not used).

It also means that the application has to first create and fill the array, and then iterate over it. So it's probably twice as slow as a for..to..do loop. And with the array creation memory usage is in the region of O(f**k)!

For the actual test itself, instead of using an if then else statement what it does is it calculates the distance (q()+q()|>Math.Sqrt) and rounds it down with Math.Floor. If the distance is within the circle, it'll be rounded down to 0. If the distance is outside the circle it'll be rounded down to 1. The Seq.sumBy method will then total these results.

Note then that what Seq.sumBy has totalled is not the points inside the circle, but the points outside it. So for the result it takes s (our sample size) and subtracts the total from it.

It also appears that taking a sample size as a parameter is shorter than hard-coding the value. So I am cheating a little bit...

\$\endgroup\$
1
\$\begingroup\$

Haskell, 116 114 110 96 bytes

d=8^9
g[a,b]=sum[4|a*a+b*b<d*d]
p n=(sum.take(floor n)$g<$>iterate((\x->mod(9*x+1)d)<$>)[0,6])/n

Because dealing with import System.Random; r=randoms(mkStdGen 2) would take too many precious bytes, I generate an infinite list of random numbers with the linear congruential generator that some say is almost cryptographically strong: x↦x*9+1 mod 8^9, which by the Hull-Dobell Theorem has the full period of 8^9.

g yields 4 if the random number point is inside the circle for pairs of random numbers in [0..8^9-1] because this eliminates a multiplication in the formula used.

Usage:

> p 100000
3.14208

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Perl 5, 34 bytes

$_=$a/map$a+=4/(1+(rand)**2),1..$_

The number of samples is taken from stdin. Requires -p.

Works because:

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.