A New Algorithm for Data Compression by Philip Gage 1994

In 1994, Philip Gage published A New Algorithm for Data Compression, introducing what later became known as arithmetic coding—a foundational idea that quietly reshaped how modern compression works. While the paper itself is compact, the implications are anything but: this work influenced everything from image and video codecs to how we think about probabilistic representations of data.

I’m hosting this paper here because some ideas age exceptionally well. In an era of AI, large language models, and probabilistic systems, Gage’s thinking feels newly relevant. Reading original work like this is a reminder that many of today’s “breakthroughs” are evolutions of ideas that were already remarkably clear decades ago. This is one of those papers worth slowing down for.