Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!ucla-cs!sdcrdcf!pmontgom
From: pmontgom@sdcrdcf.UUCP (Peter Montgomery)
Newsgroups: comp.lang.misc
Subject: Re: Problems needed!
Message-ID: <4712@sdcrdcf.UUCP>
Date: Sun, 28-Jun-87 20:03:51 EDT
Article-I.D.: sdcrdcf.4712
Posted: Sun Jun 28 20:03:51 1987
Date-Received: Mon, 29-Jun-87 02:43:53 EDT
References: <9819@duke.cs.duke.edu>
Reply-To: pmontgom@sdcrdcf.UUCP (Peter Montgomery)
Organization: Unisys - System Development Group, Santa Monica
Lines: 87

In article <9819@duke.cs.duke.edu> jds@duke.cs.duke.edu (Joseph D. Sloan) writes:
>
>	It's common practice in comparative programming languages 
>courses to assign the same problem in several different languages to 
>compare and contrast different features of those languages.
> ...
>Please folks, lots of problems!
>

        The operation I miss most in higher-level languages is:  Given
three integers a, b, n where 0 <= a, b < n, find integers q, r such that
a*b = q*n + r and 0 <= r < n.  We allow n to be very large; in particular
the product a*b need not fit in a positive integer.  Note q will also
satisfy 0 <= q < n.

        This is a critical operation (typically with n being a power of 2)
when writing multiple-precision arithmetic routines.  If the hardware
supports double-length multiplication and division instructions (e.g.,
EMUL and EDIV on a VAX), then this is trivial in assembly.  We may also be
able to use floating point arithmetic: if we assume that numbers below n*n
can be represented exactly in floating point, then we can compute the
double precision floating point product for a*b and work from there.  Use
of floating point would illustrate how type conversions are done in each
language, esp. if the students are told to avoid unnecessary temporary
variables.  For example, the FORTRAN code could be

		integer a, b, n, q, r
		intrinsic DBLE, DMULT, INT, MOD, REAL

		q = INT(    DMULT(REAL(a), REAL(b)) /DBLE(n))
		r = INT(MOD(DMULT(REAL(a), REAL(b)), DBLE(n)))

(intrinsic statement optional - I consider it good programming practice).
But PASCAL lacks explicit conversion from integer to floating point,
and C lacks a floating point remainder function.

        The students should also be required to do a solution using
all-integer arithmetic.  If the language already supports multiple-precision
arithmetic, then it will be easy.  Otherwise the pseudocode might resemble:

		aa <- a
		bb <- b
		q <- 0
		r <- 0
		WHILE bb <> 0 DO

			/* a*b = aa*bb + q*n + r */
			/* 0 <= aa, bb, r < n    */

		    IF bb is odd THEN
			bb <- bb - 1
			IF r < n - aa THEN
			    r <- r + aa
			ELSE
			    r <- r - (n-aa)
			    q <- q + 1
			END IF
		    END IF

			/* a*b = aa*bb + q*n + r */
			/* 0 <= aa, bb, r < n    */
			/* bb is even            */

		    bb <- bb/2
		    IF aa < n - aa THEN
			aa <- aa + aa
		    ELSE
			aa <- aa - (n-aa)
			q <- q + bb
		    END IF
		END WHILE

This (untested) code takes time O(log(b)) <= O(log(n)).
All intermediate results are between 0 and n.

        BTW, those of us who do extensive multiple-precision integer
arithmetic must either make frequent calls to assembly-language
subprograms (and it can be very expensive to make 100 procedure calls when
multiplying two numbers each occupying ten machine words) or must write
much larger subprograms in assembly language (making our programs much
less portable).  Future higher-level languages should include this as a
primitive construct.
-- 
	Peter Montgomery     {aero,allegra,bmcg,burdvax,hplabs,ihnp4,
			      psivax,randvax,sdcsvax,trwrb}!sdcrdcf!pmontgom

Don't blame me for the crowded freeways - I don't drive.