3 ms·
> The math library for Bob Morris's variable-precision desk calculator used backward error analysis to determine the precision necessary at each step to attain
by londons_explore 7y ago
> The math library for Bob Morris's variable-precision desk calculator
used backward error analysis to determine the precision necessary at
each step to attain the user-specified precision of the result.
I wonder if compilers could do this today? If you can bound values for floating point operations, you might be able to replace them with fixed point equivalents and get a big speedup. You might also be able to replace them with ints or smaller floats if you can detect the result is rounded to an int.
CPU's also have the possibility to do this since they know (some of) the actual values at runtime, and could take shortcuts with floating point calculation in places where not needed for the result.
- pavlov 7y agoReplacing floats with fixed point isn’t usually a meaningful optimization on modern CPUs. The FPU runs in parallel to the integer units, so you can easily end up idling the FPU while the integer units are too busy doing both the math and the necessary state management (counters, pointer arithmetic etc.) This could make sense for SIMD however, but then the problem is getting the array data in the right format before the computation — if you’re converting from float to int and back within the loop, it destroys any performance gain.
- londons_explore 7y agoFixed point uses a lot less power though, and many use cases are effectively power limited rather than functional-unit limited, since if you really do fill all functional units on every cycle you'll soon need to throttle back your clock speed... Perhaps a good example of that is video encoding, which is mostly fixed point, despite it looking like a pretty close fit for floating point maths.
- pavlov 7y agoA very good point. My worldview of performance is highly biased towards “full steam ahead” desktop graphics. Video encoding is a bit of a special case though because the common algorithms are carefully designed for hardware acceleration. For most rendering, it doesn’t make sense to go out of your way to avoid the FPU.
- bloomer 7y agoThis isn’t a performance optimization but rather an accuracy optimization. Even if the requested output is a double (64-bits) the intermediate calculations often need to be done to higher precision to get fully accurate answers. Note that the desktop calculator on Android does the same analysis by using computable numbers. https://dl.acm.org/doi/10.1145/2911981 https://dl.acm.org/doi/10.1145/2911981 Is a nice overview.
- nullc 7y agoIt's also a performance optimization though, since otherwise would might instead just use 400 digits of precision (or whatever) all the time, and round just the output.
- bloomer 7y agoSomewhat, in that it doesn’t use more precision than needed, but the real issue is you can’t just pick some arbitrarily large precision and round at the end. For some calculations, even 400 digits during intermediate steps would not be enough due to catastrophic cancellation and you would need to go even higher precision to get the right answer. It really is about solving an accuracy issue and not an optimization. And determining that you are using sufficient precision to get an accurate answer is an extra cost, so it is always more expensive than just plowing ahead and calculating an inaccurate answer.
- nullc 7y agoPresumably there is a maximum precision or otherwise a seemingly innocuous calculation could run you out of memory.