▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Given two fourdigit integer numbers on the stack, write an HP42S program that returns their product in no more than 20 seconds on a real HP42S.
Restriction: use no *, no BASE*, no /, no BASE/, no %, no MOD, no LN, no E^X, no LOG, no 10^X.
Currently I have two programs that meet the requirements:
00 { 77Byte Prgm }
01>LBL "MLTA"
...
29 ROTXY
...
35 END
and, since ROTXY has been allowed,
00 { 50Byte Prgm }
01>LBL "MLTB"
...
29 .END.
The latter has the advantage of being faster and shorter. Also, it accepts a wider range of nonfixed format operands.
Examples:
1234 ENTER 5678 XEQ MLTA > 7,006,652
9999 ENTER XEQ MLTA > 99,980,001
12 ENTER 3456789 XEQ MLTB > 41,481,468
1234 ENTER 5678 XEQ MLTB > 7,006,652
Gerson.
_{(7:57pm) Edited to add more restrictions:}
No STO*, no STO/, no Y^X.
_{Edited again (the LAST time) for yet one more restriction}
and no multiplication of any kind (except binary shifts).
Edited: 23 Feb 2012, 8:12 p.m. after one or more responses were posted
▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
LBL MLTA
STO* Y
X<>Y
END
Edited: 23 Feb 2012, 7:51 p.m.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Ok, from now on no STO*, no STO/, no Y^X. I knew I had forgotten something :)
Gerson.
Edited: 23 Feb 2012, 7:58 p.m.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
Still missed some:
LBL MLT
RCL* Y
END
 Pauli
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Yes, thanks! I think "no multiplication of any kind (except binary shifts)" might work. Just included.
Gerson.
Posts: 3,229
Threads: 42
Joined: Jul 2006
Got one. Execution time is maybe half a second. All the example give the correct answer.
00 { 10Byte Prgm }
01 LBL "MLT"
02 ...
03 ...
04 ...
05 END
I'll leave the ...'s empty for the moment to not spoil everyone else's fun :)
 Pauli
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Ah, and no multiplication of any kind (except binary ones), like DOT, for instance :)
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
Not explicitly. Does Sigma+ count :)
 Pauli
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
When I was asked to do this exercise, the programming language was COBOL and the only restrictions were "no MULTIPLY and no DIVIDE (no * and no /)". Times have changed :)
Gerson.
Edited: 23 Feb 2012, 8:24 p.m.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
Something like this (which I've not even bothered trying):
01 0
02 +
03 LBL 00
04 ST+ L
05 DSE Y
06 GTO 00
Glacially slow but short and a certain fail on the exercise.
 Pauli
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Quote:
Glacially slow but short and a certain fail on the exercise.
This would have failed in the original COBOL exercise back in '84. Student's programs would run for about half a second or so on the university DEC10 System before being aborted. I remember we were given three sets of multiplicands, one of them (9999, 9999). Without a reasonably good algorithm, it would have been impossible.
Gerson.
Edited: 23 Feb 2012, 8:43 p.m.
Posts: 320
Threads: 59
Joined: Dec 2006
This may prompt Gerson for another restriction, but here goes:
01 LBL "MLTA"
02 sigma+
03 RCL 15
04 CLsigma
05 RTN
Should add another clear sigma as step 02 to be sure the stat registers are empty.
;)
Edited: 23 Feb 2012, 8:27 p.m.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
This is my solution if you move the CLsigma to the front of the program.
i.e.
01 LBL "MLT"
02 CLsigma
03 sigma+
04 RCL 15
 Pauli
