# HP Forums

Full Version: Multiply Function [x]
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
I'm wondering what algorithm is use in calculator for the multiply function.

So I came up with the basic whole number multiplication by using the

7 x 4 = (7 + 7 + 7 + 7) = 28

Then I came up with this program to do the multiply function.
This program will multiply two whole numbers and do multiply with the first whole number with decimal like (21.75 x 5)

This program will not give correct result when multiply both decimal numbers like (10.2 x 11.2)

Example: 6903 x 103

6903 [ENTER] 103 [R/S] ---> 711009

Step can be reverse: 103 [ENTER] 6903 [R/S] ---> 711009

Program: Multiply Function using HP-12C
Code:
 01 STO 0 02 X<>Y 03 STO 1 04 RCL 0 05 INTG 06 X=0 ? 07 GTO 17 08 RCL 2 09 RCL 1 10   + 11 STO 2 12 RCL 0 13   1 14   - 15 STO 0 16 GTO 05 17 RCL 2 18   0 19 STO 2 20 X<>Y

Is there any other more efficient way to do this better and faster?
Anyone get a better solution so that this can do multiplication with both decimal numbers like (123.45 x 12.34)

Thank You

Gamo
Code:
 01   × (08-03-2018 11:31 AM)Massimo Gnerucci Wrote: [ -> ]
Code:
 01   × No pain no gain ... or "A vaincre sans péril on triomphe sans gloire" Hello Gamo,

what is the problem with the decimal numbers? Remove the decimal points, multiply the intergers and add the (correct) decimal point to the result.

Most of the time decimal numbers are stored in a computer as floating point numbers with significand (digits) and exponent. For example in IEEE754 format
x = m * 2^e
where m is the significand and e is the exponent.

Multiplication is done by multiplying the significands, adding the exponents and normalize the result.

The multiplication of the significands could be done by a shift and add algorithm. Wikipedia
(08-03-2018 11:31 AM)Massimo Gnerucci Wrote: [ -> ]
Code:
 01   ×

Excellent my friend!! Great way to start a weekend, with a good laugh...  I like this algorithm; it's so simple you can do it with a couple pieces of wood.

Code:
01 LBL"MULT 02 CF 00 03 X=0? 04 GTO 00 05 X<0? 06 SF 00 07 ABS 08 LN 09 X<>Y 10 X<0? 11 XEQ 01 12 ABS 13 LN 14 + 15 E^X 16 FS?C 00 17 CHS 18 RTN 19 LBL 00 20 + 21 CLX 22 CF 00 23 RTN 24 LBL 01 25 FC?C 00 26 SF 00 27 END
(08-03-2018 09:27 AM)Gamo Wrote: [ -> ]I'm wondering what algorithm is use in calculator for the multiply function.

There was a series of HP Journal articles that described how calculators do their calculations. I remember something about log, exponential and trig functions, and maybe there also was something about multiplication and division.

(08-03-2018 09:27 AM)Gamo Wrote: [ -> ]Example: 6903 x 103

6903 [ENTER] 103 [R/S] ---> 711009

When I ran this it returned 711012,14.

Why is that? Register 2 happened to have pi stored in it (from a previous calculation – the 12C has continuous memory). And your program does not clear this register before it starts adding! I have mentioned this point several times: always clear a sum before you start adding data! Clearing the sum afterwards, as your program does it, is not a solution.

(08-03-2018 09:27 AM)Gamo Wrote: [ -> ]Step can be reverse: 103 [ENTER] 6903 [R/S] ---> 711009

But the program takes much longer to finish. You should start with the smaller number in X. Why not have the program care for this? Simply start with

X<=Y?
X<>Y
X<>Y

You can also speed up (and shorten) the program by using storage arithmetics.

Edit: here's my attempt of such a program. Only one data register is required.

Code:
01 X<=Y? 02 X<>Y    // this way the larger factor is in X 03 X<>Y    // and now it's the smaller factor 04 INTG    // this must be an integer 05 STO 0   // store smaller factor as counter 06 X<>Y    // the larger factor (may be fractional) 07 INTG    // is moved into LastX (INTG used only for this purpose) 08 0       // initialize sum to zero 09 RCL 0   // check counter 10 X=0?    // has it become zero? 11 GTO 19  // then exit 12 1 13 STO-0   // else decrement counter 14 R↓ 15 R↓      // pop back sum (was in Z) 16 LstX 17 +       // add larger factor 18 GTO 09 19 +       // sum was in Y while X=0, so this returns the result in X

