HOME

TheInfoList



OR:

In mathematics, the binary logarithm () is the power to which the number must be raised to obtain the value . That is, for any real number , :x=\log_2 n \quad\Longleftrightarrow\quad 2^x=n. For example, the binary logarithm of is , the binary logarithm of is , the binary logarithm of is , and the binary logarithm of is . The binary logarithm is the
logarithm In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number  to the base  is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 of ...
to the base and is the
inverse function In mathematics, the inverse function of a function (also called the inverse of ) is a function that undoes the operation of . The inverse of exists if and only if is bijective, and if it exists, is denoted by f^ . For a function f\colon ...
of the
power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer  as the exponent. In a context where only integers are considered, is restricted to non-negati ...
function. As well as , an alternative notation for the binary logarithm is (the notation preferred by ISO 31-11 and
ISO 80000-2 ISO 80000 or IEC 80000 is an international standard introducing the International System of Quantities (ISQ). It was developed and promulgated jointly by the International Organization for Standardization (ISO) and the International Electrotec ...
). Historically, the first application of binary logarithms was in music theory, by
Leonhard Euler Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ma ...
: the binary logarithm of a frequency ratio of two musical tones gives the number of
octave In music, an octave ( la, octavus: eighth) or perfect octave (sometimes called the diapason) is the interval between one musical pitch and another with double its frequency. The octave relationship is a natural phenomenon that has been refer ...
s by which the tones differ. Binary logarithms can be used to calculate the length of the representation of a number in the
binary numeral system A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" ( zero) and "1" (one). The base-2 numeral system is a positional notatio ...
, or the number of
bit The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represented a ...
s needed to encode a message in
information theory Information theory is the scientific study of the quantification, storage, and communication of information. The field was originally established by the works of Harry Nyquist and Ralph Hartley, in the 1920s, and Claude Shannon in the 1940s. ...
. In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, they count the number of steps needed for
binary search In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the m ...
and related algorithms. Other areas in which the binary logarithm is frequently used include
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
,
bioinformatics Bioinformatics () is an interdisciplinary field that develops methods and software tools for understanding biological data, in particular when the data sets are large and complex. As an interdisciplinary field of science, bioinformatics combin ...
, the design of sports tournaments, and
photography Photography is the visual art, art, application, and practice of creating durable images by recording light, either electronically by means of an image sensor, or chemically by means of a light-sensitive material such as photographic film. It i ...
. Binary logarithms are included in the standard C mathematical functions and other mathematical software packages. The integer part of a binary logarithm can be found using the find first set operation on an integer value, or by looking up the exponent of a
floating point In computing, floating-point arithmetic (FP) is arithmetic that represents real numbers approximately, using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. For example, 12.345 can be r ...
value. The fractional part of the logarithm can be calculated efficiently.


History

The powers of two have been known since antiquity; for instance, they appear in Euclid's ''Elements'', Props. IX.32 (on the factorization of powers of two) and IX.36 (half of the Euclid–Euler theorem, on the structure of even
perfect number In number theory, a perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, 6 has divisors 1, 2 and 3 (excluding itself), and 1 + 2 + 3 = 6, so 6 is a perfect number. T ...
s). And the binary logarithm of a power of two is just its position in the ordered sequence of powers of two. On this basis,
Michael Stifel Michael Stifel or Styfel (1487 – April 19, 1567) was a German monk, Protestant reformer and mathematician. He was an Augustinian who became an early supporter of Martin Luther. He was later appointed professor of mathematics at Jena Univer ...
has been credited with publishing the first known table of binary logarithms in 1544. His book ''Arithmetica Integra'' contains several tables that show the
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s with their corresponding powers of two. Reversing the rows of these tables allow them to be interpreted as tables of binary logarithms. Earlier than Stifel, the 8th century Jain mathematician
Virasena Acharya Virasena (792-853 CE), also known as Veerasena, was a Digambara monk and belonged to the lineage of Acharya Kundakunda. He was an Indian mathematician and Jain philosopher and scholar. He was also known as a famous orator and an accomp ...
is credited with a precursor to the binary logarithm. Virasena's concept of ''ardhacheda'' has been defined as the number of times a given number can be divided evenly by two. This definition gives rise to a function that coincides with the binary logarithm on the powers of two, but it is different for other integers, giving the
2-adic order In mathematics an even integer, that is, a number that is divisible by 2, is called evenly even or doubly even if it is a multiple of 4, and oddly even or singly even if it is not. The former names are traditional ones, derived from ancient Gr ...
rather than the logarithm. The modern form of a binary logarithm, applying to any number (not just powers of two) was considered explicitly by
Leonhard Euler Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ma ...
in 1739. Euler established the application of binary logarithms to music theory, long before their applications in information theory and computer science became known. As part of his work in this area, Euler published a table of binary logarithms of the integers from 1 to 8, to seven decimal digits of accuracy.


