Division and Modulus for Computer Scientists.pdf

Division and Modulus for Computer Scientists DAAN LEIJEN University of Utrecht Dept. of Computer Science PO.Box 80.089, 3508 TB Utrecht The Netherlands daan@cs.uu.nl,http://www.cs.uu.nl/~daan/lvm.html December 3, 2001 1 Introduction There exist many definitions of the div and mod functions in computer science literature and programming languages. Boute (Boute, 1992) describes most of these and discusses their mathematical properties in depth. We shall therefore only briefly review the most common definitions and the rare, but mathematically elegant, Euclidean division. We also give an algorithm for the Euclidean div and mod functions and prove it correct with respect to Euclid’s theorem. 1.1 Common definitions Most common definitions are based on the following mathematical definition. For any two real numbers D (dividend) and d (divisor) with d 6= 0, there exists a pair of numbers q (quotient) and r (remainder) that satisfy the following basic conditions of division: (1) q ∈ Z (the quotient is an integer) (2) D = d · q + r (division rule) (3) |r | |d | We only consider functions div and mod that satisfy the following equalities: q = D div d r = D mod d The above conditions don’t enforce a unique pair of numbers q and r. When div and mod are defined as functions, one has to choose a particular pair q and r that satisfy these conditions. It is this choice that causes the different definitions found in literature and programming languages. Note that the definitions for division and modulus in Pascal and Algol68 fail to satisfy even the basic division conditions for negative numbers. The four most 1 2 Division and Modulus for Computer Scientists common definitions that satisfy these conditions are div-dominant and use the same basic structure. q = D div d = f (D/d) r = D mod d = D ? d · q Note that due to the definition of r, condition (2) is automatically satisfied by these definitions. Each definition is instantiated by choosing a proper function f : q = trunc(D/d) (