4 ms·
I sometimes have difficulty finding efficient algorithms for specific tasks like this. Any advice on becoming better at finding efficient algorithms?
by Zamicol 5y ago
I sometimes have difficulty finding efficient algorithms for specific tasks like this. Any advice on becoming better at finding efficient algorithms?
- klodolph 5y agoI don't have any tips. Micro-optimization at this level often requires creative leaps, and proving that they work can be tricky (although for 32-bit integers, you can just iterate over all of them to validate). There are web pages with "bit-twiddling hacks" (https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html), and sometimes you can find a solution for your problem with a superoptimizer (if you care enough).
- knuthsat 5y agoOne other way to prove these algorithms is by writing them in z3 prover. You write a simple one that is 100% correct and then you prove equality for your optimized one or find an example that will show inequality.
- chrisseaton 5y agoA great thing about a monadic operation that takes a 32-bit integer, like this one, is that you can also just exhaustively test it in reasonable time!
- Dylan16807 5y agoToday I learned "monadic" has two significantly different meanings in the realm of programming. I'm only familiar with using "unary" to mean single-parameter.
- Filligree 5y agoNah, they’re pretty much the same meaning.
- Dylan16807 5y agoA monad, derived from monoid, means multiple very specific things completely unrelated to the other definition of "single parameter". And the etymology is basically a coincidence because "mono" got used in different places, isn't it?
- a1369209993 5y ago> []completely unrelated[] to the other definition of "single parameter". Actually, all monads are monadic functions/operators on their (usually type) parameter. Eg, 'list' is a monadic operator from element types to types of lists of those elements. It's completely different (AFAICT), and mostly unrelated, but it's not completely unrelated.
- freeone3000 5y agoLet's assume you've studied the well-known computer science tricks like divide and conquer, greedy algorithms, and the various tree searches, and that's insufficient, even after specializing for your reduced domain. (These will get you 90% of the way there 90% of the time, and usually that's good enough. Sometimes it's not.) For integer tricks like this, you'll want to look at number theory. Modular equivalence is particularly useful, but lots of things in that space are useful. However, there are a lot of other tricks that rely on geometric sequences, or geometry themselves, and other higher maths -- a lot of advances like this are simply connecting random theorum a to situation b, if you can envision the situation in the correct space.
- legends2k 5y agoHere's a gem called _Matters Computational_; a storehouse of many such tricks with proper categorization and index. https://www.jjj.de/fxt/fxtbook.pdf https://www.jjj.de/fxt/fxtbook.pdf
- __vim__ 5y agoThank you for this
- an1sotropy 5y agoholy moly this is awesome; thanks!
- kevin_thibedeau 5y agoBuy a copy of Hacker's Delight.