integer division

01302014, 03:30 PM
Post: #1




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 41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE 

01312014, 04:44 AM
(This post was last modified: 01312014 04:54 AM by Thomas Klemm.)
Post: #2




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 

01312014, 01:46 PM
Post: #3




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 12digit odd Q's where X = 2*R, which is quite rare indeed (and was the source for my second example) 41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE 

01312014, 03:50 PM
Post: #4




RE: integer division
A little bit shorter:
00 { 4Byte 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 

01312014, 06:33 PM
Post: #5




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 roundup happened, it returns the correct result in these cases, but not in others (like C=1 and X=3, for instance). 41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE 

02012014, 06:06 PM
(This post was last modified: 02022014 09:18 AM by JF Garnier.)
Post: #6




RE: integer division
First calculate R:
R=MOD(C*1E12,X) then Q=(C*1E125E11*XR)/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! JF Added: Unfortunatly, this formula still fails for some cases... Needs more tuning, finally will not be so simple. 

02022014, 06:08 PM
Post: #7




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" Thomas did the same but used 1e11, splitting off only the first digit of Q 41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE 

« Next Oldest  Next Newest »

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