RPN Programming exercise (HP-42S)



#73

Given two four-digit integer numbers on the stack, write an HP-42S program that returns their product in no more than 20 seconds on a real HP-42S.

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 { 77-Byte Prgm }
01>LBL "MLTA"
...
29 ROTXY
...
35 END

and, since ROTXY has been allowed,

00 { 50-Byte Prgm }
01>LBL "MLTB"
...
29 .END.

The latter has the advantage of being faster and shorter. Also, it accepts a wider range of non-fixed 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


#74

LBL MLTA
STO* Y
X<>Y
END

Edited: 23 Feb 2012, 7:51 p.m.


#75

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.


#76

Still missed some:

LBL MLT
RCL* Y
END


- Pauli


#77

Yes, thanks! I think "no multiplication of any kind (except binary shifts)" might work. Just included.

Gerson.

#78

Got one. Execution time is maybe half a second. All the example give the correct answer.


    00 { 10-Byte 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


#79

Ah, and no multiplication of any kind (except binary ones), like DOT, for instance :-)


#80

Not explicitly. Does Sigma+ count :-)

- Pauli


#81

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.


#82

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


#83

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 DEC-10 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.

#84

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.


#85

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


#86

Ahhh, yes. That would be wiser!!!

#87

I think "no multiplication of any kind (except binary shifts)" might handle this, though Pauli may not agree.

Well, to the next round :-)

Gerson.

#88

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.


#89

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.

#90

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 HP-42S here.

Cheers,

Gerson.


#91

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.

#92

Seems like we'd be allowed to use Prosthaphaeresis to solve this one using trig identities to change the multiply into an addition.


- Pauli


#93

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.


#94

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

#95

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 four-digit 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 HP-42S.

                 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 HP-42S. 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 HP-42, 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 21-step (and perhaps even shorter) program is possible:

00 { 47-Byte Prgm }
01>LBL "MLTC"
...
21 END
Example:
12 ENTER 34 ENTER 5678 XEQ MLTC  -->  7,006,652

Gerson.


#96

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.


#97

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 HP-42S? 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, left-shift 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 4-bits (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 three-times-left-shifted-larger integer into the accumulator,
- - Test 2 –if bit2 (2^2) is on then add two-times-left-shifted larger integer into the accumulator,
- - Test 3 –if bit1 (2^1) is on then add one-time-left-shifted 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 4-bits/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


#98

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.


#99

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"

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.


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.


He! He! He! ....

No complaints: I "just" used what I have on hands ....

Great problem!

Artur


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 sums-only solutions.

I am glad you have like it,

Cheers,

Gerson.


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


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.

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 HP-71B 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 10-step HP-15C 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.


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.


Artur,

There are two HP-42S functions that remained out of the restriction list: LN1+X and E^X-1. I though someone would explore this failure, but apparently they've been neglected :-)

Gerson.


And they are multiply free :-)


- Pauli

I've implemented my suggestion:


{ 102-Byte 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.


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 2-D 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 i-th digit of X (enter as "xxxx") -> a
-> a
« IF a THEN @ if i-th digit of X is non zero
1 4 FOR j
Y j j SUB STR-> @ get j-th digit of Y (enter as "yyyy") -> b
-> b
« IF b THEN @ if j-th 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


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.


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 4-car 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 i-th digit of X (enter as "xxxx") -> a
-> a
« IF a THEN @ if i-th digit of X is non zero
1 Y LENGHT FOR j
Y j j SUB STR-> @ get j-th digit of Y (enter as "yyyy") -> b
-> b
« IF b THEN @ if j-th 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 »


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.


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 un-doubtfully fit in third Gerson's category of hidden multiplication process"

Definitely a fun little exercise.

- Pauli


I agree. It was fun and made me take out my 42S again.


My 42S needed replacement batteries :-(

- Pauli

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 n-byte
; numbers together (n up to 128)
; HL: 1st operand (LSB)
; DE: 2nd operand (LSB)
; IX: 2n-byte 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 ;4-byte operands
CALL LMULT ;multiply
RET
;
;Upon running the 8-byte result  
;will be 0020343D3C221005H (LSB in C130H)

Edited: 25 Feb 2012, 9:18 p.m.

Here is a minor optimization:

{ 102-Byte 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.

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


It seems highly optimized to me! Congratulations!

Mine uses about 50% more bytes to implement a similar algorithm.

Cheers,

Gerson.

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


Oliver, can you explain the algorithm a little, please?


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

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.

Anyone willing to give one of the hardware multiplication algorithms a go?

- Pauli

Clearly, the execise...


Quote:
Given two four-digit 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!


One out of four.

- Pauli


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! ;-)


Okay, one out of three since one of the tests is a duplicate....


- Pauli

Quote:
Clearly, the execise...

Quote:
Given two four-digit 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.


Well, I finished law school - today I know what it was good for! Hehehe! ;-)


Aha! :-)

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 { 55-Byte 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 HP-42S.

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


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^X-1 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 HP-42S is one of the four-digits 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 4-digit number into two 2-digit 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 21-step additions-only solution is possible:

00 { 47-Byte 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 21-step 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.


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.


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


Thomas,

He's calculating 4a = (a + a) + (a + a), reusing the result of the first addition.

Cheers,

Gerson.


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


Sorry! I hadn't seen your point.

Gerson.

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


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.

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

[...] (34-step, 55-byte 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.


Possibly Related Threads...
Thread Author Replies Views Last Post
  [PRIME] RPN: another attempt at returning more than one value to the RPN stack Marcus von Cube, Germany 5 402 11-05-2013, 02:44 AM
Last Post: Marcus von Cube, Germany
  HHC 2013 RPN Programming Challenge - Final Thought Jeff O. 7 392 10-17-2013, 11:02 AM
Last Post: Jeff O.
  HHC / HP Museum Programming Contest for RPN and RPL machines Gene Wright 18 809 09-22-2013, 09:39 AM
Last Post: Miguel Toro
  HP 42s programming help for novice Carl D (new) 4 198 02-02-2013, 11:39 PM
Last Post: Mike Morrow
  HHC 2012 RPN Programming Contest - 10-Step Way-After-Nashville Solution Jeff O. 32 1,311 10-12-2012, 01:41 AM
Last Post: Paul Dale
  HHC 2012 RPN Programming Challenge Conundrum Jeff O. 15 558 10-08-2012, 03:34 PM
Last Post: Gerson W. Barbosa
  HHC 2012 RPN Programming Contest Gene Wright 73 1,470 09-28-2012, 12:43 PM
Last Post: x34
  HHC 2012 programming contests coming soon (RPN and RPL) Gene Wright 9 458 09-21-2012, 03:38 PM
Last Post: Paul Dale
  Programming exercise Gerson W. Barbosa 32 1,060 08-23-2012, 07:42 PM
Last Post: Gerson W. Barbosa
  Help with RPN programming hpnut 36 1,203 03-03-2012, 09:31 AM
Last Post: Bill (Smithville, NJ)

Forum Jump: