Math library

Last updated August 08, 2023

In computer science, a math library (or maths library) is a component of a programming language's standard library containing functions (or subroutines) for the most common mathematical functions, such as trigonometry and exponentiation. Bit-twiddling and control functionalities related to floating point numbers may also be included (such as in C).

Implementation outline

Basic operations

In a math library, it is frequently useful to use type punning to interpret a floating-point number as an unsigned integer of the same size. This allows for faster inspection of certain numeral properties (positive or not) and number comparison. In more advanced cases, bit twiddling may be used to modify a number in a specific way.

For more exact operation, a double double or even triple double format may be used. In this case, a high-precision number is expressed as the sum of two or three floating-point numbers.^[5]

Transcendental functions

Transcendental functions such as log, exponential, and trig functions make up the backbone of any math library. These functions are generally implemented by a polynomial fit, usually a Taylor polynomial or a Chebyshev polynomial derived by the Remez algorithm (having the benefit of an improved error bound), but the pre-processing steps are equally important.^[5]

Trignometry

Range reduction (also argument reduction, domain-spltting) is the first step for any function, after checks for unusual values (infinity and NaN) are performed. The goal here is to reduce the domain of the argument for the polynomial to process, using the function's symmetry and periodicity (if any), setting flags to indicate e.g. whether to negate the result in the end (if needed). It is worth noting that periodic functions require higher-than-input precision when reducing, with the prototypical method being the Payne–Hanek–Corbett algorithm.^[6] After range reduction, near-zero values may be subject to a "fast path": for example, a tiny input $x$ can be returned directly in sin, while $1 - | x |$ may be used for cos.

The next step is the evaluation of the polynomial, with a conventional Horner's method used. After that, the sign of the result can be flipped according to the information from the range-reduction routine before being returned.

Logarithm and exponential

Logarithm in base 2 is relatively straightforward, as the integer part k is already in the floating-point exponent; a preliminary range reduction is accordingly performed, yielding k. The mantissa x (where log2(x) is between -1/2 and 1/2) is then compared to a table and intervals for further reduction into a z with known log2 and an in-range x/z, along with polynomial coefficients used for the interval x/z is in. The result is then log(z) + log(x/z) + k.^[7] Logarithm in other bases follow a similar approach, with the differences being (a) a different table is used; (b) k needs to be multiplied by log2(new-base).^[7]

Exponential in base 2 is similarly the "base case" due to floating-point structure. The procedure is simply a combination of range reduction (usually by lookup) and a polynomial over the remaining mantissa.^[7] The natural exponent may be implemented with a separate table for precision, while exp10 can simply be exp(x × log2(10)) when in-range.^[7] Finally, the any-base exponent function pow() is built around exp() and log() in the general case.^[7]

Related Research Articles

<span class="mw-page-title-main">Exponential function</span> Mathematical function, denoted exp(x) or e^x

The exponential function is a mathematical function denoted by $or . Unless otherwise specified, the term generally refers to the positive-valued function of a real variable, although it can be extended to the complex numbers or generalized to other mathematical objects like matrices or Lie algebras. The exponential function originated from the notion of exponentiation, but modern definitions allow it to be rigorously extended to all real arguments, including irrational numbers. Its ubiquitous occurrence in pure and applied mathematics led mathematician Walter Rudin to opine that the exponential function is "the most important function in mathematics".$

In computing, floating-point arithmetic (FP) is arithmetic that represents subsets of real numbers using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. Numbers of this form are called floating-point numbers. For example, 12.345 is a floating-point number in base ten with five digits of precision:

IEEE 754-1985 was an industry standard for representing floating-point numbers in computers, officially adopted in 1985 and superseded in 2008 by IEEE 754-2008, and then again in 2019 by minor revision IEEE 754-2019. During its 23 years, it was the most widely used format for floating-point computation. It was implemented in software, in the form of floating-point libraries, and in hardware, in the instructions of many CPUs and FPUs. The first integrated circuit to implement the draft of what was to become IEEE 754-1985 was the Intel 8087.

In mathematics, the logarithm is the inverse function to exponentiation. That means that the logarithm of a number $x$ to the base $b$ is the exponent to which $b$ must be raised to produce $x$ . For example, since $1000 = 10 3$ , the logarithm base 10 of $1000$ is $3$ , or $log 10 (1000) = 3$ . The logarithm of $x$ to base $b$ is denoted as $log b (x)$ , or without parentheses, $log b x$ , or even without the explicit base, $log x$ , when no confusion is possible, or when the base does not matter such as in big O notation.

The natural logarithm of a number is its logarithm to the base of the mathematical constant $e$ , which is an irrational and transcendental number approximately equal to $2.718 281828459$ . The natural logarithm of $x$ is generally written as $ln x$ , $log e x$ , or sometimes, if the base $e$ is implicit, simply $log x$ . Parentheses are sometimes added for clarity, giving $ln(x)$ , $log e (x)$ , or $log(x)$ . This is done particularly when the argument to the logarithm is not a single symbol, so as to prevent ambiguity.

<span class="mw-page-title-main">Exponentiation</span> Mathematical operation

In mathematics, exponentiation is an operation involving two numbers, the base and the exponent or power. Exponentiation is written as $b n$ , where $b$ is the base and $n$ is the power; this is pronounced as " $b$ (raised) to the $n$ ". When $n$ is a positive integer, exponentiation corresponds to repeated multiplication of the base: that is, $b n$ is the product of multiplying $n$ bases:

In mathematics, tables of trigonometric functions are useful in a number of areas. Before the existence of pocket calculators, trigonometric tables were essential for navigation, science and engineering. The calculation of mathematical tables was an important area of study, which led to the development of the first mechanical computing devices.

