Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- papierkorb:signed_integer_division [2025-08-10 22:50] – ↷ Seite von projects:signed_integer_division nach papierkorb:signed_integer_division verschoben mka
+++ papierkorb:signed_integer_division [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
-<code>
-                     Signed Integer Division
-                       by Robert L. Smith
-    Originally appearing in Dr. Dobb's Journal September 1983
-Not all methods of integer division produce a uniform result when the
-dividend and divisor have opposite signs.  This may not be so important in
-the area of commerce where negative values are perhaps used less.  When
-dealing with measurement and control, however, uniformity becomes more
-significant.  The Forth-83 Standard adopts a method for signed integer
-division called "floored" division.  While APL has used this method for the
-RES function for years and Small-Talk provides it as one of three methods
-for integer division, acceptance of the Standard makes Forth the first
-"popular" language to embrace this method based on its theoretical merits.
-The problem is one of mathematical purity versus user expectation.  This
-article will attempt to clarify some of the issues involved.
-Integer division is a mathematical function of two integers (a dividend and
-a divisor) that yields an integer quotient and an integer remainder.  That
-appears to be a fairly straightforward operation, but there is not
-universal agreement of the desired results when one or both arguments are
-negative.  When an ingeger quotient is used in plotting or machine control,
-the desired function is usually _not_ the quotient given by the majority of
-computers.
-Most computers with a divide function produce a quotient that has a
-property of symmetry around zero when plotted as a function of the
-dividend, due to the fact that the quotient is rounded toward zero.
-Speaking mathematically, the property is actually one of anti-symmetry,
-where the sign of the quotient is reversed when the sign of the dividend
-(or numerator) is reversed.  For integer division, this "symmetric"
-property leads to a sort of discontinuity around zero.  In this case, the
-remainder is either zero or it takes the sign of the dividend.  Figure 1a
-illustrates the quotient q as a function of a variable dividend, and a
-constant divisor 3.  We readily see the discontinuity near zero.  This may
- +-------------------------------------------------------+
- |                                                       |
- |                        3 +                 o o o      |
- |                          +           o o o            |
- |       -9                 +     o o o       9          |
- |    +-+-+-+-+-+-+-+-+-o-o-o-o-o-+-+-+-+-+-+-+-+-+-     |
- |                o o o     +                            |
- |          o o o           +                            |
- |    o o o              -3 +                            |
- |                                                       |
- |      (a) Quotient for Symmetric Integer Division      |
- |                                                       |
- |                                                       |
- |                                                       |
- |                          +                            |
- |                        2 +   o     o     o     o      |
- |       -9                 + o     o     o     o        |
- |    +-+-o-+-+-o-+-+-o-+-+-o-+-+-o-+-+-o-+-+-o-+-+-     |
- |      o     o     o     o +                 9          |
- |    o     o     o     o   + -2                         |
- |                          +                            |
- |                                                       |
- |      (b) Remainder for Symmetric Integer Division     |
- |                                                       |
- |                      Figure 1.                        |
- |_______________________________________________________|
-be reasonably serious when this quotient function is used for plotting or
-moving robot arms.  The integer quotient needs an associated remainder:
-   r = n - q * d
-where n is the numerator or dividend, d is the denominator or divisor, q is
-the quotient, and r is the remainder.  The remainder function for the
-constant divisor 3 is illustrated in Figure 1b.  If we look at the case of
-positive dividends and divisors, we observe the cyclic property that
-   r(n+d) = r(n)
-In other word, the remainder usually has a repeating or cyclical property
-as the dividend changes.  For the remainder shown in Figure 1b, we see that
-this simple property is not maintained for dividends between -d and 0.
-If we require that the remainder be cyclical, then the quotient no longer
-has any unusual discontinuities.  There are a number of possible choices
-here.  One obvious choice is to make the remainder the same as the modulus
-or residue function (1).  In this case the quotient is rounded toward minus
-infinity.  This rounding procedure is called the "floor" function.  Figure
-shows the floored quotient and its related modulus for the same
-arguments used in Figure 1.  Notice the quotient behaves in a more nearly
-continuous fashion around zero.  This is the form used in the Forth-83
-Standard, as well as some of the older versions of Forth.  The National
-microprocessor produces floored division in addition to the older
-"rounded toward zero" variety.  The modulus function is called  MOD  in
-Forth-83 and in the National 16032.  It is called RES in APL.
- +-------------------------------------------------------+
- |                                                       |
- |                        3 +                 o o o      |
- |                          +           o o o            |
- |       -9                 +     o o o       9          |
- |    +-+-+-+-+-+-+-+-+-+-+-o-o-o-+-+-+-+-+-+-+-+-+-     |
- |                    o o o +                            |
- |              o o o       +                            |
- |        o o o          -3 +                            |
- |                                                       |
- |      (a) Quotient for Floored Integer Division        |
- |                                                       |
- |                                                       |
- |                                                       |
- |                          +                            |
- |            o     o     o +   o     o     o     o      |
- |       -9 o     o     o   + o     o     o     o        |
- |    +-+-o-+-+-o-+-+-o-+-+-o-+-+-o-+-+-o-+-+-o-+-+-     |
- |                          +                 9          |
- |                          + -2                         |
- |                          +                            |
- |                                                       |
- |      (b) Remainder for Floored Integer Division       |
- |                                                       |
- |                      Figure 1.                        |
- |_______________________________________________________|
-The "floored" quotient shown in Figure 2 is not anti-symmetric around zero.
-However, for odd divisors one may easily obtain a symmetric result by
-adding a correction factor to the dividend prior to division.  Although the
-quotient is generally not defined when the divisor is zero, the modulus is
-usually defined to take the value of the dividend for this case.  If
-infinities are not allowed in computer representations, and the product of
-any number and zero is always zero, then this definition preserves the
-equation
-   n = q * d + r
-for all values of d, including zero.
-Alternative remainder functions include a positive modulus and a remainder
-that takes the sign of the quotient (2).  Some other possibilities have the
-undesirable feature of negative remainders when the dividend and divisor
-are both positive.
-Floored division is simply more useful in the majority of applications
-programs.  The major objection is that the results are not what most people
-expect: -1 divided by 4 gives 0 in the rounded-toward-zero division case,
-but -1 for floored division.  Both cases give the same results when the
-dividend and divisor have the same sign.  Timing efficiencies may play a
-small role in deciding which form of division to use, but generally the
-division process is sufficiently slow that additional tests for different
-forms of rounding take only a little extra time.  Indeed, for some
-processors with built-in signed and unsigned divide functions, it may be
-faster in the common case of positive arguments to test signs and use the
-unsigned division than to just use the signed division function.  If you
-have an older Forth system (such as 79-Standard or fig-FORTH), the screen
-in Figure 3 shows a high-level conversion from the older form of  /MOD  to
-the newer version.  For those unfamiliar with Forth,  /MOD  takes two
-arguments, the dividend and the divisor, and returns two results: the
-quotient and the modulus, or remainder.  The quotient is returned as the
-most accessible element on the stack.
-The appearance of floored division in some of the newer processor chips and
-languages indicates the increasing awareness of its utility.  We might note
-in passing that even floating-point division will probably be different in
-the future than it was in the past due to the new Floating-Point Standard,
-which will require proper rounding of the quotient.
-References
-(1) Donald K. Knuth, _The Art of Computer Programming:  Volume I,
-Fundamental Algorithms_, Second Edition, Menlo Park: Addison-Wesley, 1973,
-p. 127.
-(2) Robert Berkey, "Integer Division, Rounding and Remainders", 1982 FORML
-Conference Proceedings, San Jose, California: Forth Interest Group, 1983,
-pp. 13-23.
- +---------------------------------------------------------------+
- |                                                               |
- |   ( Define 83-Standard  /MOD  in terms of old  /MOD )         |
- |   : /MOD   ( num den -- mod quot )                            |
- |      OVER OVER XOR 0<       ( test signs of arguments )       |
- |      IF                     ( signs are different )           |
- |           >R R@ /MOD OVER   ( divide and examine remainder )  |
- |           IF                ( non-zero remainder )            |
- |                1- SWAP R> + SWAP   ( adjust results )         |
- |           ELSE                     ( zero remainder )         |
- |                R> DROP             ( discard old den )        |
- |           THEN                                                |
- |      ELSE                          ( signs just the same )    |
- |           /MOD                     ( just divide normally )   |
- |      THEN ;                        ( end of definition )      |
- |                                                               |
- |                                                               |
- |                            Figure 3.                          |
- |      High Level Forth Code to Convert to Floored Division     |
- |_______________________________________________________________|
-</code>