all fun projects at Olimex Ltd
22 Apr 2013 14 Comments
in wpc Tags: challenge, programming, weekend, wpc
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 🙂
 | adj on BC66 new firmware update fixes… |
 | VINCENZO LI VIGNI on Say Hello to Es-Ti-Em-Pai STMP… |
 | Juergen Pintaske on IchigoJam – Single ARM c… |
 | OLIMEX Ltd on IchigoJam – Single ARM c… |
 | ukscone on IchigoJam – Single ARM c… |
Apr 22, 2013 @ 15:57:06
3/4 of the solutions use Pi to approximate Pi, one could call that cheating 😉
Apr 22, 2013 @ 16:02:07
Yup this one really got me stumped 😦
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.
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
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 )
Apr 22, 2013 @ 16:44:08
no, there isn’t. forgot to push it. whatever. old version.
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.
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 😀
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 😉
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
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. 🙂
Apr 23, 2013 @ 23:33:31
http://en.wikipedia.org/wiki/Bhaskara_I%27s_sine_approximation_formula is much more fun than Taylor series 🙂
Apr 24, 2013 @ 17:24:57
It’s really very interesting. Thank you for sharing 🙂
Apr 25, 2013 @ 01:09:37
At least I achieved something then, svetlinzarev! Or rather, it is amazing what Bhaskara I achieved, and then centuries later Bhaskara II and the http://en.wikipedia.org/wiki/Kerala_school_of_astronomy_and_mathematics .
We all know the zero comes from India, but there is so much more.