Zeroless Positional Number Representation and String Ordering
Raymond T. Boute · American Mathematical Monthly · 2000
Introduction. It is often suggested and perhaps generally believed that positional number representation critically depends on the availability of zero. We describe a simple system (henceforth called BS) that does not need zero and has the interesting property that the representation is unique, unlike the generally accepted system (AS) where leading zeros can be added without changing the value. Its importance here is in showing that AS is not the only self-evident solution, as unreflecting everyday usage might lead one to think. Studying such simple alternatives improves understanding of the standard system. The calculation rules are the same in both systems and even allow smooth mixing of representations in a combined system (CS). We explain how BS arose from the seemingly unrelated problem of numbering strings. In the formalization of BS, the concept of skew division captures the essential difference with AS, which is based on Euclid's theorem. In our presentation we adopt a formalism [5] based on the systematic use of functions and functionals that enhances calculational derivations, designing automated support, and writing related programs. It has often been observed that, in algebra and analysis, careful and appropriate notation has made calculations of an essentially formal nature so convenient that they are common practice [1], [10]. This has motivated efforts to develop such formalisms also for other areas, such as discrete mathematics [3], [5], [8], [11], [12]. We show how treating sequences (lists, strings, . . . ) as first-class functions facilitates formal reasoning about representation systems in general. We avoid ellipsis and unnecessary indexing by replacing them with appropriate well-defined operators. We adopt the notation x: S for the introduction (binding) of the variable x ranging over the set S, and restrict the use of E to set membership alone.