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...
, division by two or halving has also been called mediation or dimidiation. The treatment of this as a different operation from multiplication and division by other numbers goes back to the ancient Egyptians, whose multiplication algorithm
Ancient Egyptian multiplication
In mathematics, ancient Egyptian multiplication , one of two multiplication methods used by scribes, was a systematic method for multiplying two numbers that does not require the multiplication table, only the ability to multiply and divide by 2, and...
used division by two as one of its fundamental steps.
Some mathematicians as late as the sixteenth century continued to view halving as a separate operation, and it often continues to be treated separately in modern computer programming
Computer programming
Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
.
Performing this operation is simple in decimal arithmetic, in 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...
used in computer programming, and in other even-numbered base
Numeral system
A numeral system is a writing system for expressing numbers, that is a mathematical notation for representing numbers of a given set, using graphemes or symbols in a consistent manner....
s.
Binary
In binary arithmetic, division by two can be performed by a bit shift operation that shifts the number one place to the right.
This is a form of strength reduction
Strength reduction
Strength reduction is a compiler optimization where expensive operations are replaced with equivalent but less expensive operations. The classic example of strength reduction converts "strong" multiplications inside a loop into "weaker" additions – something that frequently occurs in array...
optimization. For example, 1101001 in binary (the decimal number 105), shifted one place to the right, is 110100 (the decimal number 52): the lowest order bit, a 1, is removed. Similarly, division by any power of two
Power of two
In mathematics, a power of two means a number of the form 2n where n is an integer, i.e. the result of exponentiation with as base the number two and as exponent the integer n....
2k may be performed by right-shifting k positions. Because bit shifts are often much faster operations than division, replacing a division by a shift in this way can be a helpful step in program optimization. However, for the sake of software portability
Software portability
Portability in high-level computer programming is the usability of the same software in different environments. The prerequirement for portability is the generalized abstraction between the application logic and system interfaces...
and readability, it is often best to write programs using the division operation and trust in the compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
to perform this replacement. An example from Common Lisp
Common Lisp
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
The above statements, however, are not always true when dealing with dividing signed
Signed number representations
In computing, signed number representations are required to encode negative numbers in binary number systems.In mathematics, negative numbers in any base are represented by prefixing them with a − sign. However, in computer hardware, numbers are represented in binary only without extra...
binary numbers. Shifting right by 1 bit will divide by two, always rounding down. However, in some languages, division of signed binary numbers round towards 0 (which, if the result is negative, means it rounds up). For example, Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
is one such language: in Java, -3 / 2 evaluates to -1, whereas -3 >> 1 evaluates to -2. So in this case, the compiler cannot optimize division by two by replacing it by a bit shift, when the dividend could possibly be negative.
Binary floating point
In binary floating-point arithmetic, division by two can be performed by decreasing the exponent by one (as long as the result is not a subnormal number). Many programming languages provide functions that can be used to divide a floating point number by a power of two. For example, the Java programming language
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
provides the method java.lang.Math.scalb for scaling by a power of two, and the C programming 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....
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...
is for decimal. However, it can be used as a model to construct an algorithm for taking half of any number N in any even
Even
-General:* Even , a Scandinavian male personal name* Even , an ethnic group from Siberia and Russian Far East**Even language, a language spoken by the Evens* Odd and Even, a solitaire card game which is played with two decks of playing cards...
base.
Write out N, putting a zero to its left.
Go through the digits of N in overlapping pairs, writing down digits of the result from the following table.
If first digit is
Even
Even
Even
Even
Even
Odd
Odd
Odd
Odd
Odd
And second digit is
0 or 1
2 or 3
4 or 5
6 or 7
8 or 9
0 or 1
2 or 3
4 or 5
6 or 7
8 or 9
Write
0
1
2
3
4
5
6
7
8
9
Example: 1738/2=?
Write 01738. We will now work on finding the result.
In mathematics, the parity of an object states whether it is even or odd.This concept begins with integers. An even number is an integer that is "evenly divisible" by 2, i.e., divisible by 2 without remainder; an odd number is an integer that is not evenly divisible by 2...
In probability theory and statistics, a median is described as the numerical value separating the higher half of a sample, a population, or a probability distribution, from the lower half. The median of a finite list of numbers can be found by arranging all the observations from lowest value to...
, a value that splits a set of data values into two equal subsets
In geometry, bisection is the division of something into two equal or congruent parts, usually by a line, which is then called a bisector. The most often considered types of bisectors are the segment bisector and the angle bisector In geometry, bisection is the division of something into two equal...
, the partition of a geometric object into two equal halves
In heraldry, dimidiation is a method of joining two coats of arms.For a time, dimidiation preceded the method known as impalement. Whereas impalement involves placing the whole of both coats of arms side by side in the same shield, dimidiation involves placing the dexter half of one coat of arms...
, a heraldic method of joining two coats of arms by splitting their designs into halves
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
