4 ms·

Hey, you finally made the leap to HN! Did you independently discover a lot of these things yourself or did you come across parts in books/papers? For me the can

by Jach 15y ago

Hey, you finally made the leap to HN! Did you independently discover a lot of these things yourself or did you come across parts in books/papers? For me the canonical example of deriving magic numbers is with the fast inverse square root trick (my favorite paper on it is http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf ) but I haven't seen many other instances... I haven't gone nearly far enough yet but I like getting pointed suggestions. There were some recent submissions here about related topics like space-filling curves and secret sharing that I've looked at before. When I started looking into abstract algebra and came across finite fields I sort of laughed at the Wikipedia page mentioning right at the beginning "Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, coding theory and Quantum error correction" with each topic being linked. It's a fun way to procrastinate. If your engine isn't part of some secret sauce I think it would be neat to study it. Unless you know of an already existing open source equivalent that's not hidden away in the corners of something like GCC?

jandrewrogers 15y ago
I found most of them in code and on the 'net but came up with a couple myself. When I started looking at bit interleaving some years back, I found a few examples for 2- and 3-dimensions but not much explanation. If you step through the algorithm and label every bit to watch how they move, it starts to become obvious what is going on. This was how I learned. The constants mask individual bits so that the sum of the shifts applied to a bit equals the total shift. If a bit needs to be shifted 5 bits to its final position, the mask is not applied to that bit for the ">>4" and ">>1" step. Consequently, constants and shifts for a particular transform do not have to be based on powers of two, just numbers where the sum of some subset of shifts matches every shift in the integer you are transforming. Once you know that, you can generate any distribution you need. However, Morton numbers take advantage of a property of their bit distributions where intermediate steps never corrupt a bit that is not going to be masked off anyway. This is not true for some other bit interleaving patterns. Extending it to arbitrary patterns requires two masking operations with another magic constant at each step which protects bits that would otherwise be destroyed in the simple Morton algorithm. Nothing like the transform engine I wrote is open source to the best of my knowledge. There is no reason I could not open source it, I just haven't. It is pretty efficient in that it can do a number of reductions and simplifications to the minimum number of steps and constants required to produce an n-dimensional interleaved result. For irregular patterns, you end up with quite a few no-op steps that can be eliminated; for regular patterns you can reuse steps, saving memory. I'll probably write it up and put it on the web at some point.

by Jach 15y ago

jandrewrogers 15y ago

I found most of them in code and on the 'net but came up with a couple myself. When I started looking at bit interleaving some years back, I found a few examples for 2- and 3-dimensions but not much explanation. If you step through the algorithm and label every bit to watch how they move, it starts to become obvious what is going on. This was how I learned. The constants mask individual bits so that the sum of the shifts applied to a bit equals the total shift. If a bit needs to be shifted 5 bits to its final position, the mask is not applied to that bit for the ">>4" and ">>1" step. Consequently, constants and shifts for a particular transform do not have to be based on powers of two, just numbers where the sum of some subset of shifts matches every shift in the integer you are transforming. Once you know that, you can generate any distribution you need. However, Morton numbers take advantage of a property of their bit distributions where intermediate steps never corrupt a bit that is not going to be masked off anyway. This is not true for some other bit interleaving patterns. Extending it to arbitrary patterns requires two masking operations with another magic constant at each step which protects bits that would otherwise be destroyed in the simple Morton algorithm. Nothing like the transform engine I wrote is open source to the best of my knowledge. There is no reason I could not open source it, I just haven't. It is pretty efficient in that it can do a number of reductions and simplifications to the minimum number of steps and constants required to produce an n-dimensional interleaved result. For irregular patterns, you end up with quite a few no-op steps that can be eliminated; for regular patterns you can reuse steps, saving memory. I'll probably write it up and put it on the web at some point.