5 ms·
Thorough work. Going back to the premise, I want to offer an alternative viewpoint by asking whether, in the case of binary trees implemented by arrays, “intege
by anyfoo 7y ago
Thorough work. Going back to the premise, I want to offer an alternative viewpoint by asking whether, in the case of binary trees implemented by arrays, “integer division by 2” of the array index is necessarily the best interpretation of what you are trying to do here?
Instead, you can also see the array index as a bit string, where every bit tells you which path to go down, left or right. In that case, “shifting right by one bit” moves you up to the parent. “Shifting left” moves you down to the left child. Flipping one bit flips you over to the other child. Bit wise operations indeed seem more natural with that interpretation.
A lot of “power of 2” multiplication/division has similar interpretations. For example, when walking page tables, you could see walking down the levels as “dividing by the size of the granule”, or simply as “shifting right to select the index on that level”.
No contest on anything where the power of 2 is coincidence, i.e. for non “computery” things where there is no such underlying structure.
- yiyus 7y agoI had a slightly similar experience at work. We deal a lot with angles and binary angles are often the most efficient representation. Many colleagues find it annoying because they insist on converting every binary angle to radian or degrees, but if you actually interpret the bits as successive divisions of a circumference, I actually find the binary representation way more intuitive than a floating point number.
- a1369209993 7y ago> they insist on converting every binary angle to [] degrees Bit of hypocrisy there, since degrees are literally the same thing, just with 360 sectors rather than (say) 256. Though the extra factors of 3 and 5 are sometimes useful.
- yiyus 7y agoThe point is to not think of the bits as the representation of a decimal number. For example, if I need to know in which quadrant an angle is, I just need to look at the first two bits, independently of the precision (which we change just shifting and truncating). But I do not mind if 90 degrees are equal to 64 or 1073741824 "sectors". I think this is another good example where a binary representation (and a shift) can be a more natural way to approach the problem.
- pdehaan 7y agoNot just more natural, it also lends itself to better accuracy and/or efficiency in some cases too. As a quick example, if you're writing a numerical approximation or even just a LUT for sin(x), you can get away with only approximating/storing values for a reduced range by using some bit twiddling. The top bit becomes sign of output if you XOR it out first, the next bit lets you take advantage of sin(pi/2-x) = sin(x+pi/2) to half the input range again, eek out symmetry for the next bit and you can nearly approximate sin(x) as a linear function for some use cases.
- slavik81 7y agoThat method is exactly equivalent to using revolutions as the unit with a fixed-point numeric representation. Maybe your skeptical colleagues would find that perspective more palatable?
- yiyus 7y agoThat's some good advice. Unfortunately, most of the people I work with do not have a computer science background (they are materials scientists and mechanical engineers), so they are not familiarized with fixed-point arithmetic neither.