In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, the binary logarithm (log₂ n) is the logarithm

Logarithm

The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...

 to the base 2

Binary numeral system

The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...

. It is the inverse function

Inverse function

In mathematics, an inverse function is a function that undoes another function: If an input x into the function ƒ produces an output y, then putting y into the inverse function g produces the output x, and vice versa. i.e., ƒ=y, and g=x...

 of n ↦ 2ⁿ. The binary logarithm of n is the power to which the number 2 must be raised to obtain the value n. This makes the binary logarithm useful for anything involving powers of 2, i.e. doubling. For example, the binary logarithm of 1 is 0, the binary logarithm of 2 is 1, the binary logarithm of 4 is 2, the binary logarithm of 8 is 3, the binary logarithm of 16 is 4 and the binary logarithm of 32 is 5.

Information theory

The binary logarithm is often used in computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

 and information theory

Information theory

Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...

 because it is closely connected to the binary numeral system

Binary numeral system

The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...

. It is frequently written ld n, from Latin

Latin

Latin is an Italic language originally spoken in Latium and Ancient Rome. It, along with most European languages, is a descendant of the ancient Proto-Indo-European language. Although it is considered a dead language, a number of scholars and members of the Christian clergy speak it fluently, and...

 logarithmus duālis, or lg n, although the ISO

ISO 31-11

ISO 31-11 was the part of international standard ISO 31 that defines mathematical signs and symbols for use in physical sciences and technology...

 specification is that it should be lb (n), lg (n) being reserved for log₁₀ n. The number of digits (bit

Bit

A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...

s) in the binary representation of a positive integer n is the integral part of 1 + lb n, i.e.


In information theory, the definition of the amount of self-information

Self-information

In information theory, self-information is a measure of the information content associated with the outcome of a random variable. It is expressed in a unit of information, for example bits,nats,or...

 and information entropy

Information entropy

In information theory, entropy is a measure of the uncertainty associated with a random variable. In this context, the term usually refers to the Shannon entropy, which quantifies the expected value of the information contained in a message, usually in units such as bits...

 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.

Computational complexity

The binary logarithm also frequently appears in the analysis of algorithms

Analysis of algorithms

To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...

. 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 lb n. This idea is used in the analysis of several algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s and data structure

Data structure

In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...

s. For example, in binary search, the size of the problem to be solved is halved with each iteration, and therefore roughly lb n iterations are needed to obtain a problem of size 1, which is solved easily in constant time. Similarly, a perfectly balanced binary search tree

Binary search tree

In computer science, a binary search tree , which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structurewhich has the following properties:...

 containing n elements has height lb n + 1.

However, the running time of an algorithm is usually expressed in big O notation

Big O notation

In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...

