Encyclopedia > Logarithmic algorithm

  Article Content


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 = by, 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 logbx = y. For instance, log10100 = 2 (since 102=100) and log28 = 3 (since 23=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 base-10 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 logb(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 loge 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 loge, in most engineering work, it means log10, while in information theory, it often means log2, 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 sub-items. Binary logarithms are useful in determining functions that exhibit this behaviour.

A curious coincidence is the approximation log2(x) ≈ log10(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.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article

... with its impressive Iguaçu[?] falls, the Rio Negro, São Francisco[?], Xingu, Madeira and the Tapajós[?] rivers. Situated along the equator, Brazil's climate is ...

This page was created in 23.9 ms