karl@haddock.ima.isc.com (Karl Heuer) (02/24/90)
In article <E*er-q@cs.psu.edu> callahan@mordor.endor.cs.psu.edu (Paul B. Callahan) writes: >After seeing enough mathematics, I was ultimately convinced that my intuition >was at fault. A similarly confusing point is that the negative of a negative number is positive. Ah, the memories of being a TA... >If we assume that floating point arithmetic is done using a sign-magnitude >representation [then truncate is probably easier than floor to implement]. But, given that most implementations use two's complement for integers, and even for floating-point exponents, why *is* sign-magnitude the standard for floating point significands? Karl W. Z. Heuer (karl@ima.ima.isc.com or harvard!ima!karl), The Walking Lint
dik@cwi.nl (Dik T. Winter) (02/25/90)
In article <16014@haddock.ima.isc.com> karl@haddock.ima.isc.com (Karl Heuer) writes: > In article <E*er-q@cs.psu.edu> callahan@mordor.endor.cs.psu.edu (Paul B. Callahan) writes: > >If we assume that floating point arithmetic is done using a sign-magnitude > >representation [then truncate is probably easier than floor to implement]. > > But, given that most implementations use two's complement for integers, and > even for floating-point exponents, why *is* sign-magnitude the standard for > floating point significands? > There is a good reason to use two's complement for integers: on an add ignore carry, this reason is much less compelling when doing floating-point arithmetic, you can not simply ignore carry. Note also that the exponent is not strictly two's complement, but has the sign bit inverted. The reason is that compare logic is simplified. Further, IEEE specifies four rounding modes, so using a two's complement mantissa because of simple truncation is no good reason. It is even stronger: when doing a round to nearest IEEE specifies that if the exact result is halfway two representable numbers, that number has to be chosen that has a low order zero bit (*). With a two's complement mantissa a similar requirement might be posed, but it would look more complex, and would be more complex in the logic. -- (*) See [I think; this is from memory] IEEE Computer, Vol. 14, Issue 1. This describes draft 8.0 of the IEEE standard and has a number of accompanying articles. The current standard is based on draft 10.0. There are some differences, but they are not shocking. I do not have a reference for that standard. -- dik t. winter, cwi, amsterdam, nederland dik@cwi.nl
ccplumb@lion.waterloo.edu (Colin Plumb) (03/01/90)
In article <16014@haddock.ima.isc.com> karl@haddock.ima.isc.com (Karl Heuer) writes: >But, given that most implementations use two's complement for integers, and >even for floating-point exponents, why *is* sign-magnitude the standard for >floating point significands? Because the multiply/add ratio is much higher for floating point code, and signed-magnitude is better for multiply at the expense of add. -- -Colin
db@lfcs.ed.ac.uk (Dave Berry) (03/02/90)
In article <12115@goofy.megatest.UUCP> djones@megatest.UUCP (Dave Jones) writes: >Just now I did a little experimenting. On Sun-3, release 4.3. In both C >and Pascal, division is correct, but mod is wrong. > >In other words, they have it exactly backwards from the ANSI Pascal >Standard. Not right mathematically. Not right according to the standard. >You got to wonder, how come? Almost certainly becasue that's how the hardware does it. Almost all processors implements integer division and modulus that way.o Questions to comp.arch readers (who I've just tuned in): 1. Is the "normal" method for calculating integer division and modulus intrinsically faster than the mathematically expected definition (that rounds towards minus infinity), or is it just convention that it's implemented this way? 2. If everyone was suddenly to agree that the mathematically expected definition should be adopted as a standard, could it be done quicker in hardware than with software over the existing hardware? There is some weight to arguments that languages should support the round towards zero versions. Standard ML defines div and mod the mathematically expected way, and this has produced criticism from some users and implementers that use of these operators on positive arguments is unnecessarily penalised, since they can't use the versions provided by the hardware. It is possible that the definition might be amended to support both definitions. I note that the ISO draft proposal for standard computer arithmetic (published in SIGPLAN notices, Jan. 1990) allows either or both versions of div and mod. For reference, the Definition of Standard ML defines div and mod as follows: i mod d, i div d return integers r, q determined by the equation d * q + r = i, where either 0 <= r < d or d < r <= 0. Thus r has the same sign as d. [An exception is raised] if d = 0. [nb. the operators used in this definition are those of arithmetic, not of the language.] What sign i mod d should have when d < 0 (in an arbitrary language, not ML) was discussd in several other articles recently. Dave Berry, LFCS, Edinburgh Uni. db%lfcs.ed.ac.uk@nsfnet-relay.ac.uk "The thought of someone sharing one's own preferences without also sharing one's aversions strikes most people as utterly inconceivable." - C. A. Tripp.
cet1@cl.cam.ac.uk (C.E. Thompson) (03/03/90)
In article <2573@castle.ed.ac.uk> db@lfcs.ed.ac.uk (Dave Berry) writes: > >Almost certainly becasue that's how the hardware does it. Almost all >processors implements integer division and modulus that way.o *Very* few processors produce a "natural" div and rem/mod which are not related by (i div j)*j + (i rem j) = i. Therefore no Pascal implementation that passes the validation tests can be as naive as you suggest. Chris Thompson JANET: cet1@uk.ac.cam.phx Internet: cet1%phx.cam.ac.uk@nsfnet-relay.ac.uk
emcmanus@cs.tcd.ie (Eamonn McManus) (03/07/90)
db@lfcs.ed.ac.uk (Dave Berry) writes: >1. Is the "normal" method for calculating integer division and modulus > intrinsically faster than the mathematically expected definition (that > rounds towards minus infinity), or is it just convention that it's > implemented this way? An interesting point about rounding to minus infinity is that it allows (sign-extending) right shifts to be used for integer division by powers of two, when using twos-complement representation. For example, -7/2 is -3 by the `normal' definition but -4 by the `mathematically expected' definition. Its twos-complement representation is 1...1001, which when shifted right produces 1...100 or -4 as required. If a programming language supported this definition of negative division, its compilers could optimize divisions by powers of two into shifts without having to know whether the quantity being divided was negative. On many (most?) processors shifts are faster than divisions even by powers of two. [Unsupported assertion.] -- Eamonn McManus <emcmanus@cs.tcd.ie> <emcmanus%cs.tcd.ie@cunyvm.cuny.edu> One of the 0% of Americans who are not Americans.
djones@megatest.UUCP (Dave Jones) (03/09/90)
From article <1710@tws8.cs.tcd.ie>, by emcmanus@cs.tcd.ie (Eamonn McManus): ... > > An interesting point about rounding to minus infinity is that it allows > (sign-extending) right shifts to be used for integer division by powers of > two, when using twos-complement representation. Lots of operations work better on a two's complement machine, when you use the 'mathematical' rules. Operations distribute correctly. Multiplications and divisions by powers of two can be done with shifts. Modulus by a power of two can be done with an &-operator. Multiplications by other numbers can be done with combinations of shifts and adds. It all works nicely because there is a nice consistent theory behind it. In fact, except for sign-extension, the operations are exactly the same for signed and unsigned numbers! How come? Imagine this: For some positive number M, we take the integers, coil them up into a helix then squash the helix into a circle of circumference M. We can consistently identify the points on that circle with any interval of length M, but two are obvious winners: If we choose the interval 0..(M-1), we get unsigned arithmetic. If we choose -(M/2) .. (M/2)-1 we get signed numbers. If M happens to be 2**n, where n is the word-size of the machine, the mod-M coiling happens automatically as the bits are shifted out and lost. Sign-extension is a way of 'recovering' the bits by shifting them in. See why it works so well? Look at the mess the Sun-3 C compiler generates, in order to come up with the conventional, but mathematically incorrect, answer to i/2: | Annotated for those lucky enough not to know already... tstl d0 | Perform various tests on it. jge L2000000 | Jump if i is greater than or equal to zero. addql #1,d0 | No? Add one to it. (What a bother.) L2000000: asrl #1,d0 | Now, we can do the shift. There's that ubiquitous test for non-negative, staring us in the face. Smug little bugger. Somebody recently said that this situation we are so often stuck with is an artifact of the system FORTRAN was first implemented on, which used sign-bit coded integers. The division routine (incorrectly) did arithmetic on the low bits and then negated the result if the sign bits of the operands differed. And the rest is histrionics.
rpw3@rigden.wpd.sgi.com (Rob Warnock) (03/09/90)
In article <1710@tws8.cs.tcd.ie> emcmanus@cs.tcd.ie (Eamonn McManus) writes: +--------------- | ...If a programming language supported | this definition of negative division, its compilers could optimize | divisions by powers of two into shifts without having to know whether the | quantity being divided was negative. On many (most?) processors shifts are | faster than divisions even by powers of two. [Unsupported assertion.] +--------------- This keeps coming up (comp.arch.topics.perennial anyone?). (The first time I ran into it was in the early 1970's when the PDP-10 Fortran compiler got the obvious bug fixed.) These days, all good compilers know how to optimize this anyway, with a pre- or post-shift correction step that makes this work "right" even for negative dividends. In C, with post-shift correction: #define DIVISOR (1 << SHIFT) #define MASK (DIVISOR - 1) result = (dividend >> SHIFT); if (dividend < 0 && (dividend & MASK) != 0) result += 1; or with pre-shift correction: if (dividend < 0) dividend += MASK; result = (dividend >> SHIFT); The really cute trick is that for most machines this can be done in just a few extra cycles *without* a branch (and therefore without a pipeline break) by computing "MASK" from the dividend's sign bit. For example, on the Am29000, to divide register "a0" by a power-of-2 constant giving "v0" costs four cycles total (most other architectures have similar short sequences): sra v0, a0, SHIFT - 1 ; replicate the sign-bit by the shift-width srl v0, v0, 32 - SHIFT ; right-justify. t0 = (a0 < 0)? MASK : 0 add v0, v0, a0 ; correct the dividend sra v0, v0, SHIFT ; do the division -Rob ----- Rob Warnock, MS-9U/510 rpw3@sgi.com rpw3@pei.com Silicon Graphics, Inc. (415)335-1673 Protocol Engines, Inc. 2011 N. Shoreline Blvd. Mountain View, CA 94039-7311
toma@tekgvs.LABS.TEK.COM (Tom Almy) (03/10/90)
In article <1710@tws8.cs.tcd.ie> emcmanus@cs.tcd.ie (Eamonn McManus) writes: >db@lfcs.ed.ac.uk (Dave Berry) writes: >>1. Is the "normal" method for calculating integer division and modulus >> intrinsically faster than the mathematically expected definition (that >> rounds towards minus infinity), or is it just convention that it's >> implemented this way? >An interesting point about rounding to minus infinity is that it allows >(sign-extending) right shifts to be used for integer division by powers of >two, when using twos-complement representation. [example deleted] >If a programming language supported >this definition of negative division, its compilers could optimize >divisions by powers of two into shifts without having to know whether the >quantity being divided was negative. Well Forth supports this type of division. It does so because in control applications you don't want the discontinuity around zero that you get with the truncating division. Yes, that does make it possible to divide by powers of two with simple shift instructions. But now division is messed up because hardware divide operations trucate rather than floor. So you get your choice -- fixup code for divisions by powers of two or fixup code for divisions by signed variables or negative constants. BTW there is considerable support in the Forth community to supply both styles of division. Smalltalk already supplies both: // and \\ for floored integer division and remainder and quo: and rem: for truncating operations. Other languages don't seem so generous. Tom Almy toma@tekgvs.labs.tek.com Standard Disclaimers Apply