Division by two

In mathematics, division by two or halving has also been called mediation or dimidiation.[1] 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.[2] Some mathematicians as late as the sixteenth century continued to view halving as a separate operation,[3][4] and it often continues to be treated separately in modern computer programming.[5] Performing this operation is simple in decimal arithmetic, in the binary numeral system used in computer programming, and in other even-numbered bases.

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.[5] 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.[6] 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,[7] and the C programming language provides the function ldexp for the same purpose.[8]

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.
If first digit is EvenEvenEvenEvenEven OddOddOddOddOdd
And second digit is 0 or 12 or 34 or 56 or 78 or 9 0 or 12 or 34 or 56 or 78 or 9
Write 01234 56789

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.

gollark: Actually, this is bad but necessary.
gollark: Prepare yourselves. ABR downtime approaches.
gollark: Just assume the (generalized, apparently) Riemann hypothesis.
gollark: Obviously you should use the deterministic Miller test instead.
gollark: Which means we can't operate them in bulk.

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

References
  1. Steele, Robert (1922), The Earliest arithmetics in English, Early English Text Society, 118, Oxford University Press, p. 82.
  2. Chabert, Jean-Luc; Barbin, Évelyne (1999), A history of algorithms: from the pebble to the microchip, Springer-Verlag, p. 16, ISBN 978-3-540-63369-3.
  3. Jackson, Lambert Lincoln (1906), The educational significance of sixteenth century arithmetic from the point of view of the present time, Contributions to education, 8, Columbia University, p. 76.
  4. Waters, E. G. R. (1929), "A Fifteenth Century French Algorism from Liége", Isis, 12 (2): 194–236, doi:10.1086/346408, JSTOR 224785.
  5. Wadleigh, Kevin R.; Crawford, Isom L. (2000), Software optimization for high-performance computing, Prentice Hall, p. 92, ISBN 978-0-13-017008-8.
  6. Hook, Brian (2005), Write portable code: an introduction to developing software for multiple platforms, No Starch Press, p. 133, ISBN 978-1-59327-056-8.
  7. "Math.scalb". Java Platform Standard Ed. 6. Retrieved 2009-10-11.
  8. Programming languages — C, International Standard ISO/IEC 9899:1999, Section 7.12.6.6.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.