▼
Posts: 320
Threads: 59
Joined: Dec 2006
Ahhh, yes. That would be wiser!!!
Posts: 2,761
Threads: 100
Joined: Jul 2005
I think "no multiplication of any kind (except binary shifts)" might handle this, though Pauli may not agree.
Well, to the next round :)
Gerson.
Posts: 591
Threads: 16
Joined: Feb 2012
Hi, Gerson;
maybe you should ask for logic operations and stack manipulation only. I remember the first time I red about CORDIC algorithm and the beauty of its solutions. I for one know that I need to go ahead and try some logic operations to solve math problems once in a while.
Just for the fun of it.
Cheers.
Luiz (Brazil)
(I red the proposition right now and I'm actually going to sleep. It has been a busy day and it is 00:11h right know. Wondering about how not to let the bugs byte... Show them this problem and ask them to solve, perhaps? Chances are they'll not have bugs in their solution. I'm too sleepy, not reasoning accordingly, sorry.)
Edited: 23 Feb 2012, 9:16 p.m.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Olá Luiz,
This is very simple program, it doesn't compare to the beauty of the CORDIC algorithm. I don't know whether my original solution then was the expected one or not. Only thing I know the program was compiled and run, giving the right answers. Well, the restrictions didn't say anything about memory usage. So, I did use a lot of memory. That's what I had, not time.
Cheers,
Gerson.
Posts: 2,761
Threads: 100
Joined: Jul 2005
Hello again, Luiz!
Yesterday, (or early today), after I replied to you, before going to sleep I watched this movie. Close to the end one of the characters (Mr. Jones) said:
"I left the store open, I sold my car, all because of 42. Who's giving a damn about anything else when you're wearing a 42?"
The number had appeared already a few time in the movie. I found it a coincidence as we were talking about the HP42S here.
Cheers,
Gerson.
▼
Posts: 591
Threads: 16
Joined: Feb 2012
Hi, Gerson.
Well, not to worry about guns, Magnum's and stuff! After all, isn't '42' THE answer in search for a question, mostly related to the universe and everything? A good hitchhiker knows it better... ;)
Cheers! And thanks for the tip. I'll find a way to watch it.
Luiz (Brazil)
Edited: 24 Feb 2012, 11:12 a.m.
Posts: 3,229
Threads: 42
Joined: Jul 2006
Seems like we'd be allowed to use Prosthaphaeresis to solve this one using trig identities to change the multiply into an addition.
 Pauli
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
Since I'm steadfastly refusing to write the bit shift, test, add and double algorithm for multiplication, I sat down and wrote a 34S program that uses Prosthaphaeresis. Nice, short and should be fairly fast.
I think all these commands are available on the 42S  the only one I've any doubt about is the final ROUNDI (round to integer) which can be done using FIX 00 and a round.
01: LBL A
02: 1/x
03: ACOS
04: x[<>] Y
05: 1/x
06: ACOS
07: ENTER[^]
08: RCL+ Z
09: R[v]
10: 
11: COS
12: R[^]
13: COS
14: +
15: 1/x
16: RCL+ X
17: ROUNDI
18: END
There are no multiplies or divides here. If exception is taken to the 1/x commands, they can be replaced by any command that reduces an integer argument into a [1, 1] range.
This code fails if either argument is zero but that would be easy to check for by putting a not equal to zero condition test before each of the 1/x commands.
 Pauli
Edited: 24 Feb 2012, 2:39 a.m.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
Actually, thinking about this a little more...
This code works fine for smallish integers positive or negative but fails as they get larger. The reason is a loss of accuracy due to the cosine operations. Thus, it would seem better to use a variant based on SIN of the original numbers not COS.
Essentially, as N becomes large, COS(1/N) tends to 1 quadratically, whereas SIN(1/N) tends to 0 linearly. Also, we can represent a lot more small numbers around zero than around one. Thus SIN(1/N) is far better for large N.
 Pauli
Posts: 2,761
Threads: 100
Joined: Jul 2005
Quote:
Since I'm steadfastly refusing to write the bit shift, test, add and double algorithm for multiplication, I sat down and wrote a 34S program that uses Prosthaphaeresis.
It really doesn't pay to use this method just to multiply those two fourdigit numbers together. I've cared about restricting logarithms, but I've forgotten about prosthaphaeresis. No problem, posing too many restrictions may prevent creative solutions to appear, so it's a good thing it has been left out. 0 BASE+ is an equivalent to ROUNDI that doesn't change the number format.
The traditional multiplication algorithm may require up to 1149 sums, if I am not wrong. That's better than up to 9999 but would take more than 100 seconds on the HP42S.
1 2 3 4
5 6 7 8

9 8 7 2
8 6 3 8
7 4 0 4
6 1 7 0

7 0 0 6 6 5 2
A variation can be imagined that will require up to 299 sums, which would take about 30 seconds on the HP42S. I've used a method that will always perform 200 sums, no matter the operands, at the cost of using more memory. Unfortunately string manipulation is very limited on the HP42, so the problem would requires less steps and no multiplication at all (no ROTXY) if the multiplicands had not a fix format. For instance, if one of the multiplicands can be splitted in two parts, then a 21step (and perhaps even shorter) program is possible:
00 { 47Byte Prgm }
01>LBL "MLTC"
...
21 END
Example:
12 ENTER 34 ENTER 5678 XEQ MLTC > 7,006,652
Gerson.
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
I would try to translate the number in X into a string and get the digits off the string. Then it's just a matter of multiplication by a value between 0 and 10. This can easily be implemented via an indirect subroutine call where each subroutine does some tricky adds (assume the stack is filled with the number):
LBL 09
+ * 2
ENTER
+ * 4
ENTER
+ * 8
+ * 9
RTN
To save steps, some routines (04, 08) may be factored out. The complete algorithm would involve a sequence of multiplication of the previous result by 10, multiplication of the multiplicand by the next digit of the multiplier, and an addition to the result. Repeat until the multiplier contains no more digits.
▼
Posts: 260
Threads: 0
Joined: Oct 2008
Dear Marcus, I think you are on the right track!
I am currently looking for a solution close to your process. But since only binary operations are allowed, I would have suggested translating the two integers into binary.
The idea is to accumulate the larger of the two integers into an accumulator that will contain the product at the end of the algorithm. The smaller will be considered as (down)counter.
At each step, I will only consider three cases:
Step1  The (down)counter is zero; end of multiplication.
Step2 – If the last bit of the (down) counter is one, the larger integer is add one time in the accumulator.
Step3  The larger integer is shift one bit to the left whereas (down) counter is shift one bit to the right and process resumes at step 1.
I am not sure this will be easily implemented into a HP42S? And whether a large operation will fit or not to the time limit.
Note, that to speed up the process, the last byte of the (down)counter may be considered instead of only a bit. In this case, depend of value of the ‘byte’ the larger integer has to be added into the accumulator more than one time. To achieve this, leftshift of it may be useful to spare operation since it is equivalent to a multiplication by 2. Considering binary representation of integers may help here to find the needed trick!
For example, algorithm using a byte of 4bits (a nibble) :
Step1  The (down)counter is zero; end of multiplication.
Step2 – Considering the last byte (a nibble) of the (down) counter :
  Test 1 –if bit3 (2^3) is on then add threetimesleftshiftedlarger integer into the accumulator,
  Test 2 –if bit2 (2^2) is on then add twotimesleftshifted larger integer into the accumulator,
  Test 3 –if bit1 (2^1) is on then add onetimeleftshifted larger integer into the accumulator,
  Test 4 –if bit0 (2^0) is on then add larger integer into the accumulator,
