Quick Quiz #1 - DIV and MOD

Programming language questions
cfbsoftware
Posts: 55
Joined: Wed Sep 18, 2013 10:06 pm
Contact:

Quick Quiz #1 - DIV and MOD

Post by cfbsoftware »

Here is the first of a series of Component Pascal Quick Quizzes to sort out the men from the boys.

Don't cheat! The conditions of the quiz are:

a) Do not refer to the language report
b) Do not try it in BlackBox until you have worked out the result with pen and paper

To avoid winning the 'Spoiler of the Day' trophy please to do not reply with the correct answer or any explanation in a reply until this topic has had at least 100 views.

--------------------------------------
1. Given the following assignments:

Code: Select all

q := -10 DIV 3;
r := -10 MOD 3;
where q and r are INTEGER

What are the resulting values of q and r?

--------------------------------------

2. Given the following assignments:

Code: Select all

x := -10;
q := x DIV 3;
r := x MOD 3;
where x, q and r are INTEGER

What are the resulting values of q and r?

--------------------------------------

Regards,
Chris

Chris Burrows
CFB Software
http://www.cfbsoftware.com
User avatar
Robert
Posts: 177
Joined: Sat Sep 28, 2013 11:04 am
Location: Edinburgh, Scotland

Re: Quick Quiz #1 - DIV and MOD

Post by Robert »

Well I got these right, but this stuff is my bead and butter so it would have been embarrassing if I had not.

It gets harder when the number to the right of the DIV & MOD operators (which I shall call 'm') is negative. BlackBox is one of the few environments I have come across that does the 'right' thing.

The 'right' thing is quite subjective, so what I mean by right is not necessarily what other people think is right!

In truth, negative numbers to the right of the operators come up "naturally" very infrequently, so maybe it is not very important. But when they do I have found the BlackBox definition the most convenient.

I remember (I apologise if my memory is at fault) a conversation with the Zonnon fraternity on this subject. The language report defines MOD & DIV, for positive 'm', the same as BlackBox, but early versions did not implement that; they implemented them the C way. This was a noted implementation limitation. Ok, Rome wasn't built in a day. But the report explicitly did not define the result for negative 'm'. When I asked about that I expected some opinions about the relative merits of one definition verses another. But the reply surprised me. They strongly held the view that it should not be defined at all.


And Chris - I think the title of your quiz adds to the trickiness! - but will look forward to the next. Do I have to wait for the 100 responses?
cfbsoftware
Posts: 55
Joined: Wed Sep 18, 2013 10:06 pm
Contact:

Re: Quick Quiz #1 - DIV and MOD

Post by cfbsoftware »

BlackBox is one of the few environments I have come across that does the 'right' thing.
The first time I saw the behaviour described was in 1986 in an article by Prof Wirth regarding Modula-2. As far as I know subsequent implementations of Modula-2 and Oberon all use that behaviour. That is how it comes to be defined that way in Component Pascal. I'll email you the reference and post a link here to the article once the 100 views target is reached.

Edited: 25/11/2014

NOTE: I have since been reminded that there is a difference between Modula-2 / Oberon and Component Pascal. Component Pascal defines the behaviour of DIV (MOD) when the divisor(modulus) is negative whereas Modula-2 and Oberon leave those cases undefined.
Last edited by cfbsoftware on Tue Nov 25, 2014 7:35 am, edited 1 time in total.
manumart1
Posts: 67
Joined: Tue Sep 17, 2013 6:25 am

Re: Quick Quiz #1 - DIV and MOD

Post by manumart1 »

My answer:

1.

Code: Select all

q := -10 DIV 3;
r := -10 MOD 3;
q = -4
r = 2

I applied these rules:
  • (a) -10 = 3 * q + r
  • (b) q = The greatest integer so that
    • (b.1) 3 * q <= -10
    • (b.2) -10 <= 3 * (q + 1)
2.

Code: Select all

x := -10;
q := x DIV 3;
r := x MOD 3;
Same as 1.
cfbsoftware
Posts: 55
Joined: Wed Sep 18, 2013 10:06 pm
Contact:

Re: Quick Quiz #1 - DIV and MOD

Post by cfbsoftware »

