(41C) Quotient and Remainder

[Werner]

[Update: for now, only for positive X and Y]
You would think this is a no-brainer, but, as has been touched upon a couple of times, you can't just calculate the Quotient with INT(Y/X), as that will fail when rounding occurs in the division.
The following routine gets it right, and even saves X in LASTX:

Code:

@ given X and Y, determine Quotient=DIV(Y,X)  and Remainder=MOD(Y,X)
@               L       X       Y       Z       T
@ In:                   X       Y
@ Out:          X       R       Q
01 LBL"RQ"  @           X       Y
02 RCL Y
03 RCL Y
04 /                   Y/X      X       Y
05 ENTER
06 INT @                Q      Q..      X       Y
07 X=Y?
08 GTO 00
09 RDN
10 RDN @                X       Y       Q
11 MOD @    X    R    Q
12 RTN
13 LBL 00
14 RDN
15 RDN @                X       Y       Q       Q
16 STO Z
17 MOD @        X       R       X       Q       Q
18 ST- Y @      X       R      X-R      Q       Q
19 X<>Y
20 X<=Y?
21 DSE Z @ Q=1 rounded up is not possible
22 RDN @        X       R       Q
23 END

Try for instance:
Y: 4 000 000 001, 4 000 000 002, 4 000 000 003
X: 4
and get the correct
Q: 1E9
R: 1,2,3

or

Y: 2.000000003E19
X: 4E9
to get
Q: 5 000 000 007
R: 2 000 000 000

Getting it right on machines that do round-to-even is somewhat harder. Stay tuned for my 42S solution, in another section of this forum.

Cheers, Werner
as an afterthought: this RQ split will only work when it makes sense, eg not for Y=1e40 and X=6 because then Q carries too many digits

[Joe Horn]

Interesting: The QR routine in the PPC ROM gets the wrong quotient for your final example. It returns 5000000008.

For reference, here's the code for QR in the PPC ROM. The synthetic command "STO O" is used to preserve Z and T on the stack. Same input and output order as your program.

Code:

82 LBL "QR"
83 X<>Y
84 STO O
85 X<>Y
86 MOD
87 ST- O
88 LASTX
89 ST/ O
90 CLX
91 X<> O
92 X<>Y
93 RTN

[Werner]

Hi Joe!
I have been working on these routines for quite a long time; it is surprisingly hard to get right.
see my conversation with Albert here.
And the PPC ROM routine works as long as Y is not too large wrt to R. If R is small then Y-R cannot be calculated eg
Y=2e10
X=3
result: Q=6 666 666 666, R=2
the PPC ROM will return Q=6 666 666 667 here, as it does Q=(Y-R)/X, but in 10-digit arithmetic Y-R=Y

Unfortunately, if you want to use this in a 'long division' routine, you're going to have to do an RQ split of
Y=Cc00
X=Xx
where each letter is a half-length integer and Cc < Xx, and this situation will occur, as in my last example. So I had to get it right for all those cases as well.
I also tried to return results as quickly as possible, since the halfway cases are rare (this is more prominent in the 42S routine), and use only the stack AND return X in LASTX.

Cheers, Werner

[Ángel Martin]

FWIW, QREM in the SandMath returns exactly the expected results.
Not my merit, it is based on Ken Emery's routine published in MCODE for Beginners.

[Werner]

(04-05-2023 02:44 PM)Ángel Martin Wrote:  FWIW, QREM in the SandMath returns exactly the expected results.
Not my merit, it is based on Ken Emery's routine published in MCODE for Beginners.

Hello Angel,
I looked that routine up, it performs the exact same steps as the PPC ROM routine, but coded in MCODE. It does not use extended precision (to my untrained eye, I don't speak MCODE), so I wonder how it got the right results? Or maybe you 'tweaked' it?
Werner

[Ángel Martin]

(04-10-2023 07:25 AM)Werner Wrote:  

(04-05-2023 02:44 PM)Ángel Martin Wrote:  FWIW, QREM in the SandMath returns exactly the expected results.
Not my merit, it is based on Ken Emery's routine published in MCODE for Beginners.

Hello Angel,
I looked that routine up, it performs the exact same steps as the PPC ROM routine, but coded in MCODE. It does not use extended precision (to my untrained eye, I don't speak MCODE), so I wonder how it got the right results? Or maybe you 'tweaked' it?
Werner

You're correct, I use a 13-digit division routine in QREM, which seems to make the difference.

Cheers,
ÁM

[J-F Garnier]

(04-16-2023 03:32 PM)Ángel Martin Wrote:  I use a 13-digit division routine in QREM, which seems to make the difference.

Using the internal 13-digit truncated division, then truncating (not rounding) it to 10 digits is the right thing to implement the integer division

J-F

[Ángel Martin]

(04-16-2023 06:30 PM)J-F Garnier Wrote:  

(04-16-2023 03:32 PM)Ángel Martin Wrote:  I use a 13-digit division routine in QREM, which seems to make the difference.

Using the internal 13-digit truncated division, then truncating (not rounding) it to 10 digits is the right thing to implement the integer division

J-F

Yes, and the OS does that for you: the truncated 10-digit value is placed in C, while the 13-digit value is left in registers {A,B}

[J-F Garnier]

(04-18-2023 05:40 AM)Ángel Martin Wrote:  the OS does that for you: the truncated 10-digit value is placed in C, while the 13-digit value is left in registers {A,B}

No, the OS provides the rounded 10-digit value in C.
If we need the truncated 10-digit value, we need to build it from {A,B}
(very similar to the HP-71B math code that I know much better)

So QREM may give the wrong quotient when the dividend is >1E10, e.g.:
2E10 3 QREM --> Q=6666666667

(checked on V41-R9I, Lib#4-R59b, SandMath-R7)

J-F
Edit: not really sure of the SandMath version I downloaded from TOS. The Web page and the manual both say Release 7, but the ROM says R6 (HL-6B, SM-6B) ?

[Werner]

I used Sandmath V9 'bankswitched something' in my DM41X to verify QREM, it gets everything absolutely right, see the original problematic one that the PPC routine got wrong:
Y: 2.000000003E19
X: 4E9
to get
Q: 5 000 000 007
R: 2 000 000 000
(where the PPC ROM gets 5 000 000 008)
and of course also 2E10 and 3 -> 6 666 666 666 and 2

Cheers, Werner

[J-F Garnier]

Oh yes, my fault, I used a wrong (older) SandMath ROM, the one that is included in the V41 distribution.
Using the latest SandMath 'Release 7' from TOS indeed gives the right quotient for this test case:
2E10 3 QREM --> 666666666
All good, sorry Angel.

BTW, this SandMath 'Release 7' module on TOS is internally called "SandMath-V-#9 Bank-Switched 4x4++" with version = "8.8" and a ROM ID = "SM-9L". Still a bit confusing for me.

J-F

[Ángel Martin]

(04-18-2023 03:13 PM)J-F Garnier Wrote:  Oh yes, my fault, I used a wrong (older) SandMath ROM, the one that is included in the V41 distribution.
Using the latest SandMath 'Release 7' from TOS indeed gives the right quotient for this test case:
2E10 3 QREM --> 666666666
All good, sorry Angel.

BTW, this SandMath 'Release 7' module on TOS is internally called "SandMath-V-#9 Bank-Switched 4x4++" with version = "8.8" and a ROM ID = "SM-9L". Still a bit confusing for me.

J-F

Version control is a challenge when you "don't own the channel", I'm always behind sending updates to Warren, Monte, and SM so it's unfortunately likely that older versions are still posted on-line; sorry about that.

For the most part the CL site is up-to-date though, that's my reference.

ÁM