3 ms·
> Brains win again over brawn: a well-designed, mathematically knowledgeable algorithm beats brute force! But it didn't, though, did it. Brute force got an ans
by barrkel 6y ago
> Brains win again over brawn: a well-designed, mathematically knowledgeable algorithm beats brute force!
But it didn't, though, did it. Brute force got an answer before brains found the smarter way.
It's great that the well-designed, math knowledgeable algorithm beats brute force, but it takes time to design something well, and to gain the knowledge, if it even exists, which is not a guaranteed prior. In the meantime, your quickly written brute force approach can be making progress.
IMO always try brute force first if there isn't a fairly obvious alternative. Surprisingly often, brute force is enough.
- benchaney 6y agoThat seems highly questionable. Given the complexity of his brute force algorithm, it was probably significantly more complex, and required more development time than the more elegant solution. The only reason the brute force got its answer first, was because it was the first thing he tried. That’s hardly an advantage of the approach.
- rlonn 6y agoIf you know how to do something, it is usually a lot faster to do it that way, than go looking for alternative solutions. The mantra of highly productive people: Start where you are. Use what you have. Do what you can.
- benchaney 6y agoThis is what I found doubtful. Generally implementing and debugging complex solutions is very time consuming and self education is very efficient.
- barrkel 6y agoWhat you're missing is the discovery time of the elegant solution, and the knowledge required to know that it may exist.
- benchaney 6y agoI’m not missing anything. The time spent to properly understand your problem is generally quite small, and pays itself back many times over.
- svat 6y agoAs they say, “A couple of months in the laboratory can frequently save a couple of hours in the library.” Or in this case, a thousand-plus hours of computer time saved a few minutes of looking it up (https://en.wikipedia.org/w/index.php?title=Prime_number&oldid=958581307#Number_of_primes_below_a_given_bound https://en.wikipedia.org/w/index.php?title=Prime_number&oldi...) or asking a mathematician.
- rlonn 6y agoand was that entry available on Wikipedia in 1994?
- svat 6y agoObviously Wikipedia didn't exist in 1994; I only gave the link for someone who is actually interested in looking it up today. A paper clearly explaining how to compute π(x) (I was just reading it) had come out in 1985: https://www.ams.org/journals/mcom/1985-44-170/S0025-5718-1985-0777285-5/S0025-5718-1985-0777285-5.pdf https://www.ams.org/journals/mcom/1985-44-170/S0025-5718-198...
- barrkel 6y agoWhere would the average bloke in the street go to find that in 1994? And where would they get that knowledge? (I mean, these days, the first thing you'd do is Google, the second thing is ask on SO or similar. You'd do this before even thinking about coding something yourself. So the bar to jumping to brute force has shifted somewhat.)
- gmfawcett 6y ago(I'd love to live in a town where the average bloke in the street was interested in fast algorithms for computing π(x), that would be a neat place!) You'd seek out a mathematician, or visit a university library and ask for the maths librarian. If you didn't know about those resources, you'd go to your public library, and hopefully a librarian would point you in the right direction. All of these search algorithms still work today. :)