New book-sorting algorithm almost reaches perfection
https://www.quantamagazine.org/new-book-sorting-algorithm-almost-reaches-perfection-20250124/It was surprising to me too! But reflecting on it more closely, most performance isn't about "faster" in a literal sense of "more instructions run per time", but about carefully choosing how to do less work. The security property here being "history independence" is also in a way stating "we don't need to, and literally cannot, do any work that tracks history".
It's definitely an interesting approach to performance, essentially using cryptography as a contraint to prevent more work. What properties do we need, and what properties can we ignore? The question becomes if we MUST ignore this property cryptographically, how does that affect the process and the related performance?
It certainly feels like it may be a useful perspective, a rigorous approach to performance that may be a path to more improvements in key cases.
Apparently both of them are linked deep inside the article, perhaps Quanta can make it mandatory to list all the reference towards the end of the article, it will be very helpful for the readers.
[1] Nearly Optimal List Labeling:
https://arxiv.org/abs/2405.00807
[2] A sparse table implementation of priority queues:
For arrays in B-tree nodes, which is the main place where I have encountered this problem, I doubt it will be faster than just using `memmove()`, and for truly large arrays, it would be easier to use a B tree.
If that is the case, this joins a number of algorithms that are asymptotically faster than algorithms in use and paradoxically slower than them. Examples of such algorithms include all of the fast matrix multiplication algorithms, which are slower than good implementations of the the textbook O(n^3) algorithm (GEMM).
This is true! One of the things I find cool about big-O complexity using polynomial reference classes is that logarithms give you an infinitesimal value. Take that, "infinitesimals don't really exist" people!
Game: https://patorjk.com/games/subpixel-snake/ Code: https://github.com/patorjk/subpixel-snake
Resource for subpixel geometries: https://geometrian.com/resources/subpixelzoo/
Can you explain to them what you want them to now do?
I read the paper and I would like to say, it's confusing at best. But I'm hoping you can help out.