4 ms·

A method which this article doesn't mention is stochastic rounding or probabilistic rounding. Rather than striving for exact values for every computation, we m

A method which this article doesn't mention is stochastic rounding or probabilistic rounding. Rather than striving for exact values for every computation, we make it so that the expected value is exact. For example, suppose our number system was restricted to the integers and we have incoming value 1.1, with stochastic rounding we'd round down to 1 90% of the time and 2 10% of the time giving an expected value of 1.1! Further reading: https://nhigham.com/2020/07/07/what-is-stochastic-rounding/ https://nhigham.com/2020/07/07/what-is-stochastic-rounding/

orlp 2y ago
Interesting, I haven't seen that before in the context of numerics. It is used all the time however in audio and image processing, where it is called dithering.
vlovich123 2y ago
Doesn't that require a call to generate a random number for every floating point number you encounter? That seems expensive...
- KMnO4 2y ago
  A lot of hardware has built in RNGs, but even using a software algorithm (eg Xorshift) is extremely inexpensive. Also, sometimes you’re not limited by processing speed, but by the destination data structure (eg quantized to integers). https://en.wikipedia.org/wiki/Xorshift https://en.wikipedia.org/wiki/Xorshift
  - vlovich123 2y ago
    I'm aware of fast RNGs, but even compared to HW floating point operations, I believe they're still more expensive than Khan summation. HW circuits maybe could do well. I see that most of the interest is around LLMs and doing quantized sums (gathering from the fact that Intel has shipped this in their accelerator), but this came up in the WiFi positioning code I was working on 10 years ago (we were using "classical" f64).
