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.