alt Hacker News> Fixed point numbers to the rescue!
> a diagram that shows that dividing 0x7F (127) by 243 and then multiplying by 256 results in 0x86 (134)
How... how does that help with anything?
> Now digits can be easily extracted from the top two bits of the resulting 10-bit number when multiplying this 8-bit byte by 3.
What? Why? How? This is supposed to be the most insightful part of the post, and it's literally just "Behold!" from that one proof of Pythagorean theorem. Could someone please elaborate it for a non-genius like me?
Replies
If it's any consolation, I spent like two years of my life immersed in this field[1] and can still recite powers of three in the same way most nerds can only tell you powers of two, yet I still can't follow this floating point black magic.
[1] behold my misspent youth: https://tunguska.sf.net/
I think the key insight here is that 243 is 100000 in base3. So dividing by 243 essentially converts any 5 digit base 3 number to [0,1) interval. Multiplying by 256 converts it to [0,256) interval which conveniently fits into a byte.
If your pack_number function builds the number up, the standard way to break it down is by extracting the least significant digit first using modulo and division. To get something that works well with SIMD we need a different approach. Instead of extracting the least significant digit from the bottom of an integer, we extract the most significant digit from the top of a fraction.
1. Convert to a fixed-point fraction: We scale our integer N into a fixed-point representation (e.g., using a 32-bit integer to represent the fraction). We do this by multiplying N by a precomputed reciprocal of 243.
2. Multiply by the base: Multiply the fraction by 3.
3. Extract: The integer portion of the result is your most significant trit.
4. Mask: Keep only the fractional remainder, and repeat.
The only operations here are multiplication, bitwise shift, and bitwise AND, i.e. perfectly suited for SIMD.
(in step 1 we replace the division with a multiplication by using the reciprocal. SIMD uses fixed-point integer arithmetic, not floating-point decimals)