Step3  The larger integer is shift one byte to the left
whereas the (down) counter is shift one byte (a 4bits/nibble) to the right (with no carry)
and process resumes at step 1.
Still seeking how to implement all this efficiently…
Edited: 24 Feb 2012, 2:18 p.m. after one or more responses were posted
▼
Posts: 1,477
Threads: 71
Joined: Jan 2005
I had to actually program and use this in the real world for my work many years ago.
IBM VM/370 had a scripting language called EXEC (here's the manual). It allowed for addition and subtraction but no other arithmetic operations. However it had functions for substring, concatenate and length and basic looping and conditionals. All variables were essentially strings but the addition and subtraction operators would treat the strings as numbers. I needed an integer multiplication function that worked the same way and had to come up with how to do that in EXEC and it had to run on some pretty large integers.
Edited: 24 Feb 2012, 1:28 p.m.
▼
Posts: 260
Threads: 0
Joined: Oct 2008
If EXEC is able of addition and handle numerics mostly as strings,
an algorithm based on successive additions that sequentially consider unit, tens, tausend, etc. may have to be considerate.
As an illustration:
5678 x 1234 :
= 5678 x 4 : "5678" + "5678" + "5678" + "5678"
+ 56780 x 3 : + "56780" + "56780" + "56780"
+ 567800 x 2 : + "567800" + "567800"
+ 5678000 x 1 : + "5678000"
________________ : _________________________
"7006652"
Posts: 127
Threads: 21
Joined: Jul 2006
Dear Sirs,
May I try something in my HP15C ???? It is very fast and no +  * /, or log and ln or exp...
f LBL D
STO 0
X >< Y (X SWAP Y)
0
X >< Y
f INTEGRATE 0
g RTN
f LBL 0
RCL 0
g RTN
Well, we don't have bit manipulation on 15C ...
Best regards!
Artur
Edited: 24 Feb 2012, 1:32 p.m.
▼
Posts: 591
Threads: 16
Joined: Feb 2012
Hi, Artur; tudo certo? (is everything OK?)
Quote: (...)and no +  * /, or log and ln or exp...
Hey! These are all embedded into INTEGRATE! I vote for 'cheating!' qB^D (hehehe...)
Cheers.
Luiz (Brazil)
Edited: 24 Feb 2012, 1:48 p.m.
▼
Posts: 127
Threads: 21
Joined: Jul 2006
He! He! He! ....
No complaints: I "just" used what I have on hands ....
Great problem!
Artur
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Olá Artur,
Quote:
Great problem!
But not properly written... Anyway, the good thing is this has allowed for imaginative solutions using commands and functions with implicit multiplications, like yours, Chuck's and Pauli's. (I am not criticizing Namir's instant solution  it perfectly complied to the rules at the time of posting :)
So it appears the solution falls under three categories:
1) Mostly sums and occasional bits rotation, as is my first solution;
2) Mostly bits rotation, as my second solution and Werner's highly optmized program;
3) Mainly implicit multiplications (Sigma+, COS, Integrate).
Perhaps we should include a fourth category, using free format operands, like (1 2 3 4 and 5678) or (12 34 and 5678) or even (12 34 ) for calculator which don't have string handling. This might make things easier for sumsonly solutions.
I am glad you have like it,
Cheers,
Gerson.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
I am fairly sure that the COS function on the 42S is implemented using CORDIC. No multiplications hidden in there, everything is shift and add. I'll agree that sigma+ definitely uses multiply and integrate almost certainly does.
The modulo 2 PI reduction for COS doesn't apply to my program either, all arguments to COS are small enough to not need this. The only operation I've any doubt about is the reciprocal which might or might not be implemented using division and there is quite possibly an alternate way to range reduce the integers.
 Pauli
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Quote:
No multiplications hidden in there, everything is shift and add. I'll agree that sigma+ definitely uses multiply and integrate almost certainly does.
You're quite right! I am aware of this, but somehow that escaped me. Sorry!
Gerson.
Posts: 1,755
Threads: 112
Joined: Jan 2005
Quote:
Dear Sirs,
May I try something in my HP15C ???? It is very fast and no +  * /, or log and ln or exp...
I came up with the same "solution" for the HP71B where the simple statement:
INTEGRAL(0,X,0,Y)
will return the product of X and Y at once. For instance:
> INTEGRAL(0,41,0,271)
11111
By the way, your 10step HP15C program can be made one step shorter this way:
01 LBL A
02 STO 0
03 CLX
04 X<>Y
05 INTEG 0
06 RTN
07 LBL 0
08 RCL 0
09 RTN
Best regards from V.
▼
Posts: 127
Threads: 21
Joined: Jul 2006
I have to admit: here is the place of gods ... the OlymHPus!!!
I, a simple mortal, can't beat you!
Thanks for appreciating my "cheating" solution I was just ashemed to put one involving logs:
a * b = c
log(a*b) = log(c)
logC = log B + log B
so:
c = 10^(logA + logB)
f LBL A
g LOG
X >< Y
g LOG
+
G 10^X
G RTN
For positive numbers, but there will be a small error for big numbers.
Artur
Edited: 24 Feb 2012, 7:51 p.m.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Artur,
There are two HP42S functions that remained out of the restriction list: LN1+X and E^X1. I though someone would explore this failure, but apparently they've been neglected :)
Gerson.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
And they are multiply free :)
 Pauli
