Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere.... , the binary logarithm (log2n) is the logarithm
Logarithm
In mathematics, the logarithm of a number to a given base is the Power or exponent to which the base must be raised in order to produce the number.... for base 2. It is the inverse function
Inverse function
In mathematics, if ƒ is a function from A to B then an inverse function for ƒ is a function in the opposite direction, from B to A, with the property that a round trip from A to B to A returns each element of the initial set to itself.... of .
Information theory
The binary logarithm is often used in computer science
Computer science
Computer 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. Historically, information theory was developed by Claude E.... (where it is frequently written lg n, or ld n, from Latin
Latin
Latin is an Italic language, historically spoken in Latium and Ancient Rome. Through the Military history of the Roman Empire, Latin spread throughout the Mediterranean and a large part of Europe.... logarithmus dualis [although the ISO specification is that it should be lb (n), lg (n) being reserved for log10n] ), because it is closely connected to the binary numeral system
Binary numeral system
The binary numeral system, or notation with a radix of 2. Owing to its straightforward implementation in digital electronic circuitry using logic gates, the binary system is used internally by all modern computers.... .
Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere.... , the binary logarithm (log2n) is the logarithm
Logarithm
In mathematics, the logarithm of a number to a given base is the Power or exponent to which the base must be raised in order to produce the number.... for base 2. It is the inverse function
Inverse function
In mathematics, if ƒ is a function from A to B then an inverse function for ƒ is a function in the opposite direction, from B to A, with the property that a round trip from A to B to A returns each element of the initial set to itself.... of .
Computer 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. Historically, information theory was developed by Claude E.... (where it is frequently written lg n, or ld n, from Latin
Latin
Latin is an Italic language, historically spoken in Latium and Ancient Rome. Through the Military history of the Roman Empire, Latin spread throughout the Mediterranean and a large part of Europe.... logarithmus dualis [although the ISO specification is that it should be lb (n), lg (n) being reserved for log10n] ), because it is closely connected to the binary numeral system
Binary numeral system
The binary numeral system, or notation with a radix of 2. Owing to its straightforward implementation in digital electronic circuitry using logic gates, the binary system is used internally by all modern computers.... . The number of digits (bit
Bit
A bit is a binary numeral system numerical digit, taking a value of either 0 or 1. Binary digits are a basic unit of information Computer data storage and transmission in digital computing and digital information theory.... s) in the binary representation of a positive integer n is the integral part of 1 + lg 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 Units of measurement of information, for example bits,... and information entropy
Information entropy
In information theory, entropy is a measure of the uncertainty associated with a random variable. The term by itself in this context usually refers to the Shannon entropy, which quantifies, in the sense of an expected value, the self-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.
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 lg n. This idea is used in the analysis of several algorithm
Algorithm
In mathematics, computing, linguistics and related subjects, an algorithm is a sequence of finite instructions, often used for calculation and data processing.... s and data structure
Data structure
A data structure in computer science is a way of storing data in a computer so that it can be used efficiently. It is an organization of mathematical and logical concepts of data.... s. For example, in binary 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 balanced binary search tree
Binary search tree
In computer science, a binary search tree is a binary tree data structurewhich has the following properties:* Each node has a distinct value.... containing n elements has height lg n+1.
However, the running time of an algorithm is usually expressed in big O notation
Big O notation
In mathematics, big O notation describes the asymptotic analysis of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions.... , ignoring constant factors. Since log2n = (1/logk 2)logkn, where k can be any number greater than 1, algorithms that run in O(log2n) time can also be said to run in, say, O(log13n) 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(2lg n) is not the same as O(2ln n) because the former is equal to O(n) and the latter to O(n0.6931...).
Algorithms with running time n lg n are sometimes called linearithmic
Linearithmic
In computer science, a linearithmic function is a Function of the form n · log n .In terms of Big O notation, linearithmic is ?, o for every e > 0, and T.... . Some examples of algorithms with running time O(lg n) or O(n lg n) are:
Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, average performance, makes comparisons to sort n items. However, in the Best, worst and average case, it makes comparisons....
Merge sort or merge_sort is an Big O notation comparison sort sorting algorithm. In most implementations it is Sorting algorithm#Classification, meaning that it preserves the input order of equal elements in the sorted output....
Monge arrays, or Monge matrices, are mathematical objects used primarily in computer science. They are named for their discoverer, the French mathematician Gaspard Monge.... calculation
Using calculators
An easy way to calculate the log2(n) on calculator
Calculator
A calculator is a device for performing mathematical calculations, distinguished from a computer by having a limited problem solving ability and an interface optimized for interactive calculation rather than programming.... s that do not have a log2-function is to use the natural logarithm
Natural logarithm
The natural logarithm, formerly known as the hyperbolic logarithm, is the logarithm to the base e , where e is an irrational number 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 formulae
Logarithm
In mathematics, the logarithm of a number to a given base is the Power or exponent to which the base must be raised in order to produce the number.... for this are:
and this produces the curiosity that log2(n) is within 0.6% of loge(n)+log10(n). loge(n)+log10(n) is actually log2.008135929...(n) where the base is elog10e(10)
In mathematics, the domain of a given function is the set of "input" values for which the function is defined. For instance, the domain of cosine would be all real numbers, while the domain of the square root would be only numbers greater than or equal to 0 .... and range
Range (mathematics)
In mathematics, the range of a function is the Set of all "output" values produced by that function. Sometimes it is called the , or more precisely, the image of the domain of the function.... , the binary logarithm can be computed rounding
Rounding
Rounding involves reducing the number of significant digits in a number. The result of rounding is a "shorter" number having fewer non-zero digits yet similar in magnitude.... up, or rounding down. These two forms of integer binary logarithm are related by this formula:
C is a general-purpose computer programming language originally developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories to implement the Unix operating system.... computes the binary logarithm (rounding down) of an integer, rounded down. 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.
/**
* Returns the floor form of binary logarithm for a 32 bit integer.
* -1 is returned if n is 0.
*/
int floorLog2(unsigned int n)
In mathematics, the real numbers may be described informally in several different ways. The real numbers include both rational numbers, such as 42 and −23/129, and irrational numbers, such as pi and the square root of two; or, a real number can be given by an infinite decimal representation, such as 2.4871773339...., where the digits co... , the binary logarithm may be computed in two parts:
The integers are natural numbers including 0 and their negative and non-negative numberss . They are numbers that can be written without a fractional or decimal component, and fall within the set .... part,
Compute the fractional part
Computing the integral part is straightforward. For any , there exists a unique integer such that , or equivalently . Now the integral part of the logarithm is simply , and the fractional part is . In other words:
The fractional part of the result is , and can be computed recursively
Recursion
Recursion, in mathematics and computer science, is a method of defining Function in which the function being defined is applied within its own definition.... , using only elementary multiplication and division. To compute the fractional part:
We start with a real number .
Now square repeatedly until the result is . Call the result , and let be the number of squarings needed.
Now and so . Thus:
Notice that is once again a real number in the interval .
If (where is the desired precision), then and we are done. Otherwise, return to step 1, and compute the binary logarithm of using the same method recursively.
The result of all of this is:
After computing , the error in the result is less than .
Python is a general-purpose high-level programming language. Its design philosophy emphasizes code readability. Python's core syntax and semantics are Minimalism , while the standard library is large and comprehensive.... program computes the binary logarithm using the recursive method outlined above, showing the steps along the way:
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)
# 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 # square until >= 2
rem = x
m = 0
while rem < 2:
m += 1
fp /= 2
rem *= rem
In computer science, tail recursion is a special case of Recursion_ in which the last operation of the function, the tail call, is a recursive call.... , this can be implemented more efficiently with iteration
Iteration
Iteration means the act of repeating.... . Here is an iterative version:
def lg(x, tol=1e-13):
res = 0.0
# 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
The natural logarithm, formerly known as the hyperbolic logarithm, is the logarithm to the base e , where e is an irrational number constant approximately equal to 2.718281828.... (base e
E (mathematical constant)
The mathematical constant e is the unique real number such that the function ex has the same value as the derivative, for all values of x.... ),
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)