You have to get the correct answer to win the 'Spoiler of the Day' trophy ;) Better luck next time!

Note:
To avoid winning the 'Spoiler of the Day' trophy please to do not reply with the correct answer or any explanation in a reply until this topic has had at least 100 views.
Zinn
Posts: 123
Joined: Mon Nov 24, 2014 10:47 am
Location: Frankfurt am Main
Contact:

Re: Quick Quiz #1 - DIV and MOD

Post by Zinn »

In the old days of computing (30 years ago) with C and Turbo Pascal a lot of compiler had an erroneous MOD function.
I used the following program for checking it.
I have this program translated to Component Pascal here.
In my old programs I used the procedure DivMod to avoid errors after transfer my program to an other system.

Code: Select all

MODULE TestDivMod;

	IMPORT StdLog;

	VAR a, b, c, i: INTEGER;

	PROCEDURE DivMod (number, divider: INTEGER; VAR a, b: INTEGER); (* form TbaseHexlib *)
	BEGIN
		a := number DIV divider;
		b := number MOD divider;
(*----------------------------------------------------------------------------
-- correct error in div & mod function: >>>  number := a * divider + b  <<<
--    number : -9 -8 -7  -6 -5 -4  -3 -2 -1   0 +1 +2  +3 +4 +5  +6 +7 +8  +9
------------------------------------------------------------------------------
-- func div 3: -3 -2 -2  -2 -1 -1  -1  0  0   0  0  0  +1 +1 +1  +2 +2 +2  +3
-- math div 3: -3 -3 -3  -2 -2 -2  -1 -1 -1   0  0  0  +1 +1 +1  +2 +2 +2  +3
------------------------------------------------------------------------------
-- func mod 3:  0 -2 -1   0 -2 -1   0 -2 -1   0  1  2   0  1  2   0  1  2   0
-- math mod 3:  0  1  2   0  1  2   0  1  2   0  1  2   0  1  2   0  1  2   0
-----------------------------------------------------------------------------*)
		IF b < 0 THEN a := a - 1; b := b + divider END;
	END DivMod;

	PROCEDURE Log;
	BEGIN
		StdLog.Tab; StdLog.Int(i);
		StdLog.Tab; StdLog.Int(a);
		StdLog.Tab; StdLog.Int(b);
		StdLog.Tab; StdLog.Int(c);
		IF c = i THEN StdLog.String('   OK') ELSE  StdLog.String('   failed') END;
		StdLog.Ln;
	END Log;

	PROCEDURE Run*;
	BEGIN
		FOR i := - 9 TO 9 DO
			a := i DIV 3;
			b := i MOD 3;
			c := 3 * a + b;
			Log;
		END;
	END Run;

	PROCEDURE Run2*;
	BEGIN
		FOR i := - 9 TO 9 DO
			DivMod(i, 3, a, b);
			c := 3 * a + b;
			Log;
		END;
	END Run2;

END TestDivMod.

(!)TestDivMod.Run
(!)TestDivMod.Run2
Josef Templ
Posts: 262
Joined: Tue Sep 17, 2013 6:50 am

Re: Quick Quiz #1 - DIV and MOD

Post by Josef Templ »

Please note that C does not have a MOD operator at all (if I remember correctly).
It has a 'remainder' operator. Most CPUs have a remainder operation
in hardware, not a MOD operation. The difference shows up for negative dividends.
The MOD function is actually meaningless for negative divisors because MOD is
mathematically only defined for positive values.
Getting a MOD behavior from a CPU's remainder operation requires additional code
emitted by the compiler or contained in the runtime system. So it is typically a
little slower than remainder.
Supporting negative divisors may require even more code (executed even for positive values)
and the benefit is questionable. That's enough reasons for Wirth not to support it.
I am not sure, but I think that C, at least in its original version, also did not define
the semantics of negative divisors.

- Josef
User avatar
Robert
Posts: 177
Joined: Sat Sep 28, 2013 11:04 am
Location: Edinburgh, Scotland

Re: Quick Quiz #1 - DIV and MOD

Post by Robert »

Josef Templ wrote:The MOD function is actually meaningless for negative divisors because MOD is
mathematically only defined for positive values.
Questionable.

