Algorithms based on number base systems?

 

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.

    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:

  • Positional Number Systems
  • Binary Numbers (Binary Random-Access Lists, Zeroless Representations, Lazy Representations, Segmented Representations)
  • Skew Binary Numbers (Skew Binary Random Access Lists, Skew Binomial Heaps)
  • 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.

    • "Ternary numbers can be used to convey self-similar structures like a Sierpinski Triangle or a Cantor set conveniently." source

    "Quaternary numbers are used in the representation of 2D Hilbert curves." source

    "The quater-imaginary numeral system was first proposed by Donald Knuth in 1955, in a submission to a high-school science talent search. It is a non-standard positional numeral system which uses the imaginary number 2i as its base. It is able to represent every complex number using only the digits 0, 1, 2, and 3." source

    "Roman numerals are a biquinary system." source

    "Senary may be considered useful in the study of prime numbers since all primes, when expressed in base-six, other than 2 and 3 have 1 or 5 as the final digit." source

    "Sexagesimal (base 60) is a numeral system with sixty as its base. It originated with the ancient Sumerians in the 3rd millennium BC, it was passed down to the ancient Babylonians, and it is still used — in a modified form — for measuring time, angles, and the geographic coordinates that are angles." source

    etc...

    This list is a good starting point.

    I read your question the other day, and today was faced with a problem: How do I generate all partitionings of a set? The solution that occurred to me, and that I used (maybe due to reading your question) was this:

    For a set with (n) elements, where I need (p) partitions, count through all (n) digit numbers in base (p).

    Each number corresponds to a partitioning. Each digit corresponds to an element in the set, and the value of the digit tells you which partition to put the element in.

    It's not amazing, but it's neat. It's complete, causes no redundancy, and uses arbitrary bases. The base you use depends on the specific partitioning problem.

    链接地址: http://www.djcxy.com/p/40012.html

    上一篇: 大O运行时间为不同的数据结构

    下一篇: 基于数字基础系统的算法？