Multiply Function [x]

[Gamo]

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
adding up method.

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

[Massimo Gnerucci]

Code:


01   ×

[Pekis]

(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"

[wynen]

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

[rprosperi]

(08-03-2018 11:31 AM)Massimo Gnerucci Wrote:  

Code:


01   ×

Excellent my friend!! Great way to start a weekend, with a good laugh...

[Dave Britten]

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

[Dieter]

(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

[Thomas Klemm]

(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

[Thomas Klemm]

(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

This line adds the exponents:

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.

[Leviset]

I asked a similar question on the HPCC Forum last year.
Firstly Google CORDIC.
The best information I found is in the attached Algorithms PDF.

[ijabbott]

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.

[Gamo]

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

[Gamo]

Leviset

Thank You for more in-depth information on algorithm.


Gamo

[Namir]

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.

[Thomas Puettmann]

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

[brickviking]

(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)

[Gamo]

Thank You to everyone who gave more information about this topic.

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

[Thomas Klemm]

(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