division by two
{{Short description|None}}
File:Orange_sliced_in_half.jpg
In mathematics, division by two or halving has also been called mediation or dimidiation.{{citation|title=The Earliest arithmetics in English|volume=118|series=Early English Text Society|first=Robert|last=Steele|publisher=Oxford University Press|year=1922|page=82}}. The treatment of this as a different operation from multiplication and division by other numbers goes back to the ancient Egyptians, whose multiplication algorithm used division by two as one of its fundamental steps.{{citation|title=A history of algorithms: from the pebble to the microchip|first1=Jean-Luc|last1=Chabert|first2=Évelyne|last2=Barbin|publisher=Springer-Verlag|year=1999|isbn=978-3-540-63369-3|page=16}}.
Some mathematicians as late as the sixteenth century continued to view halving as a separate operation,{{citation|title=The educational significance of sixteenth century arithmetic from the point of view of the present time|volume=8|series=Contributions to education|first=Lambert Lincoln|last=Jackson|publisher=Columbia University|year=1906|page=76}}.{{citation|title=A Fifteenth Century French Algorism from Liége|journal=Isis|volume=12|issue=2|year=1929|first=E. G. R.|last=Waters|pages=194–236|jstor=224785|doi=10.1086/346408|s2cid=144157808}}. and it often continues to be treated separately in modern computer programming.{{citation|title=Software optimization for high-performance computing|first1=Kevin R.|last1=Wadleigh|first2=Isom L.|last2=Crawford|publisher=Prentice Hall|year=2000|page=[https://archive.org/details/softwareoptimiza0000wadl/page/92 92]|isbn=978-0-13-017008-8|url=https://archive.org/details/softwareoptimiza0000wadl/page/92}}.
Performing this operation is simple in decimal arithmetic, in the binary numeral system used in computer programming, and in other even-numbered bases. To divide an odd number by 2 use the mathematical solution ((N−1)÷2)+0.5. For example, if N=7, then ((7−1)÷2)+0.5=3.5, so 7÷2=3.5.
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 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 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 and readability, it is often best to write programs using the division operation and trust in the compiler to perform this replacement.{{citation|title=Write portable code: an introduction to developing software for multiple platforms|first=Brian|last=Hook|publisher=No Starch Press|year=2005|isbn=978-1-59327-056-8|page=133}}. An example from Common Lisp:
(setq number #b1101001) ; #b1101001 — 105
(ash number -1) ; #b0110100 — 105 >> 1 ⇒ 52
(ash number -4) ; #b0000110 — 105 >> 4 ≡ 105 / 2⁴ ⇒ 6
The above statements, however, are not always true when dealing with dividing signed 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 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 provides the method java.lang.Math.scalb for scaling by a power of two,{{cite web
|url=http://java.sun.com/javase/6/docs/api/java/lang/Math.html#scalb(double,%20int)
|title=Math.scalb
|work=Java Platform Standard Ed. 6
|accessdate=2009-10-11
}} and the C programming language provides the function ldexp for the same purpose.{{citation
|title=Programming languages — C, International Standard ISO/IEC 9899:1999
}}, Section 7.12.6.6.
Decimal
The following algorithm 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 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.
| class="wikitable" |
| 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.
- 01: even digit followed by 1, write 0.
- 17: odd digit followed by 7, write 8.
- 73: odd digit followed by 3, write 6.
- 38: odd digit followed by 8, write 9.
Result: 0869.
From the example one can see that 0 is even.
If the last digit of N is odd digit one should add 0.5 to the result.
See also
- One half
- Median, a value that splits a set of data values into two equal subsets
- Bisection, the partition of a geometric object into two equal halves
- Dimidiation, a heraldic method of joining two coats of arms by splitting their designs into halves