Signed-digit representation

Last updated

In mathematical notation for numbers, a signed-digit representation is a positional numeral system with a set of signed digits used to encode the integers.

Contents

Signed-digit representation can be used to accomplish fast addition of integers because it can eliminate chains of dependent carries. [1] In the binary numeral system, a special case signed-digit representation is the non-adjacent form , which can offer speed benefits with minimal space overhead.

History

Challenges in calculation stimulated early authors Colson (1726) and Cauchy (1840) to use signed-digit representation. The further step of replacing negated digits with new ones was suggested by Selling (1887) and Cajori (1928).

In 1928, Florian Cajori noted the recurring theme of signed digits, starting with Colson (1726) and Cauchy (1840). [2] In his book History of Mathematical Notations, Cajori titled the section "Negative numerals". [3] For completeness, Colson [4] uses examples and describes addition (pp. 163–4), multiplication (pp. 165–6) and division (pp. 170–1) using a table of multiples of the divisor. He explains the convenience of approximation by truncation in multiplication. Colson also devised an instrument (Counting Table) that calculated using signed digits.

Eduard Selling [5] advocated inverting the digits 1, 2, 3, 4, and 5 to indicate the negative sign. He also suggested snie, jes, jerd, reff, and niff as names to use vocally. Most of the other early sources used a bar over a digit to indicate a negative sign for it. Another German usage of signed-digits was described in 1902 in Klein's encyclopedia. [6]

Definition and properties

Digit set

Let be a finite set of numerical digits with cardinality (If , then the positional number system is trivial and only represents the trivial ring), with each digit denoted as for is known as the radix or number base . can be used for a signed-digit representation if it's associated with a unique function such that for all This function, is what rigorously and formally establishes how integer values are assigned to the symbols/glyphs in One benefit of this formalism is that the definition of "the integers" (however they may be defined) is not conflated with any particular system for writing/representing them; in this way, these two distinct (albeit closely related) concepts are kept separate.

can be partitioned into three distinct sets , , and , representing the positive, zero, and negative digits respectively, such that all digits satisfy , all digits satisfy and all digits satisfy . The cardinality of is , the cardinality of is , and the cardinality of is , giving the number of positive and negative digits respectively, such that .

Balanced form representations

Balanced form representations are representations where for every positive digit , there exist a corresponding negative digit such that . It follows that . Only odd bases can have balanced form representations, as otherwise has to be the opposite of itself and hence 0, but . In balanced form, the negative digits are usually denoted as positive digits with a bar over the digit, as for . For example, the digit set of balanced ternary would be with , , and . This convention is adopted in finite fields of odd prime order : [7]

Dual signed-digit representation

Every digit set has a dual digit set given by the inverse order of the digits with an isomorphism defined by . As a result, for any signed-digit representations of a number system ring constructed from with valuation , there exists a dual signed-digit representations of , , constructed from with valuation , and an isomorphism defined by , where is the additive inverse operator of . The digit set for balanced form representations is self-dual.

For integers

Given the digit set and function as defined above, let us define an integer endofunction as the following:

If the only periodic point of is the fixed point , then the set of all signed-digit representations of the integers using is given by the Kleene plus , the set of all finite concatenated strings of digits with at least one digit, with . Each signed-digit representation has a valuation

.

Examples include balanced ternary with digits .

Otherwise, if there exist a non-zero periodic point of , then there exist integers that are represented by an infinite number of non-zero digits in . Examples include the standard decimal numeral system with the digit set , which requires an infinite number of the digit to represent the additive inverse , as , and the positional numeral system with the digit set with , which requires an infinite number of the digit to represent the number , as .

For decimal fractions

If the integers can be represented by the Kleene plus , then the set of all signed-digit representations of the decimal fractions, or -adic rationals , is given by , the Cartesian product of the Kleene plus , the set of all finite concatenated strings of digits with at least one digit, the singleton consisting of the radix point ( or ), and the Kleene star , the set of all finite concatenated strings of digits , with . Each signed-digit representation has a valuation

