9 ms·
The article covers ways to obtain smaller error bounds, mainly for testing algorithm stability in practice. The methods proposed are very varied in nature: blo
by thxg 5y ago
The article covers ways to obtain smaller error bounds, mainly for testing algorithm stability in practice.
The methods proposed are very varied in nature: blocked algorithms, x87 80-bit arithmetic, AVX2/ARMv8-A fused multiply-add (FMA) operations, and probabilistic bounds.
While the article is otherwise very good, I am unsure about one of those in 2021: 80-bit arithmetic. The corresponding x87 instructions are deprecated by Intel, and their performance is disastrous. For example, the complex algorithms implemented in software by glibc to compute transcendental functions (sin, cos, exp, ...) are faster and more accurate than their single instruction x87 FPU counterparts (FSIN, FCOS, ...)!
I would be very curious to see, in a few algorithms, a comparison of x87 arithmetic with double-doubles and even low-precision MPFR. MPFR, by the way, may have its place here if we're talking about sacrificing some performance for higher precision.
- gpderetta 5y agoThe trascendental instructions are slow and have low accuracy, but the "normal" x87 fp ops are still fast (except for the lack of vectorization).
- thxg 5y agoYou're right, I didn't know that. In a quick "long double" vs "double" microbenchmark, I see a negligible penalty for additions and comparisons, and 37% penalty when multiplications are involved.
- adgjlsfhk1 5y agoYeah. The problem with them is that using double-double based methods gives you 104 bits of precision that works with vectorization (and therefore is faster than x87).
- gpderetta 5y agoI assume double-double would be the emulated __float128 type in GCC (or hand written equivalent)? Can GCC vectorize it or it needs to be done by hand?
- snovv_crash 5y agoAgreed, I've seen better results from algorithmic approaches. For example, Takahashi for bounded-error on extremely large dot product. Depending on use case even doing a pseudo-Takahashi where you only merge the error back once every N iterations can unblock instruction-level parallelism letting the performance hit be only around 2x relative to naive dot products, but with still effectively the same guarantees.
- evancox100 5y agoI think they were only recommending x87 for a final summation