tag:blogger.com,1999:blog-5246987755651065286.post4743630652093296816..comments2024-02-22T16:15:42.388-08:00Comments on cbloom rants: 05-07-09 - Integer Function Inversionscbloomhttp://www.blogger.com/profile/10714564834899413045noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-5246987755651065286.post-14552130558471043862009-05-16T07:24:00.000-07:002009-05-16T07:24:00.000-07:00Oh, and f : x |-> x^2 and any other analytic fu...Oh, and f : x |-> x^2 and any other analytic function that maps ints to ints is extra-nice in that regard since it guarantees that f^(-1) will always dequantize values back into the right bucket without any fudging around, provided the calculation is done exactly (or close enough to exact).ryghttps://www.blogger.com/profile/03031635656201499907noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-58112651133740058612009-05-16T07:17:00.000-07:002009-05-16T07:17:00.000-07:00Hm, say you want C : [0,n] -> [0,m] with C(x) &...Hm, say you want C : [0,n] -> [0,m] with C(x) >= C(x)+1.<br />Recasting this as a continuous problem: is there a unit interval remapper f : [0,1] -> [0,1] such that a) f' >= n/m everywhere (guarantees the C(x) >= C(x+1)) and b) both f and f^(-1) have "nice" analytic forms. There's more you need to ensure that f^(-1) always reconstructs the right value, but b) is already a pretty tough requirement.<br /><br />Scaled+translated exponential functions might work, but polynomials of higher order than quadratic are a bad idea. OTOH, the set of such functions f is convex, so once you have a few of them, you also have a whole spectrum inbetween.ryghttps://www.blogger.com/profile/03031635656201499907noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-57691855543830731092009-05-15T17:25:00.000-07:002009-05-15T17:25:00.000-07:00Yeah the first thing you describe is "lifting...Yeah the first thing you describe is "lifting". It's how we make the integer reversible rotations.<br /><br />The second bit is more interesting to me. For example<br /><br />x *= x;<br /><br />is obviously invertible in ints (for x >= 1).cbloomhttps://www.blogger.com/profile/10714564834899413045noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-92013769626347575642009-05-15T16:57:00.000-07:002009-05-15T16:57:00.000-07:00I was just thinking about invertible integer opera...I was just thinking about invertible integer operations for hashing, so I will brain dump everything I know of from that, but I don't think any of it is useful.<br /><br />It turns out that if you have multiple variables, then you can do all sorts of things where you update one variable from the others, and it's trivial to reverse:<br /><br /> foo += [...complicated-thing...]<br />or<br /> foo ^= [...complicated-thing...]<br /><br />e.g. like this:<br /><br /> a += b >> 5;<br /> b ^= a << 7;<br /> b -= (c << 4) * (a >> 11);<br /><br />can easily be reversed (by subtracting or re-xoring); if you have a large basic block full of instructions like this, you can just walk backward through them one at a time applying this logic.<br /><br />But, if "complicated-thing" involves *foo*, then all bets are off (and this is where cryptographic hashes go).<br /><br />Consider this operation:<br /><br /> x += (x << 1)<br /><br />This is obviously the same as 'x = x*3', so it's not surprising that it's invertible, but note the mismatch between the cost of computing it forward and the cost of computing it backward. Now consider this operation:<br /><br /> x ^= (x << 1)<br /><br />This can still be inverted; the bottom bit of x is the original value that it used to be; the next bit up, x1, can be computed as: x1_new = x0_old ^ x1_old, so x1_old = x1_new ^ x0_old. Then each successive bit can be computed the same way. But there's no close-formed way to compute it.<br /><br />And the thing is, it's not even a-priori obvious that 'x ^= x << 1' is a 1-to-1 function, nevermind how hard it turns out to be to invert.Anonymousnoreply@blogger.com