ANS TC Magnet for Division
ForthNet articles from GEnie
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!d...@hobbes.cert.sei.cmu.edu
ForthNet articles from GEnie
Date: 07-22-90 (06:07) Number: 445 (Echo)
To: R.BERKEY [ROBERT] Refer#: 441
From: ZAFAR ESSAK Read: NO
Subj: ANS TC MAGNET FOR DIVISIO Status: PUBLIC MESSAGE
All this discussion regarding the handling of division in Forth is
important even if at times it wears out one's interest. The Forth
language is a tremendous tool for developing applications as well as
exploring the intricacies of hardware structure. To maintain the
"public" interest in using Forth for application development the ANSI
Standards effort is going to have to make some hard decisions between
trying to compromise between what has been done in past implementations
of Forth and answering what is correct. I have followed discussions of
division in Forth for years and have longed for resolution based on
mathematically correct criteria. Having already learnt a language
doesn't make me scared of learning a little more. But I am quite
scared of a language based on the need to please individuals at the
expense of pursuing knowledge and understanding. One can even justify
the cost of changes to an application based on CORRECTNESS but not
based on appeasing others.
I do appreciate the amount of effort individuals are expending on the
ANSI Standard and some of the ideas and discussions on-line have
demonstrated some nice approaches to simplification of programming.
However, if the prime motivation of the committee is to find the areas
of compromise then maybe a more appropriate name for the resulting
language would be COMPOST, and it might possibly provide fertile ground
for future development. Unfortunately such an approach may cause
application developers to look elsewhere for required transportability
or convince them to support a single like-minded vendor.
Zafar.
---
* Via Qwikmail 2.01
NET/Mail : British Columbia Forth Board - Burnaby BC - (604)434-5886