For real numbers

If the integers can be represented by the Kleene plus , then the set of all signed-digit representations of the real numbers is given by , the Cartesian product of the Kleene plus , the set of all finite concatenated strings of digits with at least one digit, the singleton consisting of the radix point ( or ), and the Cantor space , the set of all infinite concatenated strings of digits , with . Each signed-digit representation has a valuation

.

The infinite series always converges to a finite real number.

For other number systems

All base- numerals can be represented as a subset of , the set of all doubly infinite sequences of digits in , where is the set of integers, and the ring of base- numerals is represented by the formal power series ring , the doubly infinite series

where for .

Integers modulo powers of b

The set of all signed-digit representations of the integers modulo , is given by the set , the set of all finite concatenated strings of digits of length , with . Each signed-digit representation has a valuation

Prüfer groups

A Prüfer group is the quotient group of the integers and the -adic rationals. The set of all signed-digit representations of the Prüfer group is given by the Kleene star , the set of all finite concatenated strings of digits , with . Each signed-digit representation has a valuation

Circle group

The circle group is the quotient group of the integers and the real numbers. The set of all signed-digit representations of the circle group is given by the Cantor space , the set of all right-infinite concatenated strings of digits . Each signed-digit representation has a valuation

The infinite series always converges.

b-adic integers

The set of all signed-digit representations of the -adic integers, is given by the Cantor space , the set of all left-infinite concatenated strings of digits . Each signed-digit representation has a valuation

b-adic solenoids

The set of all signed-digit representations of the -adic solenoids, is given by the Cantor space , the set of all doubly infinite concatenated strings of digits . Each signed-digit representation has a valuation

In written and spoken language

Indo-Aryan languages

The oral and written forms of numbers in the Indo-Aryan languages use a negative numeral (e.g., "un" in Hindi and Bengali, "un" or "unna" in Punjabi, "ekon" in Marathi) for the numbers between 11 and 90 that end with a nine. The numbers followed by their names are shown for Punjabi below (the prefix "ik" means "one"): [8]

Similarly, the Sesotho language utilizes negative numerals to form 8's and 9's.

Classical Latin

In Classical Latin, [9] integers 18 and 19 did not even have a spoken, nor written form including corresponding parts for "eight" or "nine" in practice - despite them being in existence. Instead, in Classic Latin,

For upcoming integer numerals [28, 29, 38, 39, ..., 88, 89] the additive form in the language had been much more common, however, for the listed numbers, the above form was still preferred. Hence, approaching thirty, numerals were expressed as: [10]

This is one of the main foundations of contemporary historians' reasoning, explaining why the subtractive I- and II- was so common in this range of cardinals compared to other ranges. Numerals 98 and 99 could also be expressed in both forms, yet "two to hundred" might have sounded a bit odd - clear evidence is the scarce occurrence of these numbers written down in a subtractive fashion in authentic sources.

Finnish Language

There is yet another language having this feature (by now, only in traces), however, still in active use today. This is the Finnish Language, where the (spelled out) numerals are used this way should a digit of 8 or 9 occur. The scheme is like this: [11]

...

Above list is no special case, it consequently appears in larger cardinals as well, e.g.:

Emphasizing of these attributes stay present even in the shortest colloquial forms of numerals:

...

However, this phenomenon has no influence on written numerals, the Finnish use the standard Western-Arabic decimal notation.

Time keeping

In the English language it is common to refer to times as, for example, 'seven to three', 'to' performing the negation.

Other systems

There exist other signed-digit bases such that the base . A notable examples of this is Booth encoding, which has a digit set with and , but which uses a base . The standard binary numeral system would only use digits of value .

Note that non-standard signed-digit representations are not unique. For instance:

The non-adjacent form (NAF) of Booth encoding does guarantee a unique representation for every integer value. However, this only applies for integer values. For example, consider the following repeating binary numbers in NAF,

See also

Notes and references

  1. Dhananjay Phatak, I. Koren (1994) Hybrid Signed-Digit Number Systems: A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains
  2. Augustin-Louis Cauchy (16 November 1840) "Sur les moyens d'eviter les erreurs dans les calculs numerique", Comptes rendus 11:789. Also found in Oevres completes Ser. 1, vol. 5, pp. 43442.
  3. Cajori, Florian (1993) [1928-1929]. A History of Mathematical Notations . Dover Publications. p.  57. ISBN   978-0486677668.
  4. Colson, John (1726). "A Short Account of Negativo-Affirmative Arithmetick, by Mr. John Colson, F. R. S." Philosophical Transactions. 34: 161–173. ISSN   0260-7085. JSTOR   103469.
  5. Eduard Selling (1887) Eine neue Rechenmachine, pp. 1518, Berlin
  6. Rudolf Mehmke (1902) "Numerisches Rechen", §4 Beschränkung in den verwendeten Ziffern, Klein's encyclopedia, I-2, p. 944.
  7. Hirschfeld, J. W. P. (1979). Projective Geometries Over Finite Fields. Oxford University Press. p. 8. ISBN   978-0-19-850295-1.
  8. Punjabi numbers from Quizlet
  9. J. Matthew Harrington (2016) Synopsis of Ancient Latin Grammar
  10. "duodetriginta", Wiktionary, the free dictionary, 25 March 2020, retrieved 7 April 2024
  11. "Kielitoimiston sanakirja". www.kielitoimistonsanakirja.fi. Retrieved 7 April 2024.

Related Research Articles

In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is countable if there exists an injective function from it into the natural numbers; this means that each element in the set may be associated to a unique natural number, or that the elements of the set can be counted one at a time, although the counting may never finish due to an infinite number of elements.

In commutative algebra, the prime spectrum of a commutative ring is the set of all prime ideals of , and is usually denoted by ; in algebraic geometry it is simultaneously a topological space equipped with the sheaf of rings .

<span class="mw-page-title-main">Topological group</span> Group that is a topological space with continuous group action

In mathematics, topological groups are the combination of groups and topological spaces, i.e. they are groups and topological spaces at the same time, such that the continuity condition for the group operations connects these two structures together and consequently they are not independent from each other.

A mathematical symbol is a figure or a combination of figures that is used to represent a mathematical object, an action on mathematical objects, a relation between mathematical objects, or for structuring the other symbols that occur in a formula. As formulas are entirely constituted with symbols of various types, many symbols are needed for expressing all mathematics.

In mathematics, a quadric or quadric surface (quadric hypersurface in higher dimensions), is a generalization of conic sections (ellipses, parabolas, and hyperbolas). It is a hypersurface (of dimension D) in a (D + 1)-dimensional space, and it is defined as the zero set of an irreducible polynomial of degree two in D + 1 variables; for example, D = 1 in the case of conic sections. When the defining polynomial is not absolutely irreducible, the zero set is generally not considered a quadric, although it is often called a degenerate quadric or a reducible quadric.

In ring theory, a branch of abstract algebra, a quotient ring, also known as factor ring, difference ring or residue class ring, is a construction quite similar to the quotient group in group theory and to the quotient space in linear algebra. It is a specific example of a quotient, as viewed from the general setting of universal algebra. Starting with a ring and a two-sided ideal in , a new ring, the quotient ring , is constructed, whose elements are the cosets of in subject to special and operations.

In mathematics, a Lie superalgebra is a generalisation of a Lie algebra to include a ‑grading. Lie superalgebras are important in theoretical physics where they are used to describe the mathematics of supersymmetry.

