Symmetric level-index arithmetic

Last updated

The level-index (LI) representation of numbers, and its algorithms for arithmetic operations, were introduced by Charles Clenshaw and Frank Olver in 1984. [1]

Contents

The symmetric form of the LI system and its arithmetic operations were presented by Clenshaw and Peter Turner in 1987. [2]

Michael Anuta, Daniel Lozier, Nicolas Schabanel and Turner developed the algorithm for symmetric level-index (SLI) arithmetic, and a parallel implementation of it. There has been extensive work on developing the SLI arithmetic algorithms and extending them to complex and vector arithmetic operations.

Definition

The idea of the level-index system is to represent a non-negative real number X as

where and the process of exponentiation is performed times, with . and f are the level and index of X respectively. x = + f is the LI image of X. For example,

so its LI image is

The symmetric form is used to allow negative exponents, if the magnitude of X is less than 1. One takes sgn(log(X)) or sgn(|X|  |X|−1) and stores it (after substituting +1 for 0 for the reciprocal sign since for X = 1 = e0 the LI image is x = 1.0 and uniquely defines X=1 and we can do away without a third state and use only one bit for the two states −1 and +1[ clarification needed ]) as the reciprocal sign rX. Mathematically, this is equivalent to taking the reciprocal (multiplicative inverse) of a small magnitude number, and then finding the SLI image for the reciprocal. Using one bit for the reciprocal sign enables the representation of extremely small numbers.

A sign bit may also be used to allow negative numbers. One takes sgn(X) and stores it (after substituting +1 for 0 for the sign since for X = 0 the LI image is x = 0.0 and uniquely defines X = 0 and we can do away without a third state and use only one bit for the two states −1 and +1[ clarification needed ]) as the sign sX. Mathematically, this is equivalent to taking the inverse (additive inverse) of a negative number, and then finding the SLI image for the inverse. Using one bit for the sign enables the representation of negative numbers.

The mapping function is called the generalized logarithm function. It is defined as

and it maps onto itself monotonically and so it is invertible on this interval. The inverse, the generalized exponential function, is defined by

The density of values X represented by x has no discontinuities as we go from level to  + 1 (a very desirable property) since:

The generalized logarithm function is closely related to the iterated logarithm used in computer science analysis of algorithms.

Formally, we can define the SLI representation for an arbitrary real X (not 0 or 1) as

where sX is the sign (additive inversion or not) of X and rX is the reciprocal sign (multiplicative inversion or not) as in the following equations:

whereas for X = 0 or 1, we have:

For example,

and its SLI representation is

See also

Related Research Articles

In mathematics, any vector space has a corresponding dual vector space consisting of all linear forms on together with the vector space structure of pointwise addition and scalar multiplication by constants.

<span class="mw-page-title-main">Fibonacci sequence</span> Numbers obtained by adding the two previous ones

In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted Fn. The sequence commonly starts from 0 and 1, although some authors start the sequence from 1 and 1 or sometimes from 1 and 2. Starting from 0 and 1, the sequence begins

The Riesz representation theorem, sometimes called the Riesz–Fréchet representation theorem after Frigyes Riesz and Maurice René Fréchet, establishes an important connection between a Hilbert space and its continuous dual space. If the underlying field is the real numbers, the two are isometrically isomorphic; if the underlying field is the complex numbers, the two are isometrically anti-isomorphic. The (anti-) isomorphism is a particular natural isomorphism.

<span class="mw-page-title-main">Laplace's equation</span> Second-order partial differential equation

In mathematics and physics, Laplace's equation is a second-order partial differential equation named after Pierre-Simon Laplace, who first studied its properties. This is often written as

In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent if it has a model, i.e., there exists an interpretation under which all formulas in the theory are true. This is the sense used in traditional Aristotelian logic, although in contemporary mathematical logic the term satisfiable is used instead. The syntactic definition states a theory is consistent if there is no formula such that both and its negation are elements of the set of consequences of . Let be a set of closed sentences and the set of closed sentences provable from under some formal deductive system. The set of axioms is consistent when there is no formula such that and .

<span class="mw-page-title-main">Noether's theorem</span> Statement relating differentiable symmetries to conserved quantities

Noether's theorem states that every continuous symmetry of the action of a physical system with conservative forces has a corresponding conservation law. This is the first of two theorems proven by mathematician Emmy Noether in 1915 and published in 1918. The action of a physical system is the integral over time of a Lagrangian function, from which the system's behavior can be determined by the principle of least action. This theorem only applies to continuous and smooth symmetries of physical space.

Geometrical optics, or ray optics, is a model of optics that describes light propagation in terms of rays. The ray in geometrical optics is an abstraction useful for approximating the paths along which light propagates under certain circumstances.

<span class="mw-page-title-main">Schwinger–Dyson equation</span> Equations for correlation functions in QFT