In mathematics, the common logarithm is the logarithm with base 10. It is also known as the decadic logarithm and as the decimal logarithm, named after its base, or Briggsian logarithm, after Henry Briggs, an English mathematician who pioneered its use, as well as standard logarithm. Historically, it was known as logarithmus decimalis or logarithmus decadis. It is indicated by $log(x)$ , $log 10 (x)$ , or sometimes $Log(x)$ with a capital $L$ (however, this notation is ambiguous, since it can also mean the complex natural logarithmic multi-valued function). On calculators, it is printed as "log", but mathematicians usually mean natural logarithm (logarithm with base e ≈ 2.71828) rather than common logarithm when they write "log". To mitigate this ambiguity, the ISO 80000 specification recommends that $log 10 (x)$ should be written $lg(x)$ , and $log e (x)$ should be $ln(x)$ .

In mathematics, for given real numbers a and b, the logarithm log_b a is a number x such that b^x = a. Analogously, in any group G, powers b^k can be defined for all integers k, and the discrete logarithm log_b a is an integer k such that b^k = a. In number theory, the more commonly used term is index: we can write x = ind_ra (mod m) (read "the index of a to the base r modulo m") for r^x ≡ a (mod m) if r is a primitive root of m and gcd(a,m) = 1.

In mathematics, the binary logarithm is the power to which the number $2$ must be raised to obtain the value $n$ . That is, for any real number $x$ ,

In mathematics, a transcendental function is an analytic function that does not satisfy a polynomial equation, in contrast to an algebraic function. In other words, a transcendental function "transcends" algebra in that it cannot be expressed algebraically.

The IEEE Standard for Floating-Point Arithmetic is a technical standard for floating-point arithmetic established in 1985 by the Institute of Electrical and Electronics Engineers (IEEE). The standard addressed many problems found in the diverse floating-point implementations that made them difficult to use reliably and portably. Many hardware floating-point units use the IEEE 754 standard.

The significand is part of a number in scientific notation or in floating-point representation, consisting of its significant digits. Depending on the interpretation of the exponent, the significand may represent an integer or a fraction.

In computing, a roundoff error, also called rounding error, is the difference between the result produced by a given algorithm using exact arithmetic and the result produced by the same algorithm using finite-precision, rounded arithmetic. Rounding errors are due to inexactness in the representation of real numbers and the arithmetic operations done with them. This is a form of quantization error. When using approximation equations or algorithms, especially when using finitely many digits to represent real numbers, one of the goals of numerical analysis is to estimate computation errors. Computation errors, also called numerical errors, include both truncation errors and roundoff errors.

In computer science and numerical analysis, unit in the last place or unit of least precision (ulp) is the spacing between two consecutive floating-point numbers, i.e., the value the least significant digit represents if it is 1. It is used as a measure of accuracy in numeric calculations.

Extended precision refers to floating-point number formats that provide greater precision than the basic floating-point formats. Extended precision formats support a basic format by minimizing roundoff and overflow errors in intermediate values of expressions on the base format. In contrast to extended precision, arbitrary-precision arithmetic refers to implementations of much larger numeric types using special software.

The BKM algorithm is a shift-and-add algorithm for computing elementary functions, first published in 1994 by Jean-Claude Bajard, Sylvanus Kla, and Jean-Michel Muller. BKM is based on computing complex logarithms (L-mode) and exponentials (E-mode) using a method similar to the algorithm Henry Briggs used to compute logarithms. By using a precomputed table of logarithms of negative powers of two, the BKM algorithm computes elementary functions using only integer add, shift, and compare operations.

In computing, half precision is a binary floating-point computer number format that occupies 16 bits in computer memory. It is intended for storage of floating-point values in applications where higher precision is not essential, in particular image processing and neural networks.

In computing, quadruple precision is a binary floating point–based computer number format that occupies 16 bytes with precision at least twice the 53-bit double precision.

In computing, Microsoft Binary Format (MBF) is a format for floating-point numbers which was used in Microsoft's BASIC languages, including MBASIC, GW-BASIC and QuickBASIC prior to version 4.00.

References

↑ "C math library".
↑ "java maths library".
↑ "haskell prelude maths".
↑ "haskell prelude".
1 2 Daramy-Loirat, Catherine; Defour, David; Dinechin, Florent de; Gallet, Matthieu; Gast, Nicolas; Lauter, Christoph; Muller, Jean-Michel (December 2006). CR-LIBM A library of correctly rounded elementary functions in double-precision (Report).
↑ Brisebarre, N.; Defour, D.; Kornerup, P.; Muller, J.-M.; Revol, N. (March 2005). "A new range-reduction algorithm". IEEE Transactions on Computers. 54 (3): 331–339. doi:10.1109/TC.2005.36.
1 2 3 4 5 musl v1.2.2 math directory, log1p.c, log2.c, log10.c, exp2.c

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] "C math library".

[2] "java maths library".

[3] "haskell prelude maths".

[4] "haskell prelude".

[cr-5] 1 2 Daramy-Loirat, Catherine; Defour, David; Dinechin, Florent de; Gallet, Matthieu; Gast, Nicolas; Lauter, Christoph; Muller, Jean-Michel (December 2006). CR-LIBM A library of correctly rounded elementary functions in double-precision (Report).

[6] Brisebarre, N.; Defour, D.; Kornerup, P.; Muller, J.-M.; Revol, N. (March 2005). "A new range-reduction algorithm". IEEE Transactions on Computers. 54 (3): 331–339. doi:10.1109/TC.2005.36.

[musl-7] 1 2 3 4 5 musl v1.2.2 math directory, log1p.c, log2.c, log10.c, exp2.c

[1]

[2]

[3]

[4]

[5]

[6]

[7]