Balanced ternary is a ternary numeral system that uses a balanced signed-digit representation of the integers in which the digits have the values −1, 0, and 1. This stands in contrast to the standard (unbalanced) ternary system, in which digits have values 0, 1 and 2. The balanced ternary system can represent all integers without using a separate minus sign; the value of the leading non-zero digit of a number has the sign of the number itself. The balanced ternary system is an example of a non-standard positional numeral system. It was used in some early computers and has also been used to solve balance puzzles.

<span class="mw-page-title-main">Positional notation</span> Method for representing or encoding numbers

Positional notation, also known as place-value notation, positional numeral system, or simply place value, usually denotes the extension to any base of the Hindu–Arabic numeral system. More generally, a positional system is a numeral system in which the contribution of a digit to the value of a number is the value of the digit multiplied by a factor determined by the position of the digit. In early numeral systems, such as Roman numerals, a digit has only one value: I means one, X means ten and C a hundred. In modern positional systems, such as the decimal system, the position of the digit means that its value must be multiplied by some value: in 555, the three identical symbols represent five hundreds, five tens, and five units, respectively, due to their different positions in the digit string.

In mathematics, the ring of integers of an algebraic number field is the ring of all algebraic integers contained in . An algebraic integer is a root of a monic polynomial with integer coefficients: . This ring is often denoted by or . Since any integer belongs to and is an integral element of , the ring is always a subring of .

In mathematics, differential algebra is, broadly speaking, the area of mathematics consisting in the study of differential equations and differential operators as algebraic objects in view of deriving properties of differential equations and operators without computing the solutions, similarly as polynomial algebras are used for the study of algebraic varieties, which are solution sets of systems of polynomial equations. Weyl algebras and Lie algebras may be considered as belonging to differential algebra.

Bijective numeration is any numeral system in which every non-negative integer can be represented in exactly one way using a finite string of digits. The name refers to the bijection that exists in this case between the set of non-negative integers and the set of finite strings using a finite set of symbols.

In mathematics, in particular in algebraic geometry and differential geometry, Dolbeault cohomology (named after Pierre Dolbeault) is an analog of de Rham cohomology for complex manifolds. Let M be a complex manifold. Then the Dolbeault cohomology groups depend on a pair of integers p and q and are realized as a subquotient of the space of complex differential forms of degree (p,q).

In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations that are defined on it.

In commutative algebra, an element b of a commutative ring B is said to be integral over a subring A of B if b is a root of some monic polynomial over A.

In cryptography, learning with errors (LWE) is a mathematical problem that is widely used to create secure encryption algorithms. It is based on the idea of representing secret information as a set of equations with errors. In other words, LWE is a way to hide the value of a secret by introducing noise to it. In more technical terms, it refers to the computational problem of inferring a linear -ary function over a finite ring from given samples some of which may be erroneous. The LWE problem is conjectured to be hard to solve, and thus to be useful in cryptography.

In the study of differential equations, the Loewy decomposition breaks every linear ordinary differential equation (ODE) into what are called largest completely reducible components. It was introduced by Alfred Loewy.

In mathematics, a profinite integer is an element of the ring

Short integer solution (SIS) and ring-SIS problems are two average-case problems that are used in lattice-based cryptography constructions. Lattice-based cryptography began in 1996 from a seminal work by Miklós Ajtai who presented a family of one-way functions based on SIS problem. He showed that it is secure in an average case if the shortest vector problem (where for some constant ) is hard in a worst-case scenario.

In mathematics, derived noncommutative algebraic geometry, the derived version of noncommutative algebraic geometry, is the geometric study of derived categories and related constructions of triangulated categories using categorical tools. Some basic examples include the bounded derived category of coherent sheaves on a smooth variety, , called its derived category, or the derived category of perfect complexes on an algebraic variety, denoted . For instance, the derived category of coherent sheaves on a smooth projective variety can be used as an invariant of the underlying variety for many cases. Unfortunately, studying derived categories as geometric objects of themselves does not have a standardized name.