Weekend programming challenge issue #5 results


Image

The Monte Carlo approach for computing Pi constant seems to have confused lot of you as we got only 17 solutions πŸ™‚

Recap:

6 solutions in Python

4 solutions in C language

2 solutions in C++

1 Java

1 JavaScript

1 Prolog

1 Scala

1 Matlab

Scala solution seems shortest with 1 line code πŸ™‚

14 Comments (+add yours?)

  1. ventosus
    Apr 22, 2013 @ 15:57:06

    3/4 of the solutions use Pi to approximate Pi, one could call that cheating πŸ˜‰

    Reply

  2. nippius
    Apr 22, 2013 @ 16:02:07

    Yup this one really got me stumped 😦

    Reply

    • Dylan
      Apr 22, 2013 @ 19:34:45

      I know how you feel! My first attempt, using pi, looked like some of the entries but gave 2.3 as a result. Second attempt, before I gave up, gave 3.15 consistently. But that was false dawn: changed input parameters changed the value. (I was looking at lines of length between 0.99 and 1.01 using pythagorean hack for some bizarre reason).

      I enjoyed the challenge though despite being stumped by it! I’ll be busy next Saturday and Sunday again, so roll on, Friday!

      P.S. Friday’s circuit will be a flux capacitor.

      Reply

  3. luke4oxnet
    Apr 22, 2013 @ 16:19:43

    I didn’t find a way for long needle to compute Pi, without arcus sinus function, which uses Pi. For short needle Pi can be calculated without cheating. There are at least few ways to randomize the direction without Pi usage, I found good overview of the methods here: http://www.efg2.com/Lab/Mathematics/Buffon.htm

    Reply

    • turbinenreiter
      Apr 22, 2013 @ 16:42:05

      i just used degrees instead of radiants.
      or do i get something wrong?
      solution 2 is mine.
      (and there is a updated version on my github, using classes – https://github.com/turbinenreiter/weekendhack )

      Reply

    • svetlinzarev
      Apr 22, 2013 @ 20:23:42

      I cannot see the problem of using Pi in the process of generating random angles. You can use 123456 instead of Pi for example, but then some angles will be generated more frequently than others, yet it will still work.

      Reply

      • Emiliano Daddario
        Apr 22, 2013 @ 21:29:46

        This is more or less what I wrote before. The greater this arbitrary constant “const” is, the better the estimate, because what alters the probability is the fact that the remainder of the division const/Pi is not zero. So if this remainder is small with respect to const, it is negligible. You can’t assign const=infinity in most languages, so for example in Java you may choose Integer.MAX_VALUE (I just quickly tested it myself). Of course assigning const=Pi is more accurate than that, but someone called it cheating πŸ˜€

      • ventosus
        Apr 22, 2013 @ 23:29:44

        I totally agree and my initial version was exactly like that.
        BUT…
        I got curious on how the machine may compute the sinus in the first place, and I’ve learned that the programmers were not naive and took well care of the fact that sin has a periodicity of 2Pi, a mirror point at 0 & Pi and a mirror axis at Pi/2 & 3/2Pi. A given sinus algo most probably will just be annoyed if you throw a big number at it, as it has to shift it by a multiple of Pi to the range where its implementation is most efficient (e.g. [0,Pi/2]). Apart from the obvious Pi in the code, I’d bet Pi’s value or a fraction of it is hidden in the sinus implementation…

        here an example http://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/ieee754/dbl-64/s_sin.c;hb=HEAD

        P.s, I meant cheating in a strictly philosophical sense, e.g. using the result to calculate itself πŸ˜‰

      • svetlinzarev
        Apr 23, 2013 @ 15:59:32

        Sin(), cos()… and the other trigonometric f(x) are implemented using Taylor series πŸ™‚ So no Pi involved, but that’s rather slow. I recently found a very interesting topic about how trig. functions are implemented in Java: https://www.java.net//node/645530 and after some research I found that other languages (C for instance) also use hardware dependent code http://stackoverflow.com/questions/2284860/how-does-c-compute-sin-and-other-math-functions

  4. Emiliano Daddario
    Apr 22, 2013 @ 17:51:29

    Try to substitute a very large integer (ideally infinity) instead of Pi in my Scala code (and maybe in others’ code), and you’ll still have a quite good approximation of Pi in the result. So it’s not cheating. πŸ™‚

    Reply

  5. Dylan
    Apr 23, 2013 @ 23:33:31

    http://en.wikipedia.org/wiki/Bhaskara_I%27s_sine_approximation_formula is much more fun than Taylor series πŸ™‚

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: