Hacker News Reader

Comment by Zamicol | Hacker News Reader

I sometimes have difficulty finding efficient algorithms for specific tasks like this. Any advice on becoming better at finding efficient algorithms?

View on HN

Here's a gem called _Matters Computational_; a storehouse of many such tricks with proper categorization and index.

https://www.jjj.de/fxt/fxtbook.pdf

holy moly this is awesome; thanks!

Thank you for this

I 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), and sometimes you can find a solution for your problem with a superoptimizer (if you care enough).

One 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.

A 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!

Today I learned "monadic" has two significantly different meanings in the realm of programming.

I'm only familiar with using "unary" to mean single-parameter.

Nah, they’re pretty much the same meaning.

A 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?

> []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.

Let'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.

Buy a copy of Hacker's Delight.

Reply on news.ycombinator.com