Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!henry From: henry@utzoo.UUCP (Henry Spencer) Newsgroups: net.lang.c Subject: Re: Beware: Hackers - (nf) - integer division Message-ID: <3459@utzoo.UUCP> Date: Tue, 10-Jan-84 19:59:52 EST Article-I.D.: utzoo.3459 Posted: Tue Jan 10 19:59:52 1984 Date-Received: Tue, 10-Jan-84 19:59:52 EST References: <2208@fortune.UUCP> Organization: U of Toronto Zoology Lines: 33 Rob Warnock observes: Not only will "negative_int >> n" give you a terribly wrong answer (compared to "negative_int / (2**n)") if your machine uses logical shift, but it will give you an "off by one" answer if you use arithmetic shift (unless negative_int happens to be minus a power of 2 bigger than "n"). Actually, if the machine is using arithmetic shift the shift is arguably right and the "true" division wrong. The problem is that there is no unique "right" definition of integer division for the case where the remainder is nonzero. The basic problem is to define a function n div d (where n and d are integers) that yields an ordered pair of integers such that q*d + r == n && |r| < |d|. The problem is that there is more than one such function. The four most obvious possibilities can be summed up in terms of their effects on a non-zero remainder: 1. Remainder has same sign as dividend. 2. Remainder has same sign as divisor. 3. Remainder is always positive. 4. Magnitude of remainder is minimized, with some decision rule for resolving ties (e.g. 5 div 2 == <2, 1> or <3, -1>). 3 is a bit odd. 4 is rounding, which is usual for floating-point but odd for integers. The major candidates are 1 and 2. 1 is the Fortran approach, truncating the quotient towards 0. Most languages and most machines have followed Fortran's lead. 2 is "modulus division", with the quotient truncated toward minus infinity. This is the division operation implemented by arithmetic shifts on a two's-complement machine. Modulus division is possibly superior to Fortran division, in fact, and some recent languages and one recent machine (the 16032) recognize this. -- Henry Spencer @ U of Toronto Zoology {allegra,ihnp4,linus,decvax}!utzoo!henry