Definition and properties

The binary logarithm function may be defined as the
inverse function In mathematics, the inverse function of a function (also called the inverse of ) is a function that undoes the operation of . The inverse of exists if and only if is bijective, and if it exists, is denoted by f^ . For a function f\colon ...
to the
power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer  as the exponent. In a context where only integers are considered, is restricted to non-negati ...
function, which is a strictly increasing function over the positive
real number In mathematics, a real number is a number that can be used to measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small var ...
s and therefore has a unique inverse. Alternatively, it may be defined as , where is the
natural logarithm The natural logarithm of a number is its logarithm to the base of the mathematical constant , which is an irrational and transcendental number approximately equal to . The natural logarithm of is generally written as , , or sometimes, if ...
, defined in any of its standard ways. Using the complex logarithm in this definition allows the binary logarithm to be extended to the
complex number In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the for ...
s. As with other logarithms, the binary logarithm obeys the following equations, which can be used to simplify formulas that combine binary logarithms with multiplication or exponentiation: :\log_2 xy=\log_2 x + \log_2 y :\log_2\frac=\log_2 x - \log_2 y :\log_2 x^y = y\log_2 x. For more, see
list of logarithmic identities In mathematics, many logarithmic identities exist. The following is a compilation of the notable of these, many of which are used for computational purposes. Trivial identities : Explanations By definition, we know that: :\color \log \color ...
.


Notation

In mathematics, the binary logarithm of a number is often written as . However, several other notations for this function have been used or proposed, especially in application areas. Some authors write the binary logarithm as ,. the notation listed in ''
The Chicago Manual of Style ''The Chicago Manual of Style'' (abbreviated in writing as ''CMOS'' or ''CMS'', or sometimes as ''Chicago'') is a style guide for American English published since 1906 by the University of Chicago Press. Its 17 editions have prescribed writ ...
''.
Donald Knuth Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer ...
credits this notation to a suggestion of
Edward Reingold Edward M. Reingold (born 1945) is a computer scientist active in the fields of algorithms, data structures, graph drawing, and calendrical calculations. In 1996 he was inducted as a Fellow of the Association for Computing Machinery. In 2000 he ...
,
p. 11
The same notation was in the 1973 2nd edition of the same book (p. 23) but without the credit to Reingold.
but its use in both information theory and computer science dates to before Reingold was active. The binary logarithm has also been written as with a prior statement that the default base for the logarithm is . Another notation that is often used for the same function (especially in the German scientific literature) is ,. from
Latin Latin (, or , ) is a classical language belonging to the Italic branch of the Indo-European languages. Latin was originally a dialect spoken in the lower Tiber area (then known as Latium) around present-day Rome, but through the power ...
'' logarithmus dualis'' or ''logarithmus dyadis''. The , ISO 31-11 and
ISO 80000-2 ISO 80000 or IEC 80000 is an international standard introducing the International System of Quantities (ISQ). It was developed and promulgated jointly by the International Organization for Standardization (ISO) and the International Electrotec ...
standards recommend yet another notation, . According to these standards, should not be used for the binary logarithm, as it is instead reserved for the
common logarithm 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 ...
.


Applications


Information theory

The number of digits (
bit The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represented a ...
s) in the binary representation of a positive integer is the integral part of , i.e. : \lfloor \log_2 n\rfloor + 1. In information theory, the definition of the amount of self-information and
information entropy In information theory, the entropy of a random variable is the average level of "information", "surprise", or "uncertainty" inherent to the variable's possible outcomes. Given a discrete random variable X, which takes values in the alphabet \ ...
is often expressed with the binary logarithm, corresponding to making the bit the fundamental unit of information. With these units, the Shannon–Hartley theorem expresses the information capacity of a channel as the binary logarithm of its signal-to-noise ratio, plus one. However, the
natural logarithm The natural logarithm of a number is its logarithm to the base of the mathematical constant , which is an irrational and transcendental number approximately equal to . The natural logarithm of is generally written as , , or sometimes, if ...
and the
nat Nat or NAT may refer to: Computing * Network address translation (NAT), in computer networking Organizations * National Actors Theatre, New York City, U.S. * National AIDS trust, a British charity * National Archives of Thailand * National ...
are also used in alternative notations for these definitions.


