6 ms·

> 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) > Tada! How

> 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) > Tada! 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?

marginalia_nu 3mo ago
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/ https://tunguska.sf.net/
- StilesCrisis 3mo ago
  Fixed point! Not floating. That's the whole trick.
  - marginalia_nu 3mo ago
    Ah, then it makes at least some sense.
Tepix 3mo ago
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)
zokier 3mo ago
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.
- marginalia_nu 3mo ago
  It's kinda remarkable this works given how base 2 and base 3 are incredibly poorly aligned and make for a kind of worst case scenario when it comes to division (e.g. 1/3 = 1/2 - 1/4 + 1/8 - 1/16 + 1/32 ... and 1/2 = 1/3 + 1/9 + 1/27 + 1/81 + ...)

marginalia_nu 3mo ago

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/ https://tunguska.sf.net/

StilesCrisis 3mo ago
Fixed point! Not floating. That's the whole trick.
- marginalia_nu 3mo ago
  Ah, then it makes at least some sense.

Tepix 3mo ago

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)

zokier 3mo ago

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.

marginalia_nu 3mo ago
It's kinda remarkable this works given how base 2 and base 3 are incredibly poorly aligned and make for a kind of worst case scenario when it comes to division (e.g. 1/3 = 1/2 - 1/4 + 1/8 - 1/16 + 1/32 ... and 1/2 = 1/3 + 1/9 + 1/27 + 1/81 + ...)