Note: the smaller (!) of the two factors must be an integer ≥0. If there is a fractional part it is discarded.
The larger factor may be fractional.

123,4 [ENTER] 17 [R/S] => 2097,80
17 [ENTER] 123,4 [R/S] => 2097,80

Dieter
(08-03-2018 01:07 PM)wynen Wrote: [ -> ]The multiplication of the significants could be done by a shift and add algorithm. Wikipedia

Peasant or binary multiplication

Here's a program for the HP-11C:
Code:
LBL A       ; times STO 0       ; b a CLx         ; s=0 a LBL 0       ; while x<>y        ; a s x=0         ; a=0? GTO 2       ; done RCL 0       ; b a s STO+ 0      ; b → 2b x<>y        ; a b s 2           ; 2 a b s ÷           ; a÷2 b s s ENTER       ; a÷2 a÷2 b s INT         ; a'=⌊a÷2⌋ a÷2 b s x=y         ; 2∣a GTO 1       ; even R↓          ; a÷2 b s a' R↓          ; b s a' a÷2 +           ; s'=s+b a' GTO 0       ; while LBL 1       ; even R↑          ; s'=s a' GTO 0       ; while LBL 2       ; done R↓          ; s RTN         ;

This is a translation of the following Python program:
Code:
def times(a, b):     s = 0     while a != 0:         if a % 2 != 0:             s += b         a /= 2         b += b     return s

It works for positive integers $$a$$ and $$b$$ and calculates $$a\times b$$.

Cheers
Thomas
(08-03-2018 02:40 PM)Dieter Wrote: [ -> ]There was a series of HP Journal articles that described how calculators do their calculations. I remember something about log, exponential and trig functions, and maybe there also was something about multiplication and division.

This is the relevant MCODE of the HP-41 for the multiplication:
Code:
***************************************************** *   NUT MATH ROM 1                                  * * HP41C MAINFRAME MICROCODE ADDRESSES @14000-15777  * ***************************************************** ****************************************************** *      COMMON MATH ENTRIES                         *** *          IF NUMBER IS 2-10,                      *** *             THEN FORM IS:                        *** *                A HAS 10-DIGIT FORM               *** *                C HAS 10-DIGIT FORM               *** *          IF NUMBER IS 1-10,                      *** *             THEN FORM IS:                        *** *                A HAS SIGN AND EXP                *** *                B HAS 13-DIGIT MANTISSA           *** *                C HAS 10-DIGIT FORM               *** *          IF NUMBER IS 2-13,                      *** *             THEN FORM IS:                        *** *                A AND B AS IN 1-10                *** *                M HAS SIGN AND EXP                *** *                C HAS 13-DIGIT MANTISSA           *** *                                                  *** *       ON EXIT, C HAS 10-DIGIT FORM               *** *                A AND B HAVE 13-DIGIT FORM        *** *                                                  *** ****************************************************** 136  115 MP2-10   56 B=0    W 137  116         172 AB EX  M 138  117 MP1-10  730 MC EX 139  120         630 C=M 140  121         106 C=0    X 141  122 MP2-13   76 B=0    S 142  123         136 C=0    S 143  124         730 MC EX 144  125        1006 C=A+C  X 145  126        1136 C=A-C  S 146  127          23 GONC   MPY110 ( 131) 147  130        1236 C=-C   S 148  131 MPY110   16 A=0    W 149  132         730 MC EX 150  133        1334 PT=    13 151  134 MPY120 1734 INC PT 152  135        1616 A SR   W 153  136          23 GOTO   MPY140 ( 140) 154  137 MPY130  456 A=A+B  W 155  140 MPY140 1142 C=C-1  PT 156  141        1763 GONC   MPY130 ( 137) 157  142        1524 ? PT=  12 158  143        1713 GONC   MPY120 ( 134) 159  144         630 C=M 160  145 MPY150  256 AC EX  W           ***ROUND, SHIFT AND NORMALIZE

Code:
144  125        1006 C=A+C  X

The algorithm uses the same digit by digit method we use when we manually calculate the product of two numbers.

The accumulator A keeps track of the sum.
The mantissa of one number is kept in B and continuously added to A while the mantissa of the other number in C is decremented digit by digit:
Code:
154  137 MPY130  456 A=A+B  W 155  140 MPY140 1142 C=C-1  PT 156  141        1763 GONC   MPY130 ( 137)

