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
(08-03-2018 11:31 AM)Massimo Gnerucci Wrote: [ -> ]
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: [ -> ]
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
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.
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.
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)
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