# Binary logarithm

__NOTOC__

In

mathematics , the**binary logarithm**(log_{2}"n") is thelogarithm forbase 2 . It is theinverse function of $n\; mapsto\; 2^n$.The binary logarithm is often used in

computer science andinformation theory (where it is frequently written**lg "n**", or**ld "n**", fromLatin "logarithmus dualis" [although the ISO specification is that it should be**lb ("n")**, lg ("n") being reserved for log_{10}"n"] ), because it is closely connected to thebinary numeral system . The number of digits (bit s) in the binary representation of a positive integer "n" is the integral part of 1 + lg "n", i.e. :$lfloor\; lg\; n\; floor\; +\; 1.$In information theory, the definition of the amount ofself-information andinformation entropy involves the binary logarithm; this is needed because the unit of information, the bit, refers to information resulting from an occurrence of one of two equally probable alternatives.The binary logarithm also frequently appears in the

analysis of algorithms . If a number "n" greater than 1 is divided by 2 repeatedly, the number of iterations needed to get a value at most 1 is again the integral part of lg "n". This idea is used in the analysis of severalalgorithm s anddata structure s. For example, inbinary search , the size of the problem to be solved is halved with each iteration, and therefore roughly lg "n" iterations are needed to obtain a problem of size 1, which is solved easily in constant time. Similarly, a perfectly balancedbinary search tree containing "n" elements has height lg "n"+1.However, the running time of an algorithm is usually expressed in

big O notation , ignoring constant factors. Since log_{2}"n" = (1/log_{k}2)log_{k}"n", where "k" can be any number greater than 1, algorithms that run in "O"(log_{2}"n") time can also be said to run in, say, "O"(log_{13}"n") time. The base of the logarithm in expressions such as "O"(log "n") or "O"("n" log "n") is therefore not important.In other contexts, though, the base of the logarithm needs to be specified. For example "O"(2^{lg "n"}) is not the same as "O"(2^{ln "n"}) because the former is equal to "O"("n") and the latter to "O"("n"^{0.6931...}).Algorithms with running time "n" lg "n" are sometimes called

linearithmic . Some examples of algorithms with running time "O"(lg "n") or "O"("n" lg "n") are:*average time quicksort

*binary search tree s

*merge sort

*Monge array calculation**Using calculators**An easy way to calculate the log

_{2}("n") oncalculator s that do not have a log_{2}-function is to use thenatural logarithm "ln" or thecommon logarithm "log" functions, which are found on most "scientific calculators". The formulae for this are: :log_{2}("n") = ln("n")/ln(2) = log("n")/log(2)so :log_{2}("n") = log_{"e"}("n")×1.442695... = log_{10}("n")×3.321928... and this produces the curiosity that log_{2}("n") is within 0.6% of log_{"e"}("n")+log_{10}("n"). log_{"e"}("n")+log_{10}("n") is actually log_{2.008135929...}("n") where the base is "e"^{log10"e"(10)}**Algorithm****Integer**For integer domain and range, the binary logarithm can be computed

