Has there ever been an algorithm invented that improved performance so much that existing hardware went from Unable to do the thing to Easily able to do the thing?
@WomanCorn Some of the advent-of-code answers show how using naive solution can take until the heat death of the universe but a clever algorithm will have the answer in seconds. I don't have any specific examples, but know that has frequently been the case. https://adventofcode.com/ (discussions of such things are usually on the linked subreddit)
@WomanCorn leap motion's hand tracker went from unusable to magic, all thanks to software updates
@WomanCorn Don't know about invented, but I've definitely rewritten code that was unusable slow and gotten 80x improvement in performance and actually beat the requirements. Didn't use any new algos, just normal ones I knew from 2nd year Uni that the original author apparently didn't know :)
@WomanCorn Gradient descent and backpropogation are good examples. Prior to them, we were just sampling vectors.
Similarly, lots of stuff in linear algebra liibraries. In particular, stuff which allows you to find things like eigendecompositions, singular values, and other features of linear maps without ever explicitly representing the matrix in its entirety. See the use-cases of Scipy's linear operator.
@WomanCorn Mathematics and my brain :)
@WomanCorn The SIKE break took SIKE from "cannot be broken with all the computing in the world" to "a laptop, one core, one hour" https://www.quantamagazine.org/post-quantum-cryptography-scheme-is-cracked-on-a-laptop-20220824/