The Wikipedia article http://en.wikipedia.org/wiki/Modular_ar ... ue_systems, see the section "Integers modulo n", defines them in terms of the quotient group Z/nZ.
It distinguishes two cases, n= 0 & n # 0.

Earlier parts of the article do refer to n > 0, but that does not apply to this section. See, for example, the first clause in the paper http://www.math.uconn.edu/~kconrad/blur ... /coset.pdf.

I think it is truer to say that there is not a single universally accepted definition; there are more than 1 which are useful in different contexts.
Josef Templ wrote:Getting a MOD behavior from a CPU's remainder operation requires additional code
emitted by the compiler or contained in the runtime system. So it is typically a
little slower than remainder.
True, at least for Pentium & Motorola 68030 type processors. Unless you use the floating point unit?
Josef Templ wrote:Supporting negative divisors may require even more code (executed even for positive values)
and the benefit is questionable. That's enough reasons for Wirth not to support it.
True again, as far as I can see.

I wonder how the BlackBox compiler implements MOD & DIV - does anyone know?


If anyone is wondering if modulo arithmetic is actually useful the answer is "Yes" for anyone who has ever used an https web site.

Robert
cfbsoftware
Posts: 55
Joined: Wed Sep 18, 2013 10:06 pm
Contact:

Re: Quick Quiz #1 - DIV and MOD

Post by cfbsoftware »

Robert wrote:I wonder how the BlackBox compiler implements MOD & DIV - does anyone know?
These look like the relevant lines of code from DevCPC486:

Code: Select all

		(* largeint support *)
		| div:
			IF rev THEN DevCPL486.GenFDOp(FDIVR, y) ELSE DevCPL486.GenFDOp(FDIV, y) END;
			Floor(y, FALSE)
		| mod:
			IF y.mode # Reg THEN LoadR(y); rev := ~rev END;
			IF rev THEN DevCPL486.GenFMOp(1C9H); (* FXCH ST1 *) END;
			DevCPL486.GenFMOp(1F8H);	(* FPREM *)
			DevCPL486.GenFMOp(1E4H);	(* FTST *)
			CheckAv(AX);
			DevCPL486.GenFMOp(FSTSW);
			DevCPL486.MakeReg(a, AX, Int32); GetReg(b, Int32, {}, {AX});
			DevCPL486.GenMove(a, b);
			DevCPL486.GenFMOp(0D1H);	(* FCOM *)
			DevCPL486.GenFMOp(FSTSW);
			DevCPL486.GenXor(b, a); Free(b);
			(* DevCPL486.GenCode(WAIT); *) DevCPL486.GenCode(SAHF);
			local := DevCPL486.NewLbl; DevCPL486.GenJump(ccBE, local, TRUE);
			DevCPL486.GenFMOp(0C1H);	(* FADD ST1 *)
			DevCPL486.SetLabel(local);
			DevCPL486.GenFMOp(5D9H);	(* FSTP ST1 *)
I know very little about Intel assembly language but they do look like floating point operations to me. Your supposition may have been spot on.
User avatar
Robert
Posts: 177
Joined: Sat Sep 28, 2013 11:04 am
Location: Edinburgh, Scotland

Re: Quick Quiz #1 - DIV and MOD

Post by Robert »

cfbsoftware wrote:I know very little about Intel assembly language but they do look like floating point operations to me
And me!

I don't understand the significance of the "largeint support" comment here. Does it mean this code works with INTEGERs and LONGINTs, or with the latter only?

I had heard that LONGINTs were implemented on the FPU, so am not surprised it is used here for LONGINTs. I am still curious how MOD & DIV are implemented for INTEGERs. Maybe they are simply promoted to LONGINTs?


I can't help observing that the code extract above contains (at least) two bugs, and their fixes have been previously published:

Code: Select all

		(* largeint support *)
		| div:
			IF y.mode # Reg THEN LoadR(y); rev := ~rev END; (* <<< patch by luowy, 19-Dec-2011 + Ivan Denisov *) 
			IF rev THEN DevCPL486.GenFDOp(FDIVR, y) ELSE DevCPL486.GenFDOp(FDIV, y) END;
			Floor(y, FALSE)
		| mod:
Robert
Post Reply