Algorithms based on number base systems? [closed]

Question

I've noticed recently that there are a great many algorithms out there based in part or in whole on clever uses of numbers in creative bases. For example:

• Binomial heaps are based on binary numbers, and the more complex skew binomial heaps are based on skew binary numbers.
• Some algorithms for generating lexicographically ordered permutations are based on the factoradic number system.
• Tries can be thought of as trees that look at one digit of the string at a time, for an appropriate base.
• Huffman encoding trees are designed to have each edge in the tree encode a zero or one in some binary representation.
• Fibonacci coding is used in Fibonacci search and to invert certain types of logarithms.

My question is: what other algorithms are out there that use a clever number system as a key step of their intuition or proof?. I'm thinking about putting together a talk on the subject, so the more examples I have to draw from, the better.

Answer 1

Chris Okasaki has a very good chapter in his book Purely Functional Data Structures that discusses "Numerical Representations": essentially, take some representation of a number and convert it into a data structure. To give a flavor, here are the sections of that chapter:

1. Positional Number Systems
2. Binary Numbers (Binary Random-Access Lists, Zeroless Representations, Lazy Representations, Segmented Representations)
3. Skew Binary Numbers (Skew Binary Random Access Lists, Skew Binomial Heaps)
4. Trinary and Quaternary Numbers

Some of the best tricks, distilled:

• Distinguish between dense and sparse representations of numbers (usually you see this in matrices or graphs, but it's applicable to numbers too!)
• Redundant number systems (systems that have more than one representation of a number) are useful.
• If you arrange the first digit to be non-zero or use a zeroless representation, retrieving the head of the data structure can be efficient.
• Avoid cascading borrows (from taking the tail of the list) and carries (from consing onto the list) by segmenting the data structure

Here is also the reference list for that chapter:

• Guibas, McCreight, Plass and Roberts: A new representation for linear lists.
• Myers: An applicative random-access stack
• Carlsson, Munro, Poblete: An implicit binomial queue with constant insertion time.
• Kaplan, Tarjan: Purely functional lists with catenation via recursive slow-down.