> The question is, what might be some examples? What are some problems for which the time or space complexity of the best known solution has decreased over the last several decades to the point that the above statement would be true of them?
All trigonometric functions.
It is a common source of confusion that none of the modern SIMD instruction sets for x86 contain instructions for sine or cosine. The only instructions for them in the CPU are the FCOS and FSIN ones for the obsolete x87 FP mode. These should never be used, because the software implementations provided by your C library are both faster and more precise.
The reason the CPU instructions are worse than what you can write is that back when they were added to the CPU, the fastest known way of computing full-precision trigonometric functions in hardware was not fast enough for practical use. So instead, the instructions were implemented as approximations. Then, after some improvements in known algorithms, these approximations were improved to be somewhat better and faster. However, this caused compatibility issues because FSIN on a Pentium (or a 486? not sure) does not actually return same results as it does on a 386. Learning from this, the trigonometric functions in x87 are now forever frozen to their old, slow to compute and imprecise approximations.
However, since then a much more accurate and faster way to compute sine and cosine in software has been discovered, and every halfway decent language and math library now uses it.
All trigonometric functions.
It is a common source of confusion that none of the modern SIMD instruction sets for x86 contain instructions for sine or cosine. The only instructions for them in the CPU are the FCOS and FSIN ones for the obsolete x87 FP mode. These should never be used, because the software implementations provided by your C library are both faster and more precise.
The reason the CPU instructions are worse than what you can write is that back when they were added to the CPU, the fastest known way of computing full-precision trigonometric functions in hardware was not fast enough for practical use. So instead, the instructions were implemented as approximations. Then, after some improvements in known algorithms, these approximations were improved to be somewhat better and faster. However, this caused compatibility issues because FSIN on a Pentium (or a 486? not sure) does not actually return same results as it does on a 386. Learning from this, the trigonometric functions in x87 are now forever frozen to their old, slow to compute and imprecise approximations.
However, since then a much more accurate and faster way to compute sine and cosine in software has been discovered, and every halfway decent language and math library now uses it.