3 ms·
Limiting itself to reversible operations gives some mathematical niceties, but also locks out a lot of things. When I did something similar, I was thinking abo
by o11c 3y ago
Limiting itself to reversible operations gives some mathematical niceties, but also locks out a lot of things.
When I did something similar, I was thinking about perfect hashing, where the set of inputs is known ahead of time. The usual approach uses a constant array, but I wanted to - in particular, if the inputs are already small integers, if I could compact them further (obviously this is possible: hash -= hash > > gap_index). I sat down and wrote out a list of ... probably 100? ... primitive operations (some of which are admittedly redundant with each other, but which are useful thinking of separately). And then I got bored and never did anything with the project.
- mshroyer 3y ago> Limiting itself to reversible operations gives some mathematical niceties What are those niceties, why is a reversible operation desirable in this context?
- tyingq 3y ago"One of the important properties of an integer hash function is that it maps its inputs to outputs 1:1. In other words, there are no collisions. If there’s a collision, then some outputs aren’t possible, and the function isn’t making efficient use of its entropy. This is actually a lot easier than it sounds. As long as every n-bit integer operation used in the hash function is reversible, then the hash function has this property. An operation is reversible if, given its output, you can unambiguously compute its input." https://nullprogram.com/blog/2018/07/31/ https://nullprogram.com/blog/2018/07/31/
- jwilk 3y agoThe blog post discussed on HN: 2018: https://news.ycombinator.com/item?id=17659672 https://news.ycombinator.com/item?id=17659672 (14 comments) 2021: https://news.ycombinator.com/item?id=29117783 https://news.ycombinator.com/item?id=29117783 (1 comment)
- pyinstallwoes 3y agoXOR xor xor reversibility through cyclical permutations ?