Redirected from Logarithmic algorithm
In mathematics, the logarithm functions are the inverses of the exponential functions. If x is b to the power y, x = b^{y}, we also say that y is the logarithm of x in the base b (meaning y is the power we have to raise b to, in order to get x), and we write log_{b}x = y. For instance, log_{10}100 = 2 (since 10^{2}=100) and log_{2}8 = 3 (since 2^{3}=8).
Logarithms were invented by John Napier in the early 1600s. Before the widespread availability of electronic computers, logarithms were widely used as a calculating aid, both with tables of logarithms and slide rules. The basic idea here is that the logarithm of a product is the sum of the logarithms, and adding is easier than multiplying. In these applications, the base10 or common logarithm was typically used.
Logarithms are also useful in order to solve equations in which the unknown appears in the exponent, and they often occur as the solution of differential equations because of their simple derivatives. Furthermore, various quantities in science are expressed by their logarithms; see logarithmic scale for an explanation and a list.
The function log_{b}(x) is defined whenever x is a positive real number and b is a positive real number different from 1. See logarithmic identities for several rules governing the logarithm functions.
There is a special base e (approximately 2.718) which has useful properties. The logarithm to this base is called the natural logarithm. When dealing with the logarithms to the base e, it is common especially to denote log_{e} by ln, especially if there is any likelihood that the reader might think that base 10 or base 2 logarithms might be meant. In most pure mathematical work, log is used to denote log_{e}, in most engineering work, it means log_{10}, while in information theory, it often means log_{2}, which also sometimes is written as lg. Whenever a possibility for ambiguity exists, this ambiguity should be resolved by explicitly writing out the base.
A base used extensively in computer science is the binary logarithm. It is used frequently because many algorithms and computer applications split items into two subitems. Binary logarithms are useful in determining functions that exhibit this behaviour.
A curious coincidence is the approximation log_{2}(x) ≈ log_{10}(x) + ln(x), accurate to about 99.4% or 2 significant digits.
Logarithms may also be defined for complex arguments. This is explained on the natural logarithm page.
In the theory of finite groups there is a related notion of discrete logarithm. For some finite groups, it is believed that the discrete logarithm is very hard to calculate, whereas discrete exponentials are quite easy. This asymmetry has applications in cryptography.
Search Encyclopedia

Featured Article
