4 ms·
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, y
by klodolph 5y ago
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 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.