How Fast Are Algorithms Improve?

Algorithms
Source : medium

MIT scientists show, how briskly algorithms are improving across a broad range of examples, demonstrating their critical importance in advancing computing.

Algorithms are kind of like a parent to a computer. They tell the computer the way to make sense of information in order that they can, in turn, make something useful out of it.

The more-efficient the algorithm, less work the computer has got to do. For all of the technological progress in computing hardware and much debated lifespan of Moore’s Law, computer performance is merely one side of the picture.

Behind the scenes, a second trend is happening: Algorithms are being improved, so in-turn less computing power is required. While algorithmic efficiency may have less of a spotlight, you would definitely notice, if your trusty search engine suddenly became one-tenth as fast or if moving through big data-sets felt like wading through sludge.

This led scientists from MIT’s Computer Science & Artificial Intelligence Laboratory (CSAIL) to ask: How quickly do algorithms improve?

Existing data on this question were largely anecdotal, consisting of case-studies of particular algorithms that assumed to be representative of the broader scope. Faced with this dearth of evidence, team depart to crunch data from 57 textbooks & more than 1,110 research papers, to trace the history of when algorithms got better. Several research papers directly reported, how good new algorithms were and others needed to be re-constructed by the authors using “pseudocode,” shorthand versions of the algorithm that describe basic details.

In total, team looked at 113 “algorithm families,” sets of algorithms solving the same problem that had been highlighted as most crucial by computer science textbooks. For every of the 113, team re-constructed its history, tracking each time a new algorithm was proposed for the problem and making special-note of these that were more efficient.

Ranging in performance & separated by decades, ranging from the 1940s to now, team found a average of 8 algorithms per family, of which a couple improved its efficiency. To share this assembled database of knowledge, team also created Algorithm-Wiki.org.

The scientists charted, how quickly these families improved, that specialize in the most analyzed feature of the algorithms, how fast they might guarantee to solve the problem (in computer speak: “worst-case time complexity”). What emerged was enormous variability, but even important insights on how transformative algorithmic improvement has been for computer science.

For large computing problems, 43% of algorithm families had year on year improvements that were equal-to or larger than the much-touted gains from Moore’s Law. In 14% of problems, improvement to performance from algorithms greatly outpaced people who have come from improved hardware. The gains from algorithm improvement were particularly large for big-data problems, therefore the importance of these advancements has grown in recent decades.

The single biggest change that authors observed came when an algorithm family transitioned from exponential to polynomial complexity. The amount of effort it takes to solve an exponential problem is like sort of a person trying to guess a combination on a lock. If you simply have single 10-digit dial, task is very easy. With 4 dials like of a bicycle lock, it is hard enough that no one steals your bike, but still conceivable that you simply could try every combination. With 50, it is almost impossible, it might take too many steps. Problems that have exponential complexity are like that for computers: As they get bigger, they quickly outpace the ability of computer to handle them. Finding a polynomial algorithm often solves that, making it possible to-tackle problems in a way that no amount of hardware improvement can.

As rumblings of Moore’s Law coming to an end rapidly permeate global conversations, researchers say that computing users will increasingly got-to turn to areas like algorithms for performance improvements. The team says findings confirm that historically, gains from algorithms are enormous, therefore the potential is there. But if gains come from algorithms rather than hardware, they’ll look different. Hardware improvement from Moore’s Law happens smoothly over time and for algorithms gains come in steps that are usually large, but infrequent.

“This is that the first paper to show, how fast algorithms are improving across a broad range of examples,” says Neil Thompson, an MIT research scientist at the CSAIL and Sloan School of Management and senior-author on the new paper. “Through our analysis, we were able to say how many more tasks might be done using the same amount of computing-power after an algorithm improved. As problems increase to billions or trillions of data points, algorithmic improvement becomes substantially-more important than hardware improvement. In an era where environmental footprint of computing is increasingly worrisome, this is a way to improve businesses & other organizations without the downside.”

The paper is published in the Proceedings of the IEEE.