16 May 1999 14:11:00 -0400

Related articles |
---|

Rounding with Div and Mod operators william.rayer@virgin.net (William Rayer) (1999-05-09) |

Re: Rounding with Div and Mod operators wclodius@aol.com (1999-05-16) |

Re: Rounding with Div and Mod operators ucapjab@ucl.ac.uk (Jonathan Barker) (1999-05-16) |

Re: Rounding with Div and Mod operators nr@labrador.cs.virginia.edu (Norman Ramsey) (1999-05-16) |

Re: Rounding with Div and Mod operators guerby@acm.org (Laurent Guerby) (1999-05-16) |

Re: Rounding with Div and Mod operators anton@mips.complang.tuwien.ac.at (1999-05-16) |

Re: Rounding with Div and Mod operators Scott.Daniels@Acm.Org (Scott.David.Daniels) (1999-05-16) |

Re: Rounding with Div and Mod operators cdg@nullstone.com (Christopher Glaeser) (1999-05-16) |

Re: Rounding with Div and Mod operators johan.persson@mbox319.swipnet.se (Johan Persson) (1999-05-16) |

[11 later articles] |

From: | "Jonathan Barker" <ucapjab@ucl.ac.uk> |

Newsgroups: | comp.compilers |

Date: | 16 May 1999 14:11:00 -0400 |

Organization: | University College London |

References: | 99-05-039 |

Keywords: | arithmetic, design |

*> I'm writing a compiler for a new language which is to include the*

*> integer division and integer remainder operators (div and mod). I have*

*> some questions about the way these operators do rounding with negative*

*> operands and would appreciate any feedback.*

*>*

*> As I understand it div and mod (please excuse the Pascal notation)*

*> should always conform to a Fundamental Rule that for an integer*

*> numerator (n) and integer divisor (d) with d <> 0:*

*>*

*> n = (n div d) * d + (n mod d)*

*>*

*> What is interesting about this rule is there seem to be two ways of*

*> rounding that satisfy it when n or d are negative - either we round*

*> integers to the next lowest value or we round towards zero. The*

*> following table shows some positive and negative values of n and d*

*> under both systems:*

Dear William

For what it's worth...

As a mathematician I have often found the behaviour of div and mod

operators a little annoying (at least in C, Pascal etc). Number

theorists universally use the following standard definition of integer

division:

If n and d are integers and d is non zero, the quotient q = (n div d)

and remainder r = (n mod d) are defined by the equation n = qd + r

with the constraint 0 <= r <= d-1. Thus the remainder is always a

positive number between 0 and d-1 inclusive. Strictly speaking r

identifies the equivalence class of n in the integers modulo d.

To see that q and r thus defined are unique, suppose that they are not.

That is, suppose that qd + r = n with 0 <= r <= d-1, and there exist

q' and r' also satisfying q'd + r' = n and 0 <= r' <= d-1. Then

clearly qd + r = q'd + r', so it follows that (q-q')d = (r' - r). Hence,

either (i) q=q' and r=r', or (ii) d divides (r'-r). Obviously (i) contradicts

our hypothesis so we must assume (ii) - that (r'-r) is a multiple of d.

However, by hypothesis both r' and r are chosen from 0,...,d-1 so

their difference cannot be divisible by d. Therefore by contradiction

q' and r' cannot exist; ie. q and r are unique.

There is one very significant reason why this definition is more

'correct' than one which allows both positive and negative remainders

to occur. As I pointed out earlier, the remainder (n mod d) identifies

the equivalence class of n in the integers mod d. [0] stands for all

the integers divisible by d, [1] for integers of the form kd+1 and

in general if 0 <= r <= d-1, [r] stands for integers of the form kd+r.

However, if you also allowed negative remainders, you would have two

representations for each class. For example [-1] and [d-1] are

the same class (because kd + d-1 = (k+1)d -1).

In a sense, it does not matter how you do it, as long as what you do

is clearly defined and documented. However, any mathematical text

which discusses algorithms in number theory such as Euclid's division

algorithm, the Chinese Remainder Theorem and so on, will use the

definition I have outlined - so conforming to this standard would

somtimes ease programming tasks.

Regards

Jonathan

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.