Combinatorics

Although the natural logarithm is more important than the binary logarithm in many areas of pure mathematics such as
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Math ...
and
mathematical analysis Analysis is the branch of mathematics dealing with continuous functions, limit (mathematics), limits, and related theories, such as Derivative, differentiation, Integral, integration, measure (mathematics), measure, infinite sequences, series (m ...
, the binary logarithm has several applications in
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
: *Every binary tree with leaves has height at least , with equality when is a
power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer  as the exponent. In a context where only integers are considered, is restricted to non-negati ...
and the tree is a complete binary tree. Relatedly, the
Strahler number In mathematics, the Strahler number or Horton–Strahler number of a mathematical tree is a numerical measure of its branching complexity. These numbers were first developed in hydrology by and ; in this application, they are referred to as the ...
of a river system with tributary streams is at most . *Every
family of sets In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets, set fa ...
with different sets has at least elements in its union, with equality when the family is a
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is ...
. *Every
partial cube In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cub ...
with vertices has isometric dimension at least , and has at most edges, with equality when the partial cube is a
hypercube graph In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. has vertices, e ...
. *According to Ramsey's theorem, every -vertex undirected graph has either a
clique A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popula ...
or an independent set of size logarithmic in . The precise size that can be guaranteed is not known, but the best bounds known on its size involve binary logarithms. In particular, all graphs have a clique or independent set of size at least and almost all graphs do not have a clique or independent set of size larger than . *From a mathematical analysis of the Gilbert–Shannon–Reeds model of random shuffles, one can show that the number of times one needs to shuffle an -card deck of cards, using riffle shuffles, to get a distribution on permutations that is close to uniformly random, is approximately . This calculation forms the basis for a recommendation that 52-card decks should be shuffled seven times.


Computational complexity

The binary logarithm also frequently appears in the analysis of algorithms, not only because of the frequent use of binary number arithmetic in algorithms, but also because binary logarithms occur in the analysis of algorithms based on two-way branching. If a problem initially has choices for its solution, and each iteration of the algorithm reduces the number of choices by a factor of two, then the number of iterations needed to select a single choice is again the integral part of . This idea is used in the analysis of several
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s and
data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the rel ...
s. For example, in
binary search In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the m ...
, the size of the problem to be solved is halved with each iteration, and therefore roughly iterations are needed to obtain a solution for a problem of size . Similarly, a perfectly balanced
binary search tree In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and ...
containing elements has height . The running time of an algorithm is usually expressed in big O notation, which is used to simplify expressions by omitting their constant factors and lower-order terms. Because logarithms in different bases differ from each other only by a constant factor, algorithms that run in time can also be said to run in, say, time. The base of the logarithm in expressions such as or is therefore not important and can be omitted. However, for logarithms that appear in the exponent of a time bound, the base of the logarithm cannot be omitted. For example, is not the same as because the former is equal to and the latter to . Algorithms with running time are sometimes called
linearithmic In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
. Some examples of algorithms with running time or are: * Average time quicksort and other
comparison sort A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should oc ...
algorithms *Searching in balanced
binary search tree In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and ...
s * Exponentiation by squaring * Longest increasing subsequence Binary logarithms also occur in the exponents of the time bounds for some
divide and conquer algorithm In computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical ...
s, such as the Karatsuba algorithm for multiplying -bit numbers in time , and the Strassen algorithm for multiplying matrices in time . The occurrence of binary logarithms in these running times can be explained by reference to the master theorem for divide-and-conquer recurrences.


Bioinformatics

In
bioinformatics Bioinformatics () is an interdisciplinary field that develops methods and software tools for understanding biological data, in particular when the data sets are large and complex. As an interdisciplinary field of science, bioinformatics combin ...
,
microarray A microarray is a multiplex lab-on-a-chip. Its purpose is to simultaneously detect the expression of thousands of genes from a sample (e.g. from a tissue). It is a two-dimensional array on a solid substrate—usually a glass slide or silic ...
s are used to measure how strongly different genes are expressed in a sample of biological material. Different rates of expression of a gene are often compared by using the binary logarithm of the ratio of expression rates: the log ratio of two expression rates is defined as the binary logarithm of the ratio of the two rates. Binary logarithms allow for a convenient comparison of expression rates: a doubled expression rate can be described by a log ratio of , a halved expression rate can be described by a log ratio of , and an unchanged expression rate can be described by a log ratio of zero, for instance. Data points obtained in this way are often visualized as a scatterplot in which one or both of the coordinate axes are binary logarithms of intensity ratios, or in visualizations such as the MA plot and RA plot that rotate and scale these log ratio scatterplots.


Music theory

In music theory, the interval or perceptual difference between two tones is determined by the ratio of their frequencies. Intervals coming from
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ra ...
ratios with small numerators and denominators are perceived as particularly euphonious. The simplest and most important of these intervals is the
octave In music, an octave ( la, octavus: eighth) or perfect octave (sometimes called the diapason) is the interval between one musical pitch and another with double its frequency. The octave relationship is a natural phenomenon that has been refer ...
, a frequency ratio of . The number of octaves by which two tones differ is the binary logarithm of their frequency ratio.. To study tuning systems and other aspects of music theory that require finer distinctions between tones, it is helpful to have a measure of the size of an interval that is finer than an octave and is additive (as logarithms are) rather than multiplicative (as frequency ratios are). That is, if tones , , and form a rising sequence of tones, then the measure of the interval from to plus the measure of the interval from to should equal the measure of the interval from to . Such a measure is given by the cent, which divides the octave into equal intervals (
semitone A semitone, also called a half step or a half tone, is the smallest musical interval commonly used in Western tonal music, and it is considered the most dissonant when sounded harmonically. It is defined as the interval between two adjacent no ...
s of cents each). Mathematically, given tones with frequencies and , the number of cents in the interval from to is :\left, 1200\log_2\frac\. The millioctave is defined in the same way, but with a multiplier of instead of .


Sports scheduling

In competitive games and sports involving two players or teams in each game or match, the binary logarithm indicates the number of rounds necessary in a
single-elimination tournament A single-elimination, knockout, or sudden death tournament is a type of elimination tournament where the loser of each match-up is immediately eliminated from the tournament. Each winner will play another in the next round, until the final mat ...
required to determine a winner. For example, a tournament of players requires rounds to determine the winner, a tournament of teams requires rounds, etc. In this case, for players/teams where is not a power of 2, is rounded up since it is necessary to have at least one round in which not all remaining competitors play. For example, is approximately , which rounds up to , indicating that a tournament of teams requires rounds (either two teams sit out the first round, or one team sits out the second round). The same number of rounds is also necessary to determine a clear winner in a Swiss-system tournament.


Photography

In
photography Photography is the visual art, art, application, and practice of creating durable images by recording light, either electronically by means of an image sensor, or chemically by means of a light-sensitive material such as photographic film. It i ...
, exposure values are measured in terms of the binary logarithm of the amount of light reaching the film or sensor, in accordance with the Weber–Fechner law describing a logarithmic response of the human visual system to light. A single stop of exposure is one unit on a base- logarithmic scale.. More precisely, the exposure value of a photograph is defined as :\log_2 \frac where is the
f-number In optics, the f-number of an optical system such as a camera lens is the ratio of the system's focal length to the diameter of the entrance pupil ("clear aperture").Smith, Warren ''Modern Optical Engineering'', 4th Ed., 2007 McGraw-Hill ...
measuring the
aperture In optics, an aperture is a hole or an opening through which light travels. More specifically, the aperture and focal length of an optical system determine the cone angle of a bundle of rays that come to a focus in the image plane. An ...
of the lens during the exposure, and is the number of seconds of exposure. Binary logarithms (expressed as stops) are also used in densitometry, to express the dynamic range of light-sensitive materials or digital sensors.


Calculation


Conversion from other bases

An easy way to calculate on
calculator An electronic calculator is typically a portable electronic device used to perform calculations, ranging from basic arithmetic to complex mathematics. The first solid-state electronic calculator was created in the early 1960s. Pocket-size ...
s that do not have a function is to use the
natural logarithm The natural logarithm of a number is its logarithm to the base of the mathematical constant , which is an irrational and transcendental number approximately equal to . The natural logarithm of is generally written as , , or sometimes, if ...
() or the
common logarithm 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 ...
( or ) functions, which are found on most
scientific calculator A scientific calculator is an electronic calculator, either desktop or handheld, designed to perform mathematical operations. They have completely replaced slide rules and are used in both educational and professional settings. In some area ...
s. To change the logarithm base from or to one can use the formulae: :\log_2 n = \frac = \frac, or approximately :\log_2 n \approx 1.442695\ln n \approx 3.321928\log_ n.


Integer rounding

The binary logarithm can be made into a function from integers and to integers by
rounding Rounding means replacing a number with an approximate value that has a shorter, simpler, or more explicit representation. For example, replacing $ with $, the fraction 312/937 with 1/3, or the expression with . Rounding is often done to obta ...
it up or down. These two forms of integer binary logarithm are related by this formula: : \lfloor \log_2(n) \rfloor = \lceil \log_2(n + 1) \rceil - 1, \textn \ge 1. The definition can be extended by defining \lfloor \log_2(0) \rfloor = -1. Extended in this way, this function is related to the
number of leading zeros In computer software and hardware, find first set (ffs) or find first one is a bit operation that, given an unsigned machine word, designates the index or position of the least significant bit set to one in the word counting from the least signifi ...
of the 32-bit unsigned binary representation of , . :\lfloor \log_2(n) \rfloor = 31 - \operatorname(n). The integer binary logarithm can be interpreted as the zero-based index of the most significant bit in the input. In this sense it is the complement of the find first set operation, which finds the index of the least significant bit. Many hardware platforms include support for finding the number of leading zeros, or equivalent operations, which can be used to quickly find the binary logarithm. The fls and flsl functions in the
Linux kernel The Linux kernel is a free and open-source, monolithic, modular, multitasking, Unix-like operating system kernel. It was originally authored in 1991 by Linus Torvalds for his i386-based PC, and it was soon adopted as the kernel for the GNU ...
and in some versions of the
libc The C standard library or libc is the standard library for the C programming language, as specified in the ISO C standard. ISO/ IEC (2018). '' ISO/IEC 9899:2018(E): Programming Languages - C §7'' Starting from the original ANSI C standard, it wa ...
software library also compute the binary logarithm (rounded up to an integer, plus one).


Iterative approximation

For a general positive real number, the binary logarithm may be computed in two parts.. First, one computes the integer part, \lfloor\log_2 x\rfloor (called the characteristic of the logarithm). This reduces the problem to one where the argument of the logarithm is in a restricted range, the interval , simplifying the second step of computing the fractional part (the mantissa of the logarithm). For any , there exists a unique integer such that , or equivalently . Now the integer part of the logarithm is simply , and the fractional part is . In other words: :\log_2 x = n + \log_2 y \quad\text y = 2^x \text y \in ,2) For normalized floating-point numbers, the integer part is given by the floating-point exponent, and for integers it can be determined by performing a count leading zeros operation.. The fractional part of the result is and can be computed iteratively, using only elementary multiplication and division. The algorithm for computing the fractional part can be described in
pseudocode In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
as follows: # Start with a real number in the half-open interval . If , then the algorithm is done, and the fractional part is zero. # Otherwise, square repeatedly until the result lies in the interval . Let be the number of squarings needed. That is, with chosen such that is in . # Taking the logarithm of both sides and doing some algebra: \begin \log_2 z &= 2^m \log_2 y \\ \log_2 y &= \frac \\ &= \frac \\ &= 2^ + 2^\log_2(z/2). \end # Once again is a real number in the interval . Return to step 1 and compute the binary logarithm of using the same method. The result of this is expressed by the following recursive formulas, in which m_i is the number of squarings required in the ''i''-th iteration of the algorithm: \begin \log_2 x &= n + 2^ \left( 1 + 2^ \left( 1 + 2^ \left( 1 + \cdots \right)\right)\right) \\ &= n + 2^ + 2^ + 2^ + \cdots \end In the special case where the fractional part in step 1 is found to be zero, this is a ''finite'' sequence terminating at some point. Otherwise, it is an infinite series that converges according to the ratio test, since each term is strictly less than the previous one (since every ). For practical use, this infinite series must be truncated to reach an approximate result. If the series is truncated after the -th term, then the error in the result is less than .


Software library support

The log2 function is included in the standard C mathematical functions. The default version of this function takes double precision arguments but variants of it allow the argument to be single-precision or to be a long double. In computing environments supporting
complex numbers In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the for ...
and implicit type conversion such as
MATLAB MATLAB (an abbreviation of "MATrix LABoratory") is a proprietary multi-paradigm programming language and numeric computing environment developed by MathWorks. MATLAB allows matrix manipulations, plotting of functions and data, implementa ...
the argument to the log2 function is allowed to be a
negative number In mathematics, a negative number represents an opposite. In the real number system, a negative number is a number that is inequality (mathematics), less than 0 (number), zero. Negative numbers are often used to represent the magnitude of a loss ...
, returning a complex one..


References


External links

* *{{citation, url=http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog, title=Find the log base 2 of an N-bit integer in O(lg(N)) operations, work=Bit Twiddling Hacks, first=Sean Eron, last=Anderson, publisher=Stanford University, date=December 12, 2003, access-date=2015-11-25
Feynman and the Connection Machine
Binary arithmetic Calculus Logarithms