Path: utzoo!attcan!uunet!willett!ForthNet From: ForthNet@willett.UUCP (ForthNet articles from GEnie) Newsgroups: comp.lang.forth Subject: ANS TC Magnet for Division Message-ID: <1356.UUL1.3#5129@willett.UUCP> Date: 18 Jul 90 02:53:31 GMT Organization: String, Scotch tape, and Paperclips. (in Pgh, PA) Lines: 99 Category 10, Topic 17 Message 72 Tue Jul 17, 1990 R.BERKEY [Robert] at 08:52 PDT I'll run through some rationale concerning signed integer division, especially as it concerns standardization in 1982 of floored division. (rationale, 1: an explanation of controlling principles of opinion, belief, practice, or phenomena 2: an underlying reason : BASIS). I'll also list here what I mentioned last month as "specific technical problems" with rounded-to- zero division. ----- 1) MOD is a mathematically defined symbol. Forth-83 follows that definition. 2) Rounded-to-zero division is ignored in mathematical textbooks. Five technical problems with rounded-to-zero division: a) Rounded-to-zero division needs a negative zero such as is found on a sign-magnitude machine, and in this regard, it cannot be implemented properly on two's complement processors. The effect on two's complement machines is that quotients between -1 and 0 are represented as if they were between 0 and 1. Thereby, testing a quotient with 0< is a trap when using rounded-to-zero division. Information is lost, as 0 represents two sets of quotients, both those between -1 and 0, and those between 0 and 1. As a result of the lost information, a rounded-to-zero quotient exhibits a discontinuity at zero--in such applications as machine control and graphics. The often noted example from Brodie and Sanderson (see references below) is that of a robot arm that stalls momentarily during its movement. b) Rounded-to-zero division rounds quotients in two directions. This duality leads to reverse engineering programming to remove the extra direction, and if allowed to propogate, complexity in higher levels of the program. A common example is in coding a rounded-to-nearest result: a Forth-79 version requires an IF statement. c) A corollary to the bi-directional rounding of Forth-79 quotients is that the rounded-to-zero division has a cyclical remainder that reverses direction at zero. There has been no evidence or opinion that this remainder is useful. Charles Moore hasn't provided a rounded-to-zero remainder in his systems (his remainders are unsigned). A modulus, on the other hand, is a recurring application need. d) The rounding of the quotient of rounded-to-zero division is considered to be statistically inferior. The effect with analog signals is distortion. In the absence of the remainder, rounding to nearest or even "provides the most accurate and statistically unbiased estimate of the true results," (Intel, _8087 Numeric Data Processor, p. S-17). The rounding of flooring consistently biases the quotient, thus is more useful, such as in implementing a rounded-to-nearest result, and in limits-of-error analysis. e) Bit-fields, given that the high bit might be set, cannot be shifted with rounded-to-zero division. 3) As a result of the technical problems, rounded-to-zero division is bug prone, and this is demonstrated by published bugs in examples by Forth experts who are also division specialists. 4) With floored division, 2 / , is the same as 2/ . 5) Compared with using rounded-to-zero division, applications involving real numbers are in general handled better with either extra bits of precision, unsigned division, or rounded-to-nearest using floored division. 6) There has been no demonstration of a portable application in which rounded-to-zero division is the preferred division algorithm. References: Leo Brodie and Dean Sanderson, "Division, Relationals, and Loops", _1981 Rochester FORTH Standards Conference_, p. 117-121. Notes that the Forth-79 division is mathematically impure and produces undesirable side effects in ordinary applications. Robert Berkey, "Integer Division Rounding and Remainders", _1982 FORML Conference Proceedings_, p. 14-23. Includes timing comparisons for common division algorithms. Lists 16 division algorithms. Robert L. Smith, "Signed Integer Division", Dr. Dobbs, September 1983, also available in the GEnie library as FLOORED.DIV. "If we require that the remainder be cyclical, then the quotient no longer has any unusual discontinuities." ... "Floored division is simply more useful in the majority of applications programs." ----- Robert ----- This message came from GEnie via willett through a semi-automated process. Report problems to: uunet!willett!dwp or willett!dwp@hobbes.cert.sei.cmu.edu