The Schwinger–Dyson equations (SDEs) or Dyson–Schwinger equations, named after Julian Schwinger and Freeman Dyson, are general relations between correlation functions in quantum field theories (QFTs). They are also referred to as the Euler–Lagrange equations of quantum field theories, since they are the equations of motion corresponding to the Green's function. They form a set of infinitely many functional differential equations, all coupled to each other, sometimes referred to as the infinite tower of SDEs.

<span class="mw-page-title-main">LSZ reduction formula</span> Connection between correlation functions and the S-matrix

In quantum field theory, the Lehmann–Symanzik–Zimmermann (LSZ) reduction formula is a method to calculate S-matrix elements from the time-ordered correlation functions of a quantum field theory. It is a step of the path that starts from the Lagrangian of some quantum field theory and leads to prediction of measurable quantities. It is named after the three German physicists Harry Lehmann, Kurt Symanzik and Wolfhart Zimmermann.

<span class="mw-page-title-main">Nonlinear Schrödinger equation</span> Nonlinear form of the Schrödinger equation

In theoretical physics, the (one-dimensional) nonlinear Schrödinger equation (NLSE) is a nonlinear variation of the Schrödinger equation. It is a classical field equation whose principal applications are to the propagation of light in nonlinear optical fibers and planar waveguides and to Bose–Einstein condensates confined to highly anisotropic, cigar-shaped traps, in the mean-field regime. Additionally, the equation appears in the studies of small-amplitude gravity waves on the surface of deep inviscid (zero-viscosity) water; the Langmuir waves in hot plasmas; the propagation of plane-diffracted wave beams in the focusing regions of the ionosphere; the propagation of Davydov's alpha-helix solitons, which are responsible for energy transport along molecular chains; and many others. More generally, the NLSE appears as one of universal equations that describe the evolution of slowly varying packets of quasi-monochromatic waves in weakly nonlinear media that have dispersion. Unlike the linear Schrödinger equation, the NLSE never describes the time evolution of a quantum state. The 1D NLSE is an example of an integrable model.

Independence-friendly logic is an extension of classical first-order logic (FOL) by means of slashed quantifiers of the form and , where is a finite set of variables. The intended reading of is "there is a which is functionally independent from the variables in ". IF logic allows one to express more general patterns of dependence between variables than those which are implicit in first-order logic. This greater level of generality leads to an actual increase in expressive power; the set of IF sentences can characterize the same classes of structures as existential second-order logic.

In mathematics, the explicit formulae for L-functions are relations between sums over the complex number zeroes of an L-function and sums over prime powers, introduced by Riemann (1859) for the Riemann zeta function. Such explicit formulae have been applied also to questions on bounding the discriminant of an algebraic number field, and the conductor of a number field.

The following are important identities involving derivatives and integrals in vector calculus.

In mathematics, the Morse–Palais lemma is a result in the calculus of variations and theory of Hilbert spaces. Roughly speaking, it states that a smooth enough function near a critical point can be expressed as a quadratic form after a suitable change of coordinates.

In constructive mathematics, Church's thesis is the principle stating that all total functions are computable functions.

In mathematical analysis, and especially in real, harmonic analysis and functional analysis, an Orlicz space is a type of function space which generalizes the Lp spaces. Like the Lp spaces, they are Banach spaces. The spaces are named for Władysław Orlicz, who was the first to define them in 1932.

Lagrangian field theory is a formalism in classical field theory. It is the field-theoretic analogue of Lagrangian mechanics. Lagrangian mechanics is used to analyze the motion of a system of discrete particles each with a finite number of degrees of freedom. Lagrangian field theory applies to continua and fields, which have an infinite number of degrees of freedom.

In first-order arithmetic, the induction principles, bounding principles, and least number principles are three related families of first-order principles, which may or may not hold in nonstandard models of arithmetic. These principles are often used in reverse mathematics to calibrate the axiomatic strength of theorems.

In set theory and logic, Buchholz's ID hierarchy is a hierarchy of subsystems of first-order arithmetic. The systems/theories are referred to as "the formal theories of ν-times iterated inductive definitions". IDν extends PA by ν iterated least fixed points of monotone operators.

References

  1. Clenshaw, Charles William; Olver, Frank William John (1984). "Beyond floating point". Journal of the ACM . 31 (2): 319–328. doi: 10.1145/62.322429 .
  2. Clenshaw, Charles William; Turner, Peter R. (1988-10-01) [1986-09-16, 1987-06-04]. "The Symmetric Level-Index System". IMA Journal of Numerical Analysis . Oxford University Press, Institute of Mathematics and Its Applications. 8 (4): 517–526. doi:10.1093/imanum/8.4.517. ISSN   0272-4979. OCLC   42026743 . Retrieved 2018-07-10.

Further reading