Posts: 3,283
Threads: 104
Joined: Jul 2005
I've implemented my suggestion:
{ 102Byte Prgm }
01*LBL "MUL"
02 CLA
03 ARCL ST Y Y in Alpha
04 STO 01 X in 01
05 0
06 STO 00 Start with zero
07*LBL 99
08 48
09 ATOX
10 X=0?
11 GTO 98 End of the string, done!
12 X<Y?
13 GTO 99 Take care of ',' delimiters
14 X<>Y
15 
16 STO 02 Index of subroutine, digit value
17 RCL 00 Sum
18 ENTER
19 ENTER
20 ENTER
21 XEQ 09
22 STO+ 00 10 * sum
23 RCL 01 X
24 ENTER
25 ENTER
26 ENTER
27 XEQ IND 02 Multiply by digit
28 STO+ 00 Add to sum
29 GTO 99 Next digit
.
30*LBL 98
31 RCL 00 Show result and quit
32 RTN
.
33*LBL 00 * 0
34 0 fall through
.
35*LBL 01 * 1
36 RTN
.
37*LBL 03 * 3
38 + fall through
.
39*LBL 02 * 2
40 +
41 RTN
.
42*LBL 08 * 8 = * 2 * 4
43 +
44 ENTER
45 ENTER fall through
.
46*LBL 04 * 4 = * 2 * 2
47 +
48 ENTER
49 GTO 02 Final * 2
.
50*LBL 05 * 5 = * 4 + * 1
51 XEQ 04
52 GTO 02 Final add
.
53*LBL 06 * 6 = * 3 * 2
54 XEQ 03
55 ENTER
56 GTO 02 Final * 2
.
57*LBL 07 * 7 = * 8  * 1
58 XEQ 08
59 R^ ST Y is no longer correct after XEQ 08
60 
61 RTN
.
62*LBL 09 * 9 = * 8 + * 1
63 XEQ 08
64 R^
65 GTO 02 Final add
.
66 .END.
There is room for improvement, e. g. the first multiplication by 10 can be avoided with a flag. But the routine is pretty fast anyway (2 to 3 seconds for a 4 digit multiplier).
From my knowledge of COBOL this could come pretty close to what a solution would have been because numbers are (or can be) stored as strings in COBOL.
▼
Posts: 260
Threads: 0
Joined: Oct 2008
Your specific way to treat factor from 0 (obvious) to 9 give me a fool idea of using matrix and indirect addressing to compute the product.
Here a version into RPL, since RPN indexing of 2D matrix makes code difficult to read.
@ integers X and Y enter as 4 digits string (ex. "1234" "5678")
«
[[ 1 2 3 4 5 6 7 8 9 ] @ 9x9 matrix containing magic numbers
[ 2 4 6 8 10 12 14 16 18 ]
[ 3 6 9 12 15 18 21 24 27 ]
[ 4 8 12 16 20 24 28 32 36 ]
[ 5 10 15 20 25 30 35 40 45 ]
[ 6 12 18 24 30 36 42 48 54 ]
[ 7 14 21 28 35 42 49 56 63 ]
[ 8 16 24 32 40 48 56 64 72 ]
[ 9 18 27 36 45 54 63 72 81 ]]
[[ 1000000 100000 10000 1000 ] @ 4x4 matrix containing product factors of ten
[ 100000 10000 1000 100 ]
[ 10000 1000 100 10 ]
[ 1000 100 10 1 ]]
> X Y PRD FCT @ "xxxx" "yyyy" 9x9 4x4 store in respective local variable
« 0 @ Initiate accumulator to zero
1 4 FOR i
X i i SUB STR> @ get ith digit of X (enter as "xxxx") > a
> a
« IF a THEN @ if ith digit of X is non zero
1 4 FOR j
Y j j SUB STR> @ get jth digit of Y (enter as "yyyy") > b
> b
« IF b THEN @ if jth digit of Y is non zero
'PRD' { a b } GET >STR @ get product of a by b and convert into string
'FCT' { i j } GET >STR @ get factor for i x j and convert into string
2 7 SUB + @ keep only trailling zero string and concat it at end of product string
STR> + @ accumulate into accumulator (numeric)
END
»
NEXT @ process with next digit of Y
END
»
NEXT @ continue with next digit of X
»
» @ at end accumulator contains product X.Y
Note that
'PRD' { a b } GET >STR
'FCT' { i j } GET >STR 2 7 SUB + STR> +
may have been convert into
'PRD' { a b } GET
'FCT' { i j } GET * +
But, multiplications are illegal today !!
Edited: 24 Feb 2012, 6:34 p.m. after one or more responses were posted
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
Your solution is limited to 4 digit numbers (and fails on the 12*3456789 example). What makes it less efficient is that you do a digit by digit multiplication while my implementation multiplies longer numbers by values from 0 to 10. It's even possible to multiply an integer with an arbitrary number because the multiplicand is treated as is, only the multiplier is split into digits.
▼
Posts: 260
Threads: 0
Joined: Oct 2008
You are right.
The above version is limited to strictly 4 caracters integer string for the sake of clarity. Even low integer have to be enter as 4car string : i.e. 12 x 345 have to be type as "0012"x"0345".
And your alose are right, the algorithm is far less efficient since it have to cross every digits of the two integer. This makes exactly 16 cycles.
« SWAP >STR SWAP >STR @ integers X and Y both convert ti string
[[ 1 2 3 4 5 6 7 8 9 ] @ 9x9 matrix containing magic numbers
[ 2 4 6 8 10 12 14 16 18 ]
[ 3 6 9 12 15 18 21 24 27 ]
[ 4 8 12 16 20 24 28 32 36 ]
[ 5 10 15 20 25 30 35 40 45 ]
[ 6 12 18 24 30 36 42 48 54 ]
[ 7 14 21 28 35 42 49 56 63 ]
[ 8 16 24 32 40 48 56 64 72 ]
[ 9 18 27 36 45 54 63 72 81 ]]
> X Y PRD @ "xxxxxxx" "yyyyyy" 9x9 store in respective local variable
« 0 @ Initiate accumulator to zero
1 X LENGTH FOR i
X i i SUB STR> @ get ith digit of X (enter as "xxxx") > a
> a
« IF a THEN @ if ith digit of X is non zero
1 Y LENGHT FOR j
Y j j SUB STR> @ get jth digit of Y (enter as "yyyy") > b
> b
« IF b THEN @ if jth digit of Y is non zero
'PRD' { a b } GET >STR @ get product of a by b and convert into string
"000000000000"
1
X Y + LENGTH i j +  @ extract string of zero depending of rank
SUB + @ concat it at end of product string
STR> + @ accumulate into accumulator (numeric)
END
»
NEXT @ process with next digit of Y
END
»
NEXT @ continue with next digit of X
»
»
This last version make possible integer of any length. But, as you point it out, is a lot of thinks except efficient and sparse.
Since yesterday, I found another way to make the multiplication without multiplication :
The two integers have to be input as singleton vector (with only one element).
For exemple 3456x8976 may have been type on HP28S as :
« [ 3456 ] [ 8976 ] DOT »
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Quote:
Since yesterday, I found another way to make the multiplication without multiplication :
The two integers have to be input as singleton vector (with only one element).
For exemple 3456x8976 may have been type on HP28S as :
« [ 3456 ] [ 8976 ] DOT »
Quoting myself above, 23 Feb 2012, 8:05 p.m.:
"Ah, and no multiplication of any kind (except binary ones), like DOT, for instance :)"
Interesting solutions you all have been providing. I hope you're having fun :)
Gerson.
▼
Posts: 260
Threads: 0
Joined: Oct 2008
Yes ! A lot of fun.
Making multiplication codes without multiplication, is much more fun than riding a bicycle without it.
The end of my last message was lost during the cut&paste process.
"This code undoubtfully fit in third Gerson's category of hidden multiplication process"
Posts: 3,229
Threads: 42
Joined: Jul 2006
Definitely a fun little exercise.
 Pauli
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
I agree. It was fun and made me take out my 42S again.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
My 42S needed replacement batteries :(
 Pauli
Posts: 2,761
Threads: 100
Joined: Jul 2005
Years ago I read about the Russian peasant multiplication algorithm (that's the one I have used in my second program). I found it quite suitable for the Z80 microprocessor, which lacks multiplication as you know. It was quite fun writing a program based on the method then. This exercise made me look for it in my backup files. Why would anyone want to multiply binary numbers this long anyway? :)
_{
; LMULT: Multiplies two nbyte
; numbers together (n up to 128)
; HL: 1st operand (LSB)
; DE: 2nd operand (LSB)
; IX: 2nbyte result (LSB)
; B: n
;
ORG D000H
LMULT: XOR A ;A < 0
LD C,B ;save B onto C
SLA B ;B < B*2
PUSH IX ;save IX on the stack
LMULT0: LD (IX+0),A ;initialize result
INC IX ;
DJNZ LMULT0 ;
POP IX ;retrieve IX from the stack
...
...
...
;Test data
ORG C100H ;1st op address (LSB)
DW 0201H ;04030201H
DW 0403H
ORG C110H ;2nd op address (LSB)
DW 0605H ;08070605H
DW 0807H
;
;Test routine
;
ORG D100H
LD HL,C100H ;1st operand
LD DE,C110H ;2nd operand
LD IX,C130H ;result
LD B,4 ;4byte operands
CALL LMULT ;multiply
RET
;
;Upon running the 8byte result
;will be 0020343D3C221005H (LSB in C130H)}
Edited: 25 Feb 2012, 9:18 p.m.
Posts: 3,283
Threads: 104
Joined: Jul 2005
Here is a minor optimization:
{ 102Byte Prgm }
01*LBL "MUL"
02 X>Y?
03 X<>Y Force smaller value to be multiplier
04 FS 00 This is to avoid the first multiplication by 10
05 CLA
06 ARCL ST Y Y in Alpha
07 STO 01 X in 01
08 0
09 STO 00 Start with zero
10*LBL 99
11 48 ASCII code for '0'
12 ATOX
13 X=0?
14 GTO 98 End of the string, done!
15 X<Y?
16 GTO 99 Take care of ',' delimiters
17 X<>Y
18 
19 STO 02 Index of subroutine, digit value
20 FS?C 00
21 GTO 97 Avoid multiplication in first step
22 RCL 00 Sum
23 ENTER
24 ENTER
25 ENTER
26 XEQ 09
27 STO+ 00 10 * sum
28*LBL 97
29 RCL 01 X
30 ENTER
31 ENTER
32 ENTER
33 XEQ IND 02 Multiply by digit
34 STO+ 00 Add to sum
35 GTO 99 Next digit
.
36*LBL 98
37 RCL 00 Show result and quit
38 RTN
.
39*LBL 00 * 0
40 0 fall through
.
41*LBL 01 * 1
42 RTN
.
43*LBL 03 * 3
44 + fall through
.
45*LBL 02 * 2
46 +
47 RTN
.
48*LBL 08 * 8 = * 2 * 4
49 +
50 ENTER
51 ENTER fall through
.
52*LBL 04 * 4 = * 2 * 2
53 +
54 ENTER
55 GTO 02 Final * 2
.
56*LBL 05 * 5 = * 4 + * 1
57 XEQ 04
58 GTO 02 Final add
.
59*LBL 06 * 6 = * 3 * 2
60 XEQ 03
61 ENTER
62 GTO 02 Final * 2
.
63*LBL 07 * 7 = * 8  * 1
64 XEQ 08
65 R^ ST Y is no longer correct after XEQ 08
66 
67 RTN
.
68*LBL 09 * 9 = * 8 + * 1
69 XEQ 08
70 R^
71 GTO 02 Final add
.
72 .END.
If the smaller number (the multiplier) isn't integer, it's treated as if it did not contain a decimal point. So 1.1 ENTER 2 XEQ"MUL" will yield 22.
Execution time is always in the vicinity of 2 seconds.
Posts: 163
Threads: 7
Joined: Jul 2007
32 bytes
*LBL "M"
STO+ ST X
15
ENTER
CLX
*LBL 02
STO+ ST X
RDN
BIT?
X=0?
GTO 00
RUP
RCL+ ST T
RDN
*LBL 00
RUP
DSE ST Y
GTO 02
END
Adjust the constant 15 for larger numbers.
Cheers,
Werner
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
It seems highly optimized to me! Congratulations!
Mine uses about 50% more bytes to implement a similar algorithm.
Cheers,
Gerson.
Posts: 275
Threads: 41
Joined: Mar 2010
Less optimized, but ok for even a 41 (less than 20 sec)
01 lbl 'MLTA
02 x<=y?
03 x<>y
04 sto 00
05 clx
06 sto 01
07 x<>y
08*lbl 00
09 rcl 00
10 x<>y
11 1
12 x=y?
13 gto 09
14 st+ x
15*lbl 01
16 enter^
17 +
18 r^
19 st+ t
20 rdn
21 x<=y?
22 gto 01
23 clx
24 lastx
25*lbl 09
26 
27 x<>y
28 st+ 01
29 x<>y
30 x#0?
31 gto 00
32 rcl 01
33 end
And works for any number (but not for 0 * x)
Olivier
It build two series : for a * b (with a < b, to be faster)
i s
1 b special case with gto 09 to finish properly
2 b
4 2*b
8 4*b
16
when i > a, sum s and substract i/2 (it's the last x) from a and
loop again at lbl 00 until zero
Simple classic algorithm in binary :)
Edited: 24 Feb 2012, 5:50 p.m. after one or more responses were posted
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
Oliver, can you explain the algorithm a little, please?
▼
Posts: 275
Threads: 41
Joined: Mar 2010
Same algorithm for 42s :
01 lbl 'MLTA
02 x>y?
03 x<>y
04 sto 00
05 clx
06 sto 01
07 x<>y
08 1
09*lbl 00
10 rcl 00
11 x=0?
12 gto 02
13 rcl st y
14 and
15 x=0?
16 gto 01
17 sto 00
18 clx
19 rcl st z
20 sto+ 01
21*lbl 01
22 rdn
23 sto+ st x
24 x<>y
25 sto+ st x
26 x<>y
27 gto 00
28*lbl 02
29 rcl 01
30 .end.
but avoid multi loops
Posts: 2,761
Threads: 100
Joined: Jul 2005
Quote:
Less optimized, but ok for even a 41
Nice!
Quote:
And works for any number (but not for 0 * x)
Just insert x=0? ret between steps 07 and 08.
Regards,
Gerson.
Posts: 3,229
Threads: 42
Joined: Jul 2006
Anyone willing to give one of the hardware multiplication algorithms a go?
 Pauli
Posts: 429
Threads: 31
Joined: Jul 2011
Clearly, the execise...
Quote:
Given two fourdigit integer numbers on the stack
...does not say which two numbers should be on the stack. So I propose the following program that produces the result from the example given by Gerson, well within all restrictions:
01 LBL "EGG"
02 7006652
03 END
1234 ENTER 5678 XEQ EGG > 7006652
Tadaaaa! ;)
...and it's fast!
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
▼
Posts: 429
Threads: 31
Joined: Jul 2011
Quote:
One out of four.
 Pauli
One out of two with four digit integer numbers, as per the initial exercise text. I could accomodate for the 9999 example with a simple test which is also amongst the non forbidden functions. So still Tadaaa! ;)
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
Okay, one out of three since one of the tests is a duplicate....
 Pauli
