
In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, the binary logarithm () is the
power to which the number must be
raised to obtain the value . That is, for any real number ,
:
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 of a number is the exponent by which another fixed value, the base, must be raised to produce that number. For example, the logarithm of to base is , because is to the rd power: . More generally, if , the ...
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 2, two as the Base (exponentiation), base and integer as the exponent. In the fast-growing hierarchy, is exactly equal to f_1^ ...
function. There are several alternatives to the notation for the binary logarithm; see the
Notation
In linguistics and semiotics, a notation system is a system of graphics or symbols, Character_(symbol), characters and abbreviated Expression (language), expressions, used (for example) in Artistic disciplines, artistic and scientific disciplines ...
section below.
Historically, the first application of binary logarithms was in
music theory
Music theory is the study of theoretical frameworks for understanding the practices and possibilities of music. ''The Oxford Companion to Music'' describes three interrelated uses of the term "music theory": The first is the "Elements of music, ...
, by
Leonhard Euler
Leonhard Euler ( ; ; ; 15 April 170718 September 1783) was a Swiss polymath who was active as a mathematician, physicist, astronomer, logician, geographer, and engineer. He founded the studies of graph theory and topology and made influential ...
: the binary logarithm of a frequency ratio of two musical tones gives the number of
octave
In music, an octave (: eighth) or perfect octave (sometimes called the diapason) is an interval between two notes, one having twice the frequency of vibration of the other. The octave relationship is a natural phenomenon that has been referr ...
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 for representing numbers that uses only two symbols for the natural numbers: typically "0" ( zero) and "1" ( one). A ''binary number'' may als ...
, or the number of
bits needed to encode a message in
information theory
Information theory is the mathematical study of the quantification (science), quantification, Data storage, storage, and telecommunications, communication of information. The field was established and formalized by Claude Shannon in the 1940s, ...
. In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, 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 as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
,
bioinformatics
Bioinformatics () is an interdisciplinary field of science that develops methods and Bioinformatics software, software tools for understanding biological data, especially when the data sets are large and complex. Bioinformatics uses biology, ...
, the design of sports
tournament
A tournament is a competition involving at least three competitors, all participating in a sport or game. More specifically, the term may be used in either of two overlapping senses:
# One or more competitions held at a single venue and concen ...
s, and
photography
Photography is the visual arts, art, application, and practice of creating 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 is empl ...
.
Binary logarithms are included in the standard
C mathematical functions
C mathematical operations are a group of functions in the standard library of the C programming language implementing basic mathematical functions. Different C standards provide different, albeit backwards-compatible, sets of functions. Most of ...
and other mathematical software packages.
History
The
powers 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 the fast-growing hierarchy, is exactly equal to f_1^n(1). In the Hardy hi ...
have been known since antiquity; for instance, they appear in
Euclid's ''Elements'', Props. IX.32 (on the
factorization
In mathematics, factorization (or factorisation, see American and British English spelling differences#-ise, -ize (-isation, -ization), English spelling differences) or factoring consists of writing a number or another mathematical object as a p ...
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 proper divisors, that is, divisors excluding the number itself. For instance, 6 has proper divisors 1, 2 and 3, and 1 + 2 + 3 = 6, so 6 is a perfec ...
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 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 (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
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 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 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 polymath who was active as a mathematician, physicist, astronomer, logician, geographer, and engineer. He founded the studies of graph theory and topology and made influential ...
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 2, two as the Base (exponentiation), base and integer as the exponent. In the fast-growing hierarchy, is exactly equal to f_1^ ...
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 measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...
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 a logarithm, base of the e (mathematical constant), mathematical constant , which is an Irrational number, irrational and Transcendental number, transcendental number approxima ...
, 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:
:
:
:
For more, see
list of logarithmic identities.
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'' (''CMOS'') is a style guide for American English published since 1906 by the University of Chicago Press. Its 18 editions (the most recent in 2024) have prescribed writing and citation styles widely used in publ ...
''.
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist and mathematician. He is a professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of comp ...
credits this notation to a suggestion of
Edward Reingold,
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 languages, Italic branch of the Indo-European languages. Latin was originally spoken by the Latins (Italic tribe), Latins in Latium (now known as Lazio), the lower Tiber area aroun ...
''
logarithmus dualis''
[ or ''logarithmus dyadis''.][
The , ]ISO 31-11
ISO 31-11:1992 was the part of international standard ISO 31 that defines ''mathematical signs and symbols for use in physical sciences and technology''. It was superseded in 2009 by ISO 80000-2:2009 and subsequently revised in 2019 as ISO-80000 ...
and ISO 80000-2 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 (aka "standard logarithm") is the logarithm with base 10. It is also known as the decadic logarithm, the decimal logarithm and the Briggsian logarithm. The name "Briggsian logarithm" is in honor of the British ...
.
Applications
Information theory
The number of digits ( bits) in the binary representation of a positive integer is the integral part
In mathematics, an integral is the continuous analog of a sum, which is used to calculate areas, volumes, and their generalizations. Integration, the process of computing an integral, is one of the two fundamental operations of calculus,Int ...
of , i.e.[
:
In information theory, the definition of the amount of ]self-information
In information theory, the information content, self-information, surprisal, or Shannon information is a basic quantity derived from the probability of a particular event occurring from a random variable. It can be thought of as an alternative w ...
and information entropy
In information theory, the entropy of a random variable quantifies the average level of uncertainty or information associated with the variable's potential states or possible outcomes. This measures the expected amount of information needed ...
is often expressed with the binary logarithm, corresponding to making the bit the fundamental unit of information
A unit of information is any unit of measure of digital data size. In digital computing, a unit of information is used to describe the capacity of a digital data storage device. In telecommunications, a unit of information is used to describe the ...
. With these units, the Shannon–Hartley theorem
In information theory, the Shannon–Hartley theorem tells the maximum rate at which information can be transmitted over a communications channel of a specified bandwidth in the presence of noise. It is an application of the noisy-channel coding ...
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 a logarithm, base of the e (mathematical constant), mathematical constant , which is an Irrational number, irrational and Transcendental number, transcendental number approxima ...
and the nat 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 is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
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 ( ...
, the binary logarithm has several applications in combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
:
*Every binary tree
In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the ''left child'' and the ''right child''. That is, it is a ''k''-ary tree with . A recursive definition using set theor ...
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 2, two as the Base (exponentiation), base and integer as the exponent. In the fast-growing hierarchy, is exactly equal to f_1^ ...
and the tree is a complete binary tree
In computer science, a binary tree is a Tree (data structure), tree data structure in which each node has at most two child node, children, referred to as the ''left child'' and the ''right child''. That is, it is a m-ary tree, ''k''-ary tree wi ...
. Relatedly, the Strahler number
In mathematics, the Strahler number or Horton–Strahler number of a mathematical tree (graph theory), tree is a numerical measure of its branching complexity.
These numbers were first developed in hydrology, as a way of measuring the complexity ...
of a river system with tributary streams is at most .
*Every family of sets
In set theory and related branches of mathematics, a family (or collection) can mean, depending upon the context, any of the following: set, indexed set, multiset, or class. A collection F of subsets of a given set S is called a family of su ...
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 po ...
.
*Every partial cube 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 cubical graph, cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube.
has ...
.
*According to Ramsey's theorem, every -vertex undirected graph
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
has either a clique 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
In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that r ...
,[ 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 Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
s and data structure
In computer science, a data structure is a data organization 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 relationships amo ...
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 tree, rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left ...
containing elements has height .
The running time of an algorithm is usually expressed in big O notation
Big ''O'' notation is a mathematical notation that describes the asymptotic analysis, limiting behavior of a function (mathematics), function when the Argument of a function, argument tends towards a particular value or infinity. Big O is a memb ...
, 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. Some examples of algorithms with running time or are:
* Average time quicksort and other comparison sort 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 tree, rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left ...
s
* Exponentiation by squaring
* Longest increasing subsequence
Binary logarithms also occur in the exponents of the time bounds for some divide and conquer algorithms, such as the Karatsuba algorithm
The Karatsuba algorithm is a fast multiplication algorithm for integers. It was discovered by Anatoly Karatsuba in 1960 and published in 1962.
Knuth D.E. (1969) '' The Art of Computer Programming. v.2.'' Addison-Wesley Publ.Co., 724 pp ...
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 of science that develops methods and Bioinformatics software, software tools for understanding biological data, especially when the data sets are large and complex. Bioinformatics uses biology, ...
, microarray
A microarray is a multiplex (assay), multiplex lab-on-a-chip. Its purpose is to simultaneously detect the expression of thousands of biological interactions. It is a two-dimensional array on a Substrate (materials science), solid substrate—usu ...
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
A scatter plot, also called a scatterplot, scatter graph, scatter chart, scattergram, or scatter diagram, is a type of plot or mathematical diagram using Cartesian coordinates to display values for typically two variables for a set of dat ...
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
Music theory is the study of theoretical frameworks for understanding the practices and possibilities of music. ''The Oxford Companion to Music'' describes three interrelated uses of the term "music theory": The first is the "Elements of music, ...
, 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 (for example,
The set of all ...
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 (: eighth) or perfect octave (sometimes called the diapason) is an interval between two notes, one having twice the frequency of vibration of the other. The octave relationship is a natural phenomenon that has been referr ...
, 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 minor second, 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 ...
s of cents each). Mathematically, given tones with frequencies and , the number of cents in the interval from to is[
:
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 a match-up is immediately eliminated from the tournament. Each winner will play another in the next round, until the final match-up, ...
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
A Swiss-system tournament is a non-eliminating tournament format that features a fixed number of rounds of competition, but considerably fewer than for a round-robin tournament; thus each competitor (team or individual) does not play all the other ...
.
Photography
In photography
Photography is the visual arts, art, application, and practice of creating 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 is empl ...
, exposure value
In photography, exposure value (EV) is a number that represents a combination of a camera's shutter speed and f-number, such that all combinations that yield the same exposure (photography), exposure have the same EV (for any fixed scene luminanc ...
s 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
The Weber–Fechner laws are two related scientific law, scientific laws in the field of psychophysics, known as Weber's law and Fechner's law. Both relate to human perception, more specifically the relation between the actual change in a physica ...
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
:
where is the f-number
An f-number is a measure of the light-gathering ability of an optical system such as a camera lens. It is calculated by dividing the system's focal length by the diameter of the entrance pupil ("clear aperture").Smith, Warren ''Modern Optical ...
measuring the aperture
In optics, the aperture of an optical system (including a system consisting of a single lens) is the hole or opening that primarily limits light propagated through the system. More specifically, the entrance pupil as the front side image o ...
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
Dynamics (from Greek δυναμικός ''dynamikos'' "powerful", from δύναμις ''dynamis'' " power") or dynamic may refer to:
Physics and engineering
* Dynamics (mechanics), the study of forces and their effect on motion
Brands and ent ...
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-si ...
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 a logarithm, base of the e (mathematical constant), mathematical constant , which is an Irrational number, irrational and Transcendental number, transcendental number approxima ...
() or the common logarithm
In mathematics, the common logarithm (aka "standard logarithm") is the logarithm with base 10. It is also known as the decadic logarithm, the decimal logarithm and the Briggsian logarithm. The name "Briggsian logarithm" is in honor of the British ...
( or ) functions, which are found on most scientific calculator
A scientific calculator is an Electronics, electronic calculator, either desktop or handheld, designed to perform calculations using basic (addition, subtraction, multiplication, Division (mathematics), division) and advanced (Trigonometric fun ...
s. To change the logarithm base to 2 from , , or any other base , one can use the formulae
In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwe ...
:[
:
Approximately,
:
]
Integer rounding
The binary logarithm can be made into a function from integers and to integers by rounding
Rounding or rounding off is the process of adjusting a number to an approximate, more convenient value, often with a shorter or simpler representation. For example, replacing $ with $, the fraction 312/937 with 1/3, or the expression √2 with ...
it up or down. These two forms of integer binary logarithm are related by this formula:
:
The definition can be extended by defining . Extended in this way, this function is related to the number of leading zeros of the 32-bit unsigned binary representation of , .
:[
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
In computer software and hardware, find first set (ffs) or find first one is a bit operation that, given an unsigned Word (computer architecture), machine word, designates the index or position of the least significant bit set to one in the word c ...
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 software, free and open source Unix-like kernel (operating system), kernel that is used in many computer systems worldwide. The kernel was created by Linus Torvalds in 1991 and was soon adopted as the k ...
and in some versions of the libc
The C standard library, sometimes referred to as 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 origina ...
software library also compute the binary logarithm (rounded up to an integer, plus one).
Piecewise-linear approximation
For a number represented in floating point
In computing, floating-point arithmetic (FP) is arithmetic on subsets of real numbers formed by a ''significand'' (a signed sequence of a fixed number of digits in some base) multiplied by an integer power of that base.
Numbers of this form ...
as , with integer exponent and mantissa in the range , the binary logarithm can be roughly approximated as .[ This approximation is exact at both ends of the range of mantissas but underestimates the logarithm in the middle of the range, reaching a maximum error of approximately 0.086 at a mantissa of approximately 0.44. It can be made more accurate by using a ]piecewise linear function
In mathematics, a piecewise linear or segmented function is a real-valued function of a real variable, whose graph is composed of straight-line segments.
Definition
A piecewise linear function is a function defined on a (possibly unbounded) ...
of , or more crudely by adding a constant correction term . For instance choosing would halve the maximum error. The fast inverse square root
Fast inverse square root, sometimes referred to as or by the hexadecimal constant , is an algorithm that estimates \frac, the Multiplicative inverse, reciprocal (or multiplicative inverse) of the square root of a 32-bit floating-point number x i ...
algorithm uses this idea, with a different correction term that can be inferred to be , by directly manipulating the binary representation of to multiply this approximate logarithm by , obtaining a floating point value that approximates .
Iterative approximation
For a general positive real number, the binary logarithm may be computed in two parts.[.]
First, one computes the integer part
In mathematics, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least integer greater than or eq ...
, (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:
:
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 description of the steps in an algorithm using a mix of conventions of programming languages (like assignment operator, conditional operator, loop) with informal, usually self-explanatory, notation of actio ...
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:
# 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 is the number of squarings required in the ''i''-th iteration of the algorithm:
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
In mathematics, a series is, roughly speaking, an addition of infinitely many terms, one after the other. The study of series is a major part of calculus and its generalization, mathematical analysis. Series are used in most areas of mathemati ...
that converges according to the ratio test
In mathematics, the ratio test is a convergence tests, test (or "criterion") for the convergent series, convergence of a series (mathematics), series
:\sum_^\infty a_n,
where each term is a real number, real or complex number and is nonzero wh ...
, since each term is strictly less than the previous one (since every ). See Horner's method
In mathematics and computer science, Horner's method (or Horner's scheme) is an algorithm for polynomial evaluation. Although named after William George Horner, this method is much older, as it has been attributed to Joseph-Louis Lagrange by Hor ...
. 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
C mathematical operations are a group of functions in the standard library of the C programming language implementing basic mathematical functions. Different C standards provide different, albeit backwards-compatible, sets of functions. Most of ...
. The default version of this function takes double precision
Double-precision floating-point format (sometimes called FP64 or float64) is a floating-point arithmetic, floating-point computer number format, number format, usually occupying 64 Bit, bits in computer memory; it represents a wide range of numeri ...
arguments but variants of it allow the argument to be single-precision or to be a long double
In C and related programming languages, long double refers to a floating-point data type that is often more precise than double precision though the language standard only requires it to be at least as precise as double. As with C's other float ...
. 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 form a ...
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, implementat ...
the argument to the log2
function is allowed to be a negative number
In mathematics, a negative number is the opposite (mathematics), opposite of a positive real number. Equivalently, a negative number is a real number that is inequality (mathematics), less than 0, zero. Negative numbers are often used to represe ...
, 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