Once a digit of C is done the pointer PT is incremented and the accumulator A is shifted:
Code:
151  134 MPY120 1734 INC PT 152  135        1616 A SR   W

Easiest of course is to follow the program step by step in the debugger of an emulator.

Cheers
Thomas

PS: The algorithm is similar to the binary multiplication of my previous post. However base 10 instead of base 2 is used.
I asked a similar question on the HPCC Forum last year.
The best information I found is in the attached Algorithms PDF.
Multiplication is simple in binary:

0 * 0 = 0
0 * 1 = 0
1 * 0 = 0
1 * 1 = 1

Basically, just an AND gate.

Then you need to shift and add everything....

And HP calculators work in decimal anyway, not binary. Thank You Thomas Klemm

I was still figuring out on how to program "Peasant or binary multiplication" on
HP-12C in awhile then I try the adding up method to do the multiplication.

The peasant method is very interesting one and thank for the code for HP-11C

Thank You

Gamo
Leviset

Thank You for more in-depth information on algorithm.

Gamo
You can think of any number (even with decimals) as a polynomial of digits. Each digit is multiplied by a power of 10. For example, the number 123.4 is a polynomial ranging from 10 to the power 2 to 10 to the power -1. The digits of the number are the coefficients of the polynomial:

N(2,-1) = 1 * 10^2 + 2 * 10^1 + 3 * 10^0 + 4 * 10^(-1)

So you can multiply two numbers by multiplying the polynomials that represent them.
Hello Gamo,

nice to see that you are interested in programming elementary arithmetics! Maybe you would also enjoy to take a look into the history of computing? The book "Computing before Computers" is a very nice starting point. It is available for free http://ed-thelen.org/comp-hist/CBC.html.

One comment regarding your initial post: I know that some textbooks all over the world teach that 7 x 4 is defined to be 7 + 7 + 7 + 7. But, morally, this is wrong. 7 x 4 should always be defined to be 4 + 4 + 4 + 4 + 4 + 4 + 4.

If you go seven times running, you do it seven times. If you have seven times a cake, you have seven cakes. And if you have seven times four cakes, you have 4 + 4 + 4 + 4 + 4 + 4 + 4 cakes by definition, not the other way around.

We are lucky that multiplication of natural or even real numbers is commutative. But to fully appreciate this fact, it is good to be precise and consistent with the basic definitions. Of course, you did not state that you wanted to use the definition. So this comment is just a comment and not criticism.
Thomas
(08-04-2018 09:03 AM)Thomas Puettmann Wrote: [ -> ]...
One comment regarding your initial post: I know that some textbooks all over the world teach that 7 x 4 is defined to be 7 + 7 + 7 + 7. But, morally, this is wrong. 7 x 4 should always be defined to be 4 + 4 + 4 + 4 + 4 + 4 + 4.
Thomas

Ugh. <smell like="Common Core" />.

(Post 265)

I came across to this "Division Function" as well by using the
"Repeated Subtraction" algorithm

I decided to program this division function by using the repeated substraction.
This algorithm will work only with perfect division result so I make this program that if division is not perfect then return result as (-1)

Example: First Start f [REG]

24÷3
24 [ENTER] 3 [R/S] ---> 8

2475÷25
2475 [ENTER] 25 [R/S] ---> 99

2475÷24
2475 [ENTER] 24 [R/S] ---> -1 // Not a perfect division

Program: Division by Repeated Subtraction
Code:
 01 STO 0 02 X<>Y 03 STO 1 04 RCL 1 05 RCL 0 06   - 07 STO 1 08   1 09 CHS 10 X<>Y 11 X≤Y ? 12 GTO 26 13 RCL 1 14 X=0 ? 15 GTO 19 16   1 17 STO+2 18 GTO 04 19 RCL 2 20   1 21   + 22   0 23 STO 2 24 X<>Y 25 GTO 00 26   0 27 STO 2 28   1 29 CHS 30 GTO 00

Gamo
(08-04-2018 09:03 AM)Thomas Puettmann Wrote: [ -> ]It is available for free http://ed-thelen.org/comp-hist/CBC.html.

In Chapter One: Early Calculation on page 18 I noticed a special bone each for the square root and the cubic root.

It wasn't obvious to me how they were used:
Extracting square roots
Raíz cúbica

The 2nd link is in Spanish but you can probably still follow it when translated.

Thanks for sharing the linked documents.

Kind regards
Thomas
Reference URL's
• HP Forums: https://www.hpmuseum.org/forum/index.php
• :