4 ms·
I wonder how hard it would be, given the detection algorithm, to fix this automatically. Seems like simulated annealing would be a pretty good fit, where you pe
by mistercow 14y ago
I wonder how hard it would be, given the detection algorithm, to fix this automatically. Seems like simulated annealing would be a pretty good fit, where you perturb the word spacing on each iteration and the energy function is the total river length. The fitness landscape is rich enough with good solutions that you should rarely need more than a few iterations to arrive at one.
Still, that's a pretty expensive fitness test, and I wonder if there's a more elegant and efficient approach than Monte Carlo methods.
- kordless 14y agoThanks for this. I just spent 30 minutes reading up on calculating pi with a simple Monte Carlo algo. Thinking about doing it d3.js...
- mistercow 14y agoIt's an entertaining exercise, especially when you watch your computer chew away for several minutes before telling you that π is probably somewhere around 3.26.
- graue 14y agoHuh? You should get as close as 3.14 in less than a second if your random number source is decent.
- mistercow 14y agoPerhaps. I may be misremembering, or may have been using a particularly crappy RNG when I last did it. It was a long time ago.
- Someone 14y agoHow long ago? How much faster is current hardware? If it was, say, a 4MHz machine, you both could be right.
- petercooper 14y agoJust for fun, and because I'd never done it before, I just threw together some Ruby to do this: https://gist.github.com/peterc/5019760 https://gist.github.com/peterc/5019760 It gets to 3.14 within a second, about 30 seconds to 3.1415.. and Ruby is surely doing this in 100x the time C or Java would. Update: Also did it for JavaScript - https://gist.github.com/peterc/5019804 https://gist.github.com/peterc/5019804
- mistercow 14y agoYou can optimize that JS code a lot by using the unit circle, limiting yourself to the first quadrant, and using multiplication instead of Math.pow(). Then you can make it branchless using a little bitwise trickery. The result is this: https://gist.github.com/osuushi/5022143 https://gist.github.com/osuushi/5022143 . OK, so I was going to just do the unit circle thing. Then I got stuck in optimization mode. God I miss performance graphics programming.
- mistercow 14y agoIt would have probably been on an 450 MHz G4, maybe 6-7 years ago, and if I had to guess, I'd say I probably did it in Python.
- kordless 14y agoI was wondering about this. Evidently the more random, the more accurate. Wacky!
- AndreasFrom 14y agoI did it in Clojure once[1]. It's quite fun, I recommend it as well.
- raverbashing 14y agoCalculating Pi with Monte Carlo is equivalent to calculating the Fibonacci series with the recursive formula. It's a nice example but almost useless in practice.