Sunday, August 20, 2023

HP 42S and DM42: Multiplying Huge Positive Integers

HP 42S and DM42: Multiplying Huge Positive Integers





Introduction


The program LRG× multiplies to two large integers, allowing answers to extend beyond 12 digit capacity.  The product is shown in the alpha register.  How is this possible?  One way is to split the multiplier and multiplicand (also known as factors) into groups of digits.   This method is quite a complex process.  I will demonstrate with a simple example.




The Process Explained



Multiply: 


4,257 × 3,698 = 15,742,386


There are four digits in each of the factors (n = 4).


Split the numbers into groupings of two digits (n ÷ 2 =2).  Note that I use four registers to store the groups.   Memory registers R2 and R4 represent hundreds (10^2) while memory registers R1 and R3 represent units (10^0).


4257 = 42 × 10^2 + 57 

3698 = 36 × 10^2 + 98


R2 = 42, R1 = 57

R4 = 36, R3 = 98


Let memory register R5 be the units part of the product, up to 9999 (4 digits).   Let memory register R6 represent the part of the product 10,000 and above.  


On to the multiplication: 


Multiply R2 and R4, and store the results in R6.  In this case, 42 × 36 = 1512, which will R6 carry.   Memory register R6 represent ten-thousands (10^4) since R2 really is 4200 and R4 is really 3600, hence 4200 × 3600 = 15120000 = 1512 × 10^4.


Next multiply R1 and R3, then store the result in R5.   57 × 98 = 5586.   


We now have to take care of the cross product, which will represent hundreds (10^2).   This is done by the calculations of R2 × R3 + R4 × R1, which is 42 × 98 + 57 × 36 = 6168.  Note that this represents 6168 × 10^2 = 616800 = 610000 + 6800.  Add 61 to R6 (because R6 represents ten-thousands) and 6800 to R5.


In this example, the sums we have so far are:

R6 = 1573

R5 = 12386


R5 can only have four digits, we must carry over the 10000  (hence add 1 to R6, and drop the 1 from R5), to have a final result of:


R6 = 1573 + 1 = 1574

R5 = 2386


The answer is 15742386  (past R6 and R5 together).


Note:  Had R5 be less than 1000, R5 had to have four digits requiring a padding of zeroes (i.e. 712 becomes 0712, 16 become 0016).  


The program transfers R6 then R5 to the alpha register so the answer reads a long integer.   





In essence what we have done is:


4257 = 42 × 100 + 57 

3698 = 36 × 100 + 98


4257 × 3698 

= (42 × 10^2 + 57) × (36 × 10^2 + 98)

= (42 × 10^2 × 36 × 10^2) + (57 × 98) + (42 × 10^2 × 98 + 57 × 36 × 10^2)

= (1512 × 10^4) + 5586 + (4116 × 10^2 + 2052 × 10^2)

= (1512 × 10^4) + 5586 + (6168 × 10^2)

= 15120000 + 5586 + 616800

= 15742386


The program LRG× has larger unit digit capacity, up to 8 digits.   



HP 42S/Swiss Micros DM42 (including Free42 and Plus 42) Program:  LRG×


Raw file:  largemultiply.raw


Download the program here: https://drive.google.com/file/d/1KMCyGSSGeBvg0zT8UWvf4_uEaCVTfRwt/view?usp=sharing


Program Code:



00 { 156-Byte Prgm }

01▸LBL "LRG×"

02 ALL

03 XEQ 17

04 STO 02

05 XEQ 18

06 STO 01

07 R↓

08 XEQ 17

09 STO 04

10 XEQ 18

11 STO 03

12 RCL 02

13 RCL× 04

14 STO 06

15 RCL 01

16 RCL× 03

17 STO 05

18 RCL 01

19 RCL× 04

20 RCL 02

21 RCL× 03

22 +

23 ENTER

24 ENTER

25 XEQ 17

26 STO+ 06

27 LASTX

28 FP

29 8

30 10↑X

31 ×

32 STO+ 05

33 RCL 05

34 8

35 10↑X

36 X>Y?

37 GTO 16

38 ÷

39 ENTER

40 ENTER

41 IP

42 STO+ 06

43 R↓

44 FP

45 8

46 10↑X

47 ×

48 STO 05

49 GTO 16

50▸LBL 17

51 4

52 10↑X

53 ÷

54 IP

55 RTN

56▸LBL 18

57 LASTX

58 X<>Y

59 -

60 4

61 10↑X

62 ×

63 RTN

64▸LBL 16

65 CF 29

66 CLA

67 ARCL 06

68 8

69 RCL 05

70 X≠0?

71 GTO 21

72 8

73 GTO 22

74▸LBL 21

75 LOG

76 1

77 +

78 IP

79 -

80▸LBL 22

81 STO 07

82 X=0?

83 GTO 19

84▸LBL 20

85 48

86 XTOA

87 DSE 07

88 GTO 20

89▸LBL 19

90 ARCL 05

91 AVIEW

92 SF 29

93 .END.




Notes:


The program LRG× takes two integers from the stack.  This is meant to work on positive, non-zero integers.  


Flag 29 is the thousands separator flag.  Setting flag 29 turns them on while clearing it turns them off. In order to allow the alpha register have the long integer, flag 29 is cleared.


Memory register R5 represents units while R6 represents the part in hundred-millions.  


The program switches the display to ALL mode.  





Examples


Try these examples:  


54,195,365 × 40,857,695 = 2,214,297,693,583,675


12,068,999 × 50,245,126 = 606,408,375,448,874


50,700,600 × 33,800,020 = 1,713,681,294,012,000


58,763,110 × 6,758,999 = 397,179,801,726,890



Source


Hoffman, Dean and Mohler, Lee.   Mathematical Recreations for the Programmable Calculator  Hayden Book Company, Inc.   Rochelle Park:  New Jersey.  1982.  pp 146-166.  



Eddie 



All original content copyright, © 2011-2023.  Edward Shore.   Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited.  This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.