integer division
01-30-2014, 03:30 PM
Post: #1
 Werner Senior Member Posts: 744 Joined: Dec 2013
integer division
As part of a long division, I need to do the following on the 42S (but it applies to all HP calculators that do not have a DIV command):
Given C and X, C<X
determine Q and R so that

C*10^12 = Q*X+R

C,Q,R,X positive and less than 10^12

Sounds easy? It isn't, or I am missing something.
R is easy: MOD(C*10^12,X), absolutely correct.
Now for Q..

Try:

C=2 and X=3 (Q=666 666 666 666, R=2)
C=2e11+3, X=4e11 (Q=500 000 000 007, R=2e11)

Can you get the correct Q? For the second example, I still can't ;-)
(Well, that is not strictly correct: of course I can, but not quickly and elegantly :-)

Werner
01-31-2014, 04:44 AM (This post was last modified: 01-31-2014 04:54 AM by Thomas Klemm.)
Post: #2
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: integer division

00 { 34 Byte Prgm }
01 LBL "DIV"
02 RCL ST Y
03 1E11
04 RCL* ST Z
05 /
06 IP
07 1E11
08 *
09 R^
10 RCL ST Y
11 RCL* ST T
12 -
13 R^
14 /
15 IP
16 +
17 END

Cheers
Thomas

PS: TED Talk
01-31-2014, 01:46 PM
Post: #3
 Werner Senior Member Posts: 744 Joined: Dec 2013
RE: integer division
Hello Thomas.
Yes, that works. I do the same with 1e6 as 'split', but I was wondering if there wasn't a shorter/faster way, knowing that

Q = INT(C*10^12 / X - R / X)

works for all cases save for 12-digit odd Q's where X = 2*R, which is quite rare indeed (and was the source for my second example)
01-31-2014, 03:50 PM
Post: #4
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: integer division
A little bit shorter:

00 { 4-Byte Prgm }
01 %CH
02 1
03 %
04 END

Example:

3
ENTER
2 E 12
R/S

x: 666,666,666,666

This might not work in all cases though, but it could help in some corner cases.
OTOH it might be easier to only use 6 digits per register.

Cheers
Thomas
01-31-2014, 06:33 PM
Post: #5
 Werner Senior Member Posts: 744 Joined: Dec 2013
RE: integer division
At first sight: Whoa!
On second sight it simply shifts the problem by 1 unit. Since both my examples were cases where round-up happened, it returns the correct result in these cases, but not in others (like C=1 and X=3, for instance).
02-01-2014, 06:06 PM (This post was last modified: 02-02-2014 09:18 AM by J-F Garnier.)
Post: #6
 J-F Garnier Senior Member Posts: 745 Joined: Dec 2013
RE: integer division
First calculate R:
R=MOD(C*1E12,X)
then
Q=(C*1E12-5E11*X-R)/X+5E11

The trick is to shift the result Q by -5E11 to avoid the rounding in the division.
I leave the implementation on the HP42S as an exercice...

This reminds me the famous S&S math challenges some years ago - Hello Valentin, if you are still around!

J-F

Added: Unfortunatly, this formula still fails for some cases... Needs more tuning, finally will not be so simple.
02-02-2014, 06:08 PM
Post: #7
 Werner Senior Member Posts: 744 Joined: Dec 2013
RE: integer division
No, you have to use INT(C0/(1e11*X) instead of 5e11.

Or you can calculate the two halves of the quotient separately, as follows:
Let every position denote 6 digits.
Then we have to split Cc00 into quotient Qq and remainder Rr:

Cc00 = Qq*Xx + Rr

Cc,Rr < Xx
or

Cc00 = Q0*Xx + q*Xx + Rr
Cc00 = Q*Xx0 + q*Xx + Rr

Here, q*Xx + Rr = MOD(Cc00,Xx0)

So,

Rr = MOD(Cc00,Xx)
Q = INT(Cc00/Xx0)
q = INT(MOD(Cc00,Xx0)/Xx)

Qq = Q0 + q

Code:
*LBL "DIV"  RCL ST X  1 e6  *  STO/ ST T  X<>Y  RDN  MOD  RUP  /  INT  X<>Y  INT  1 e6  *  +  END

Thomas did the same but used 1e11, splitting off only the first digit of Q
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)