tzs 2y ago
It's not really related, but that reminds me of how some games handled slow moving objects on the Mattel Intellivision console. Your code that runs every frame to update the graphics logically wants to do something like this: X += Vx Y += Vy where (X, Y) is the location of the object at the start of the frame, and (Vx, Vy) is x and y velocities of the object in pixels/frame. To allow for velocities that aren't an integer number of pixels per frame and that are slower than 1 pixel per frame you'd want to actually store X in a fixed point format, say (Xi, Xf) where Xi is the integer part of the X position, and Xf is the fractional part times 256, so X = Xi + Xf/256. Similarly for Y. The object only actually moves on the screen when Xi or Yi changes. Similarly velocity would also be in that format: Vx = Vxi + Vxf/256, and similar for Vy. With that, the position update in your loop would be something like this: Xf += Vxf if that wrapped Xi += 1 Xi += Vxi and similar for Y. For each object you end up needing 8 bytes (1 byte for each of Xi, Xf, Yi, Yf, Vxi, Vxf, Vyi, Vyf). That doesn't sound like much but the Intellivision only had something like 240 bytes in the console available. (If you couldn't get your RAM requirements down to that it was possible to have extra RAM in the cartridge but that would raise the cost). So someone figured out that you didn't actually need to store Xf and Yf. Just generate then at random as needed! The loop then becomes something like this: rb = random_unsigned_byte() if Vxf + rb wraps Xi += 1 Xi += Vxi and similar for Y. That turns out to work quite reasonably. Essentially it is interpreting Vxf as meaning that the object has a Vxf/256 chance of crossing a pixel boundary on a given frame. Thinking of it that way then suggests getting rid of the addition of the random byte with a wrap check and just doing a compare instead: if Vxf > random_unsigned_byte() Xi += 1 Xi += Vxi and similar for Y. Net result: we've cut the RAM for storing position and velocity from 8 bytes per object to 6, at the cost of needing to generate 2 random bytes per object per frame.
- teo_zero 2y ago
  Interesting. I know this is a purely academic question as these constraints are something of the past, but was it really necessary to have 16 bits for the velocity? Was the ratio between the quickest and the slowest objects more than 256 times?
  - kevin_thibedeau 2y ago
magicalhippo 2y ago
Isn't this essentially what dithering in ADCs[1][2] is all about? [1]: https://www.allaboutcircuits.com/technical-articles/what-is-dithering-using-noise-dithering-for-eliminating-the-quantization-distortion/ https://www.allaboutcircuits.com/technical-articles/what-is-... [2]: https://www.analog.com/en/resources/analog-dialogue/articles/adc-input-noise.html https://www.analog.com/en/resources/analog-dialogue/articles...

orlp 2y ago

Interesting, I haven't seen that before in the context of numerics. It is used all the time however in audio and image processing, where it is called dithering.

vlovich123 2y ago

Doesn't that require a call to generate a random number for every floating point number you encounter? That seems expensive...

KMnO4 2y ago
A lot of hardware has built in RNGs, but even using a software algorithm (eg Xorshift) is extremely inexpensive. Also, sometimes you’re not limited by processing speed, but by the destination data structure (eg quantized to integers). https://en.wikipedia.org/wiki/Xorshift https://en.wikipedia.org/wiki/Xorshift
- vlovich123 2y ago
  I'm aware of fast RNGs, but even compared to HW floating point operations, I believe they're still more expensive than Khan summation. HW circuits maybe could do well. I see that most of the interest is around LLMs and doing quantized sums (gathering from the fact that Intel has shipped this in their accelerator), but this came up in the WiFi positioning code I was working on 10 years ago (we were using "classical" f64).

tzs 2y ago

It's not really related, but that reminds me of how some games handled slow moving objects on the Mattel Intellivision console. Your code that runs every frame to update the graphics logically wants to do something like this: X += Vx Y += Vy where (X, Y) is the location of the object at the start of the frame, and (Vx, Vy) is x and y velocities of the object in pixels/frame. To allow for velocities that aren't an integer number of pixels per frame and that are slower than 1 pixel per frame you'd want to actually store X in a fixed point format, say (Xi, Xf) where Xi is the integer part of the X position, and Xf is the fractional part times 256, so X = Xi + Xf/256. Similarly for Y. The object only actually moves on the screen when Xi or Yi changes. Similarly velocity would also be in that format: Vx = Vxi + Vxf/256, and similar for Vy. With that, the position update in your loop would be something like this: Xf += Vxf if that wrapped Xi += 1 Xi += Vxi and similar for Y. For each object you end up needing 8 bytes (1 byte for each of Xi, Xf, Yi, Yf, Vxi, Vxf, Vyi, Vyf). That doesn't sound like much but the Intellivision only had something like 240 bytes in the console available. (If you couldn't get your RAM requirements down to that it was possible to have extra RAM in the cartridge but that would raise the cost). So someone figured out that you didn't actually need to store Xf and Yf. Just generate then at random as needed! The loop then becomes something like this: rb = random_unsigned_byte() if Vxf + rb wraps Xi += 1 Xi += Vxi and similar for Y. That turns out to work quite reasonably. Essentially it is interpreting Vxf as meaning that the object has a Vxf/256 chance of crossing a pixel boundary on a given frame. Thinking of it that way then suggests getting rid of the addition of the random byte with a wrap check and just doing a compare instead: if Vxf > random_unsigned_byte() Xi += 1 Xi += Vxi and similar for Y. Net result: we've cut the RAM for storing position and velocity from 8 bytes per object to 6, at the cost of needing to generate 2 random bytes per object per frame.

teo_zero 2y ago
Interesting. I know this is a purely academic question as these constraints are something of the past, but was it really necessary to have 16 bits for the velocity? Was the ratio between the quickest and the slowest objects more than 256 times?
- kevin_thibedeau 2y ago

magicalhippo 2y ago

Isn't this essentially what dithering in ADCs[1][2] is all about? [1]: https://www.allaboutcircuits.com/technical-articles/what-is-dithering-using-noise-dithering-for-eliminating-the-quantization-distortion/ https://www.allaboutcircuits.com/technical-articles/what-is-... [2]: https://www.analog.com/en/resources/analog-dialogue/articles/adc-input-noise.html https://www.analog.com/en/resources/analog-dialogue/articles...