Posts: 2,761
Threads: 100
Joined: Jul 2005
Quote:
Clearly, the execise...
Quote:
Given two fourdigit integer numbers on the stack
...does not say which two numbers should be on the stack.
You're not wrong. I should have written "given any two ". After I finished high school I attended Law School for two boring weeks. I should have stayed a little longer, at least until I became smarter :)
Gerson.
▼
Posts: 429
Threads: 31
Joined: Jul 2011
Well, I finished law school  today I know what it was good for! Hehehe! ;)
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Posts: 735
Threads: 34
Joined: May 2007
As you haven't excluded SQRT and x^2 I used them in a poor man's aproach to implement logarithm (A) and exponentiation (B):
00 { 55Byte Prgm }
01 LBL "MULT"
02 XEQ A
03 X<>Y
04 XEQ A
05 +
06 XEQ B
07 IP
08 1
09 +
10 RTN
11 LBL A
12 RCL 00
13 X<>Y
14 LBL 00
15 SQRT
16 DSE ST Y
17 GTO 00
18 X<>Y
19 RDN
20 1
21 
22 RTN
23 LBL B
24 1
25 +
26 RCL 00
27 X<>Y
28 LBL 01
29 x^2
30 DSE ST Y
31 GTO 01
32 X<>Y
33 RDN
34 END
Initialize register 00 with 40 to meet the specifications of your 3 examples. However I guess it will only work with Free42 due to the lack of precision of the original HP42S.
Quote:
and no multiplication of any kind (except binary shifts).
The implementation of x^2 probably uses multiplication so I might get disqualified. Still a nice challenge and lots of cool solutions.
Thanks
Thomas
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Hello Thomas,
Quote:
The implementation of x^2 probably uses multiplication so I might get disqualified
That's another one I forgot :)
I forgot LN1+X and E^X1 also. These surely use CORDIC.
Quote:
Still a nice challenge and lots of cool solutions.
I am glad you have liked it. Yes, I like them all, even the ones that try to circumvent the rules :) (I don't mean yours)
The idea of the original exercise is how one would implement multiplication in a machine that lacks it. Since I used a bit shift instruction in my first solution, this allows for the more efficient binary shift and add multiplication, as in my unoptimized second solution. Back to the original problem, it would be easier to implement it on the HP42S is one of the fourdigits operands could be entered in chunks of 1 or 2 digits, for instance 1, 2, 3 and 4, or 12 and 34. In my first solution, I've use many steps just to split one 4digit number into two 2digit numbers. That's not so easy to do given the restrictions. Perhaps a better variation would be allowing all digits of one of the operands to be entered individually or in chunks of two digits, like 12 ENTER 34 ENTER 5678, for instance. Then, a 21step additionsonly solution is possible:
00 { 47Byte Prgm }
01>LBL "MLTC"
...
21 END
Example:
12 ENTER 34 ENTER 5678 XEQ MLTC > 7,006,652
Contrary to what I said earier in this thread, we can do it performing no more than 100 sums, depending of our approach. Both approaches below would take up many steps, I think. In my 21step solution 200 additions are always made, no matter the operands. The program is short but 100 numbered registers are used, that's the drawback. I will post my solutions tomorrow night, in case someone still wants to try one of these or other methods.
_{
1 2 3 4
5 6 7 8

9 8 7 2 (1234 * 9) up to 8 sums  (1234 * 8) up to 8 sums
8 6 3 8 (1234 * 7 * 10) up to 18 sums  (1234 * 7 * 10) up to 18 sums
7 4 0 4 (1234 * 6 * 100) up to 108 sums  (1234 * 6 * 10 * 10) up to 28 sums
6 1 7 0 (1234 * 5 * 1000) up to 1008 sums  (1234 * 5 * 10 * 10 * 10) up to 38 sums
   
7 0 0 6 6 5 2 up to 1145 sums  up to 95 sums
(1234 + 1234 + 1234 + 1234 + 1234 + 1234 + 1234 + 1234) = 9 872
(1234 + 1234 + 1234 + 1234 + 1234 + 1234 + 1234) = 8638; (8638 + 8638 + ... + 8638) = 86 380
(1234 + 1234 + 1234 + 1234 + 1234 + 1234) = 7404; (7404 + 7404 + ... + 7404) = 740 400
(1234 + 1234 + 1234 + 1234 + 1234) = 6170; (6170 + 6170 + ... + 6170) = 6 170 000

7 006 652
(1234 + 1234 + 1234 + 1234 + 1234 + 1234 + 1234 + 1234) = 9 872
(1234 + 1234 + 1234 + 1234 + 1234 + 1234 + 1234) = 8638; (8638 + 8638 + ... + 8638) = 86 380
(1234 + 1234 + 1234 + 1234 + 1234 + 1234) = 7404; (7404 + 7404 + ... + 7404) = 74040; (74040 + 74040 + ... + 74040) = 740 400
(1234 + 1234 + 1234 + 1234 + 1234) = 6170; (6170 + 6170 + ... + 6170) = 61700; (61700 + 61700 + ... + 61700) = 617000; (617000 + 617000 + ... + 617000) = 6 170 000

7 006 652
}
Cheers,
Gerson.
Edited: 26 Feb 2012, 11:41 a.m.
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
My approach saves additions by grouping them:
To multiply by 4, instead of 4 additions, only 2 are necessary. Another addition and you get the multiplication by 8. You'll need no more then 4 additions for any multiplier between 0 and 9.
▼
Posts: 735
Threads: 34
Joined: May 2007
Quote:
To multiply by 4, instead of 4 additions, only 2 are necessary.
Only 3 additions are needed to calculate 4a = a + a + a + a.
Cheers
Thomas
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Thomas,
He's calculating 4a = (a + a) + (a + a), reusing the result of the first addition.
Cheers,
Gerson.
▼
Posts: 735
Threads: 34
Joined: May 2007
That's understood. I just wanted to point out that you need only 3 and not 4 additions to calculate a + a + a + a. Never mind: it's not that important.
Thomas
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Sorry! I hadn't seen your point.
Gerson.
Posts: 2,761
Threads: 100
Joined: Jul 2005
I see. A multiply by ten, required for both approaches above, could be done this way:
01 LBL "TEN*"
02 STO+ ST X
03 ENTER
04 STO+ ST X
05 STO+ ST X
06 +
07 END
That is, 4 additions instead of 9. So the maximum number of additions required by the second approach would be 65, even if multiplications up to 9 were made by simple addition loops (for lesser code size, perhaps).
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
I didn't think of using STO + ST X instead of ENTER +. It will save filling the stack with X but otherwise the program will not change much.
Posts: 1,755
Threads: 112
Joined: Jan 2005
Quote:
As you haven't excluded SQRT and x^2 I used them in a poor man's aproach to implement logarithm (A) and exponentiation (B):
[...] (34step, 55byte program) [...]
If you're going to use x^2 then there's no need for such a convolute approach, this much simpler code will do:
01 LBL A
02 STO ST Z
03 X<>Y
04 STO ST Z
05 +
06 X^2
07 X<>Y
08 X^2
09 
10 4
11 /
12 RTN
which doesn't use square roots either and further the final division by 4 can be replaced by a mere shift if desired.
Example:
41, ENTER, 271, XEQ A > 11111.0000
Best regards from V.