rounding up, or rounding down. These two forms of integer binary logarithm are related by this formula::$lfloor\; log\_2(n)\; floor\; =\; lceil\; log\_2(n\; +\; 1)\; ceil\; -\; 1,\; mbox\{where\; \}n\; ge\; 1.$ [

*Citation | title=Hacker's Delight | first1=Henry S. | last1=Warren Jr. | year=2002 | publisher=Addison Wesley | isbn=978-0201914658 | pages=pp. 83*]The following example code in the C language computes the binary logarithm (rounding down) of an integer, rounded down. [

*Citation | title=Hacker's Delight | first1=Henry S. | last1=Warren Jr. | year=2002 | publisher=Addison Wesley | isbn=978-0201914658 | pages=pp. 215*] The operator '>>' represents 'unsigned right shift'. The rounding down form of binary logarithm is identical to computing the position of the most significant 1 bit.**Real number**For a general

real number , the binary logarithm may be computed in two parts:

# Compute theinteger part, $lfloorlg(x)\; floor$

# Compute the fractional partComputing the integral part is straightforward. For any $x\; >\; 0$, there exists a unique integer $n$ such that $2^n\; leq\; x\; <\; 2^\{n+1\}$, or equivalently $1\; leq\; 2^\{-n\}x\; <\; 2$. Now the integral part of the logarithm is simply $n$, and the fractional part is $lg(2^\{-n\}x)$. In other words:

:$lg\; x\; =\; n\; +\; lg(y)\; quad\; ext\{where\; \}\; y\; =\; 2^\{-n\}x\; ext\{\; and\; \}\; y\; in\; [1,2)$

The fractional part of the result is $lg\; y$, and can be computed recursively, using only elementary multiplication and division. To compute the fractional part:

# We start with a real number $y\; in\; [1,2)$.

# Now square $y$ repeatedly until the result is $geq\; 2$. Call the result $z$, and let $m$ be the number of squarings needed.

# Now $z\; =\; y^\{2uparrow\; m\}$ and so $lg\; z\; =\; 2^m\; lg\; y$. Thus:

#:$lg\; y\; =\; frac\{\; lg\; z\; \}\{\; 2^m\; \}\; =\; frac\{\; 1\; +\; lg(z/2)\; \}\{\; 2^m\; \}$

#:$lg\; y\; =\; 2^\{-m\}\; +\; 2^\{-m\}lg(z/2)$

# Notice that $z/2$ is once again a real number in the interval $[1,2)$.

# If $z/2\; <\; 1+epsilon$ (where $epsilon$ is the desired precision), then $lg(z/2)approx\; 0$ and we are done. Otherwise, return to step 1, and compute the binary logarithm of $z/2$ using the same method recursively.The result of all of this is::$lg\; x\; =\; n\; +\; 2^\{-m\_1\}\; left(\; 1\; +\; 2^\{-m\_2\}\; left(\; 1\; +\; 2^\{-m\_3\}\; left(\; 1\; +\; cdots\; ight)\; ight)\; ight)$

After computing $m\_\{1ldots\; i\}$, the error in the result is less than $2^\{-(m\_1+m\_2+ldots+m\_i)\}$.

**Example code**The following Python computes the binary logarithm using the recursive method outlined above, showing the steps along the way: [

*adapted from [*]*http://en.literateprograms.org/Logarithm_Function_%28Python%29 Logarithm Function (Python)*]Since Python does not optimize

tail recursion , this can be implemented more efficiently withiteration . Here is an iterative version:# Integer part while x<1: res -= 1 x *= 2 while x>=2: res += 1 x /= 2

# Fractional part fp = 1.0 while fp>=tol: fp /= 2 x *= x if x >= 2: x /= 2 res += fp

return res

**References****ee also***

natural logarithm (base e),

*common logarithm (base 10)

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**binary logarithm**— noun The logarithm base two … Wiktionary**Logarithm**— The graph of the logarithm to base 2 crosses the x axis (horizontal axis) at 1 and passes through the points with coordinates (2, 1), (4, 2), and (8, 3) … Wikipedia**Binary entropy function**— In information theory, the binary entropy function, denoted H(p) , or H {mathrm b}(p) ,, is defined as the entropy of a Bernoulli trial with probability of success p . Mathematically, the Bernoulli trial is modelled as a random variable X that… … Wikipedia**Binary logarithms**— Logarithm Log a*rithm (l[o^]g [.a]*r[i^][th] m), n. [Gr. lo gos word, account, proportion + ariqmo s number: cf. F. logarithme.] (Math.) One of a class of auxiliary numbers, devised by John Napier, of Merchiston, Scotland (1550 1617), to abridge… … The Collaborative International Dictionary of English**Logarithm**— Log a*rithm (l[o^]g [.a]*r[i^][th] m), n. [Gr. lo gos word, account, proportion + ariqmo s number: cf. F. logarithme.] (Math.) One of a class of auxiliary numbers, devised by John Napier, of Merchiston, Scotland (1550 1617), to abridge… … The Collaborative International Dictionary of English**Binary**— Bi na*ry, a. [L. binarius, fr. bini two by two, two at a time, fr. root of bis twice; akin to E. two: cf. F. binaire.] Compounded or consisting of two things or parts; characterized by two (things). [1913 Webster] {Binary arithmetic}, that in… … The Collaborative International Dictionary of English**Binary arithmetic**— Binary Bi na*ry, a. [L. binarius, fr. bini two by two, two at a time, fr. root of bis twice; akin to E. two: cf. F. binaire.] Compounded or consisting of two things or parts; characterized by two (things). [1913 Webster] {Binary arithmetic}, that … The Collaborative International Dictionary of English**Binary compound**— Binary Bi na*ry, a. [L. binarius, fr. bini two by two, two at a time, fr. root of bis twice; akin to E. two: cf. F. binaire.] Compounded or consisting of two things or parts; characterized by two (things). [1913 Webster] {Binary arithmetic}, that … The Collaborative International Dictionary of English**Binary logarithms**— Binary Bi na*ry, a. [L. binarius, fr. bini two by two, two at a time, fr. root of bis twice; akin to E. two: cf. F. binaire.] Compounded or consisting of two things or parts; characterized by two (things). [1913 Webster] {Binary arithmetic}, that … The Collaborative International Dictionary of English**Binary measure**— Binary Bi na*ry, a. [L. binarius, fr. bini two by two, two at a time, fr. root of bis twice; akin to E. two: cf. F. binaire.] Compounded or consisting of two things or parts; characterized by two (things). [1913 Webster] {Binary arithmetic}, that … The Collaborative International Dictionary of English