, ignoring constant factors. Since log₂ n = (1/log_k 2)log_k n, where k can be any number greater than 1, algorithms that run in O(log₂ n) time can also be said to run in, say, O(log₁₃ 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^lb 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 lb n are sometimes called linearithmic. Some examples of algorithms with running time O(lb n) or O(n lb n) are:

• average time quicksort
• binary search tree
  Binary search tree
  In computer science, a binary search tree , which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structurewhich has the following properties:...
  
  s
• merge sort
  Merge sort
  Merge sort is an O comparison-based sorting algorithm. Most implementations produce a stable sort, meaning that the implementation preserves the input order of equal elements in the sorted output. It is a divide and conquer algorithm...
  
  
• Monge array
  Monge array
  In computer science, Monge arrays, or Monge matrices, are mathematical objects named for their discoverer, the French mathematician Gaspard Monge....
  
   calculation

Using calculators

An easy way to calculate the log₂(n) on calculator

Calculator

An electronic calculator is a small, portable, usually inexpensive electronic device used to perform the basic operations of arithmetic. Modern calculators are more portable than most computers, though most PDAs are comparable in size to handheld calculators.The first solid-state electronic...

s that do not have a log₂-function is to use the natural logarithm

Natural logarithm

The natural logarithm is the logarithm to the base e, where e is an irrational and transcendental constant approximately equal to 2.718281828...

 "ln" or the common logarithm

Common logarithm

The common logarithm is the logarithm with base 10. It is also known as the decadic logarithm, named after its base. It is indicated by log10, or sometimes Log with a capital L...

 "log" functions, which are found on most "scientific calculators". The specific change of logarithm base formulae for this are:

log₂(n) = ln(n)/ln(2) = log(n)/log(2)

so

log₂(n) = log_e(n)×1.442695... = log₁₀(n)×3.321928...

and this produces the curiosity that log₂(n) is within 0.6% of log_e(n) + log₁₀(n). log_e(n)+log₁₀(n) is actually log_2.0081359...(n) where the base is e^{1/(1+log₁₀e)} = 10^{1/(1 + log_e10)} ≈ 2.00813 59293 46243 95422 87563 25191 0 to (32 significant figures). Of course, log₁₀10 = log_ee = 1.

Integer

For integer domain

Domain (mathematics)

In mathematics, the domain of definition or simply the domain of a function is the set of "input" or argument values for which the function is defined...

 and range

Range (mathematics)

In mathematics, the range of a function refers to either the codomain or the image of the function, depending upon usage. This ambiguity is illustrated by the function f that maps real numbers to real numbers with f = x^2. Some books say that range of this function is its codomain, the set of all...

, the binary logarithm can be computed rounding

Rounding

Rounding a numerical value means replacing it by another value that is approximately equal but has a shorter, simpler, or more explicit representation; for example, replacing $23.4476 with $23.45, or the fraction 312/937 with 1/3, or the expression √2 with 1.414.Rounding is often done on purpose to...

 up or down. These two forms of integer binary logarithm are related by this formula:

The definition can be extended by defining . This function is related to the number of leading zeros of the 32-bit unsigned binary representation of x, nlz(x).

The following example code, slightly altered, in the C language

C (programming language)

C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....

 computes the binary logarithm (rounding down) of an integer. The operator >> represents "unsigned right shift

Logical shift

In computer science, a logical shift is a bitwise operation that shifts all the bits of its operand. Unlike an arithmetic shift, a logical shift does not preserve a number's sign bit or distinguish a number's exponent from its mantissa; every bit in the operand is simply moved a given number of bit...

". The rounding down form of binary logarithm is identical to computing the position of the most significant 1 bit.

/**
* Returns the floor form of binary logarithm for a 32 bit integer.
* −1 is returned if n is 0.
*/
int floorLog2(unsigned int n) {
if (n 0)
return -1;

int pos = 0;
if (n >= (1 <<16)) { n >>= 16; pos += 16; }
if (n >= (1 << 8)) { n >>= 8; pos += 8; }
if (n >= (1 << 4)) { n >>= 4; pos += 4; }
if (n >= (1 << 2)) { n >>= 2; pos += 2; }
if (n >= (1 << 1)) { pos += 1; }
return pos;
}

Real number

For a general positive real number, the binary logarithm may be computed in two parts:

1. Compute the integer
   Integer
   The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
   
    part,
2. Compute the fractional part

Computing the integral part is straightforward. For any x > 0, there exists a unique integer n such that 2ⁿ ≤ x < 2ⁿ⁺¹, or equivalently 1 ≤ 2⁻ⁿx < 2. Now the integral part of the logarithm is simply n, and the fractional part is lb(2⁻ⁿx). In other words:


The fractional part of the result is , and can be computed recursively

Recursion

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...

, using only elementary multiplication and division. To compute the fractional part:

1. We start with a real number . If , then we are done and the fractional part is zero.
2. Otherwise, square repeatedly until the result is . Let be the number of squarings needed. That is, with chosen such that .
3. Taking the logarithm of both sides and doing some algebra:

   

   1. Notice that is once again a real number in the interval .
   2. Return to step 1, and compute the binary logarithm of using the same method recursively.

   
   
   The result of this is expressed by the following formulas, in which is the number of squarings required in the i-th recursion 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 which 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 i-th term, then the error in the result is less than .
   Example code
   The following Python

   Python (programming language)

   Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...

   
    program computes the binary logarithm using the recursive method outlined above, showing the steps along the way:
   (This code fails when finding the binary logarithm of any number 2^n where n is any integer.)
   
   
   def lg(x):
   ip = 0
   rem = x
   
   # Integer part
   while rem<1:
   ip -= 1
   rem *= 2
   while rem>=2:
   ip += 1
   rem /= 2
   print("lg(%g) = %d + lg(%g)" % (x, ip, rem)) # Brackets required for Python 3
   
   # Fractional part
   res = ip + frac_lg(rem)
   
   return res
   
   def frac_lg(x, fp=1.0, tol=1e-10):
   assert 1<=x<2
   
   # terminate the recursion if we're close enough
   if fp return 0
   
   # square until >= 2
   rem = x
   m = 0
   while rem < 2:
   m += 1
   fp /= 2
   rem *= rem
   
   # now:
   # rem = x**2**m, fp = 2**-m
   # => lg(rem) = lg(x)*2**m = lg(x)/fp
   # => lg(x) = fp * ( lg(rem/2) + 1 )
   # = fp + fp*lg(rem/2)
   # time for recursion!
   
   print("lg(x=%g) \t= 2**%d * ( 1 + lg(%g) )" % (x, -m, rem/2))
   return fp + frac_lg(rem/2, fp)
   
   if __name__ '__main__':
   value = 4.5
   print " X =", value
   result = lg(value)
   print("lg(X) =", result)# Brackets required for Python 3
   

   1. Sample output
   2. $ python log2.py
   3. X = 4.5
   4. lg(4.5) = 2 + lg(1.125)
   5. lg(x=1.125) = 2**-3 * ( 1 + lg(1.28289) )
   6. lg(x=1.28289) = 2**-2 * ( 1 + lg(1.35435) )
   7. lg(x=1.35435) = 2**-2 * ( 1 + lg(1.68226) )
   8. lg(x=1.68226) = 2**-1 * ( 1 + lg(1.415) )
   9. lg(x=1.415) = 2**-1 * ( 1 + lg(1.00111) )
   10. lg(x=1.00111) = 2**-10 * ( 1 + lg(1.55742) )
   11. lg(x=1.55742) = 2**-1 * ( 1 + lg(1.21278) )
   12. lg(x=1.21278) = 2**-2 * ( 1 + lg(1.08166) )
   13. lg(x=1.08166) = 2**-4 * ( 1 + lg(1.75563) )
   14. lg(x=1.75563) = 2**-1 * ( 1 + lg(1.54113) )
   15. lg(x=1.54113) = 2**-1 * ( 1 + lg(1.18753) )
   16. lg(x=1.18753) = 2**-3 * ( 1 + lg(1.97759) )
   17. lg(x=1.97759) = 2**-1 * ( 1 + lg(1.95543) )
   18. lg(x=1.95543) = 2**-1 * ( 1 + lg(1.91185) )
   19. lg(x=1.91185) = 2**-1 * ( 1 + lg(1.82758) )
   20. lg(X) = 2.16992500139

   
   
   
   Since Python does not optimize tail recursion, this can be implemented more efficiently with iteration

   Iteration

   Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration," and the results of one iteration are used as the starting point for the next iteration.-Mathematics:Iteration in...

   
   . Here is an iterative version of the same algorithm in Perl

   Perl

   Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...

   
   :
   
   
   sub lg {
   my $x = shift;
   my $tol = shift || 1e-13;
   my $res = 0.0;
   
   while ($x < 1) {
   $res -= 1;
   $x *= 2;
   }
   while ($x >= 2) {
   $res += 1;
   $x /= 2;
   }
   my $fp = 1.0;
   while ($fp >= $tol) {
   $fp /= 2;
   $x *= $x;
   if ($x >= 2) {
   $x /= 2;
   $res += $fp;
   }
   }
   $res
   }
   
   printf "x = %g\nlg(x) = %g\n", 4.5, lg(4.5);
   
   

   See also

   • Natural logarithm
     Natural logarithm
     The natural logarithm is the logarithm to the base e, where e is an irrational and transcendental constant approximately equal to 2.718281828...
     
      (base e
     E (mathematical constant)
     The mathematical constant ' is the unique real number such that the value of the derivative of the function at the point is equal to 1. The function so defined is called the exponential function, and its inverse is the natural logarithm, or logarithm to base...
     
     )
   • Common logarithm
     Common logarithm
     The common logarithm is the logarithm with base 10. It is also known as the decadic logarithm, named after its base. It is indicated by log10, or sometimes Log with a capital L...
     
     (base 10)

   The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.