The Museum of HP Calculators

HP Forum Archive 20

 RPN Programming exercise (HP-42S)Message #1 Posted by Gerson W. Barbosa on 23 Feb 2012, 7:45 p.m. 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

 Re: RPN Programming exercise (HP-42S)Message #2 Posted by Namir on 23 Feb 2012, 7:50 p.m.,in response to message #1 by Gerson W. Barbosa ```LBL MLTA STO* Y X<>Y END ``` Edited: 23 Feb 2012, 7:51 p.m.

 Re: RPN Programming exercise (HP-42S)Message #3 Posted by Gerson W. Barbosa on 23 Feb 2012, 7:54 p.m.,in response to message #2 by Namir 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.

 Re: RPN Programming exercise (HP-42S)Message #4 Posted by Paul Dale on 23 Feb 2012, 7:59 p.m.,in response to message #3 by Gerson W. Barbosa Still missed some: ```LBL MLT RCL* Y END ``` - Pauli

 Re: RPN Programming exercise (HP-42S)Message #5 Posted by Gerson W. Barbosa on 23 Feb 2012, 8:09 p.m.,in response to message #4 by Paul Dale Yes, thanks! I think "no multiplication of any kind (except binary shifts)" might work. Just included. Gerson.

 Re: RPN Programming exercise (HP-42S)Message #6 Posted by Paul Dale on 23 Feb 2012, 7:59 p.m.,in response to message #1 by Gerson W. Barbosa 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

 Re: RPN Programming exercise (HP-42S)Message #7 Posted by Gerson W. Barbosa on 23 Feb 2012, 8:05 p.m.,in response to message #6 by Paul Dale Ah, and no multiplication of any kind (except binary ones), like DOT, for instance :-)

 Re: RPN Programming exercise (HP-42S)Message #8 Posted by Paul Dale on 23 Feb 2012, 8:14 p.m.,in response to message #7 by Gerson W. Barbosa Not explicitly. Does Sigma+ count :-) - Pauli

 Re: RPN Programming exercise (HP-42S)Message #9 Posted by Gerson W. Barbosa on 23 Feb 2012, 8:20 p.m.,in response to message #8 by Paul Dale 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.

 Re: RPN Programming exercise (HP-42S)Message #10 Posted by Paul Dale on 23 Feb 2012, 8:32 p.m.,in response to message #9 by Gerson W. Barbosa 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

 Re: RPN Programming exercise (HP-42S)Message #11 Posted by Gerson W. Barbosa on 23 Feb 2012, 8:41 p.m.,in response to message #10 by Paul Dale 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.

 Re: RPN Programming exercise (HP-42S)Message #12 Posted by Chuck on 23 Feb 2012, 8:26 p.m.,in response to message #1 by Gerson W. Barbosa 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.

 Re: RPN Programming exercise (HP-42S)Message #13 Posted by Paul Dale on 23 Feb 2012, 8:29 p.m.,in response to message #12 by Chuck 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

 Re: RPN Programming exercise (HP-42S)Message #14 Posted by Chuck on 23 Feb 2012, 8:31 p.m.,in response to message #13 by Paul Dale Ahhh, yes. That would be wiser!!!

 Re: RPN Programming exercise (HP-42S)Message #15 Posted by Gerson W. Barbosa on 23 Feb 2012, 8:31 p.m.,in response to message #12 by Chuck I think "no multiplication of any kind (except binary shifts)" might handle this, though Pauli may not agree. Well, to the next round :-) Gerson.

 Re: RPN Programming exercise (HP-42S)Message #16 Posted by Luiz C. Vieira (Brazil) on 23 Feb 2012, 9:13 p.m.,in response to message #1 by Gerson W. Barbosa 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.

 Re: RPN Programming exercise (HP-42S)Message #17 Posted by Gerson W. Barbosa on 23 Feb 2012, 9:33 p.m.,in response to message #16 by Luiz C. Vieira (Brazil) 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.

 Re: RPN Programming exercise (HP-42S)Message #18 Posted by Gerson W. Barbosa on 24 Feb 2012, 8:01 a.m.,in response to message #16 by Luiz C. Vieira (Brazil) 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.

 Re: RPN Programming exercise (HP-42S)Message #19 Posted by Luiz C. Vieira (Brazil) on 24 Feb 2012, 8:21 a.m.,in response to message #18 by Gerson W. Barbosa 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.

 Re: RPN Programming exercise (HP-42S)Message #20 Posted by Paul Dale on 23 Feb 2012, 11:21 p.m.,in response to message #1 by Gerson W. Barbosa Seems like we'd be allowed to use Prosthaphaeresis to solve this one using trig identities to change the multiply into an addition. - Pauli

 Re: RPN Programming exercise (HP-42S)Message #21 Posted by Paul Dale on 24 Feb 2012, 2:37 a.m.,in response to message #20 by Paul Dale 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.

 Re: RPN Programming exercise (HP-42S)Message #22 Posted by Paul Dale on 24 Feb 2012, 2:47 a.m.,in response to message #21 by Paul Dale 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

 Re: RPN Programming exercise (HP-42S)Message #23 Posted by Gerson W. Barbosa on 24 Feb 2012, 7:39 a.m.,in response to message #21 by Paul Dale 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.

 Re: RPN Programming exercise (HP-42S)Message #24 Posted by Marcus von Cube, Germany on 24 Feb 2012, 10:35 a.m.,in response to message #23 by Gerson W. Barbosa 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.

 Re: RPN Programming exercise (HP-42S)Message #25 Posted by C.Ret on 24 Feb 2012, 11:31 a.m.,in response to message #24 by Marcus von Cube, Germany 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

 Re: RPN Programming exercise (HP-42S)Message #26 Posted by Katie Wasserman on 24 Feb 2012, 1:27 p.m.,in response to message #25 by C.Ret 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.

 Re: RPN Programming exercise (HP-42S)Message #27 Posted by C.Ret on 24 Feb 2012, 5:06 p.m.,in response to message #26 by Katie Wasserman 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" ```

 Re: RPN Programming exercise (HP-42S)Message #28 Posted by Artur-Brazil on 24 Feb 2012, 1:29 p.m.,in response to message #25 by C.Ret 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.

 Re: RPN Programming exercise (HP-42S)Message #29 Posted by Luiz C. Vieira (Brazil) on 24 Feb 2012, 1:39 p.m.,in response to message #28 by Artur-Brazil 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.

 Re: RPN Programming exercise (HP-42S)Message #30 Posted by Artur-Brazil on 24 Feb 2012, 2:00 p.m.,in response to message #29 by Luiz C. Vieira (Brazil) He! He! He! .... No complaints: I "just" used what I have on hands .... Great problem! Artur

 Re: RPN Programming exercise (HP-42S)Message #31 Posted by Gerson W. Barbosa on 24 Feb 2012, 2:50 p.m.,in response to message #30 by Artur-Brazil 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.

 Re: RPN Programming exercise (HP-42S)Message #32 Posted by Paul Dale on 24 Feb 2012, 5:58 p.m.,in response to message #31 by Gerson W. Barbosa 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

 Re: RPN Programming exercise (HP-42S)Message #33 Posted by Gerson W. Barbosa on 24 Feb 2012, 6:17 p.m.,in response to message #32 by Paul Dale 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.

 Re: RPN Programming exercise (HP-42S)Message #34 Posted by Valentin Albillo on 24 Feb 2012, 5:32 p.m.,in response to message #28 by Artur-Brazil 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. ``` ```

 Re: RPN Programming exercise (HP-42S)Message #35 Posted by Artur-Brazil on 24 Feb 2012, 7:50 p.m.,in response to message #34 by Valentin Albillo 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.

 Re: RPN Programming exercise (HP-42S)Message #36 Posted by Gerson W. Barbosa on 24 Feb 2012, 8:11 p.m.,in response to message #35 by Artur-Brazil 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.

 Re: RPN Programming exercise (HP-42S)Message #37 Posted by Paul Dale on 24 Feb 2012, 9:09 p.m.,in response to message #36 by Gerson W. Barbosa And they are multiply free :-) - Pauli

 Re: RPN Programming exercise (HP-42S)Message #38 Posted by Marcus von Cube, Germany on 24 Feb 2012, 4:40 p.m.,in response to message #24 by Marcus von Cube, Germany 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 XY 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.

 Re: RPN Programming exercise (HP-42S)Message #39 Posted by C.Ret on 24 Feb 2012, 6:12 p.m.,in response to message #38 by Marcus von Cube, Germany 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

 Re: RPN Programming exercise (HP-42S)Message #40 Posted by Marcus von Cube, Germany on 24 Feb 2012, 6:21 p.m.,in response to message #39 by C.Ret 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.

 Re: RPN Programming exercise (HP-42S)Message #41 Posted by C.Ret on 25 Feb 2012, 11:57 a.m.,in response to message #40 by Marcus von Cube, Germany 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 »`

 Re: RPN Programming exercise (HP-42S)Message #42 Posted by Gerson W. Barbosa on 25 Feb 2012, 12:09 p.m.,in response to message #41 by C.Ret 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.

 Re: RPN Programming exercise (HP-42S)Message #43 Posted by C.Ret on 25 Feb 2012, 12:31 p.m.,in response to message #42 by Gerson W. Barbosa 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"

 Re: RPN Programming exercise (HP-42S)Message #44 Posted by Paul Dale on 25 Feb 2012, 4:08 p.m.,in response to message #42 by Gerson W. Barbosa Definitely a fun little exercise. - Pauli

 Re: RPN Programming exercise (HP-42S)Message #45 Posted by Marcus von Cube, Germany on 25 Feb 2012, 7:08 p.m.,in response to message #44 by Paul Dale I agree. It was fun and made me take out my 42S again.

 Re: RPN Programming exercise (HP-42S)Message #46 Posted by Paul Dale on 25 Feb 2012, 7:50 p.m.,in response to message #45 by Marcus von Cube, Germany My 42S needed replacement batteries :-( - Pauli

 Re: RPN Programming exercise (HP-42S)Message #47 Posted by Gerson W. Barbosa on 25 Feb 2012, 9:12 p.m.,in response to message #45 by Marcus von Cube, Germany 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.

 Re: RPN Programming exercise (HP-42S)Message #48 Posted by Marcus von Cube, Germany on 25 Feb 2012, 11:01 a.m.,in response to message #38 by Marcus von Cube, Germany 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 XY 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.

 Re: RPN Programming exercise (HP-42S)Message #49 Posted by Werner on 24 Feb 2012, 1:48 p.m.,in response to message #1 by Gerson W. Barbosa 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

 Re: RPN Programming exercise (HP-42S)Message #50 Posted by Gerson W. Barbosa on 24 Feb 2012, 3:05 p.m.,in response to message #49 by Werner It seems highly optimized to me! Congratulations! Mine uses about 50% more bytes to implement a similar algorithm. Cheers, Gerson.

 Re: RPN Programming exercise (HP-42S)Message #51 Posted by Olivier De Smet on 24 Feb 2012, 5:25 p.m.,in response to message #49 by Werner 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

 Re: RPN Programming exercise (HP-42S)Message #52 Posted by Marcus von Cube, Germany on 24 Feb 2012, 5:34 p.m.,in response to message #51 by Olivier De Smet Oliver, can you explain the algorithm a little, please?

 Re: RPN Programming exercise (HP-42S)Message #53 Posted by Olivier De Smet on 25 Feb 2012, 2:43 a.m.,in response to message #52 by Marcus von Cube, Germany 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

 Re: RPN Programming exercise (HP-42S)Message #54 Posted by Gerson W. Barbosa on 25 Feb 2012, 2:36 p.m.,in response to message #51 by Olivier De Smet 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.

 Re: RPN Programming exercise (HP-42S)Message #55 Posted by Paul Dale on 24 Feb 2012, 6:34 p.m.,in response to message #1 by Gerson W. Barbosa Anyone willing to give one of the hardware multiplication algorithms a go? - Pauli

 EGG solution ;-)Message #56 Posted by Alexander Oestert on 25 Feb 2012, 5:53 a.m.,in response to message #1 by Gerson W. Barbosa 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!

 Re: EGG solution ;-)Message #57 Posted by Paul Dale on 25 Feb 2012, 6:09 a.m.,in response to message #56 by Alexander Oestert One out of four. - Pauli

 Re: EGG solution ;-)Message #58 Posted by Alexander Oestert on 25 Feb 2012, 6:50 a.m.,in response to message #57 by Paul Dale 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! ;-)

 Re: EGG solution ;-)Message #59 Posted by Paul Dale on 25 Feb 2012, 7:01 a.m.,in response to message #58 by Alexander Oestert Okay, one out of three since one of the tests is a duplicate.... - Pauli

 Re: EGG solution ;-)Message #60 Posted by Gerson W. Barbosa on 25 Feb 2012, 10:42 a.m.,in response to message #56 by Alexander Oestert 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.

 Re: EGG solution ;-)Message #61 Posted by Alexander Oestert on 25 Feb 2012, 11:26 a.m.,in response to message #60 by Gerson W. Barbosa Well, I finished law school - today I know what it was good for! Hehehe! ;-)

 Re: EGG solution ;-)Message #62 Posted by Gerson W. Barbosa on 25 Feb 2012, 11:52 a.m.,in response to message #61 by Alexander Oestert Aha! :-)

 Re: RPN Programming exercise (HP-42S)Message #63 Posted by Thomas Klemm on 26 Feb 2012, 3:01 a.m.,in response to message #1 by Gerson W. Barbosa 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

 Re: RPN Programming exercise (HP-42S)Message #64 Posted by Gerson W. Barbosa on 26 Feb 2012, 10:36 a.m.,in response to message #63 by Thomas Klemm 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.

 Re: RPN Programming exercise (HP-42S)Message #65 Posted by Marcus von Cube, Germany on 26 Feb 2012, 12:25 p.m.,in response to message #64 by Gerson W. Barbosa 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.

 Re: RPN Programming exercise (HP-42S)Message #66 Posted by Thomas Klemm on 26 Feb 2012, 1:00 p.m.,in response to message #65 by Marcus von Cube, Germany 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

 Re: RPN Programming exercise (HP-42S)Message #67 Posted by Gerson W. Barbosa on 26 Feb 2012, 1:20 p.m.,in response to message #66 by Thomas Klemm Thomas, He's calculating 4a = (a + a) + (a + a), reusing the result of the first addition. Cheers, Gerson.

 Re: RPN Programming exercise (HP-42S)Message #68 Posted by Thomas Klemm on 26 Feb 2012, 1:33 p.m.,in response to message #67 by Gerson W. Barbosa 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

 Re: RPN Programming exercise (HP-42S)Message #69 Posted by Gerson W. Barbosa on 26 Feb 2012, 3:20 p.m.,in response to message #68 by Thomas Klemm Sorry! I hadn't seen your point. Gerson.

 Re: RPN Programming exercise (HP-42S)Message #70 Posted by Gerson W. Barbosa on 26 Feb 2012, 1:06 p.m.,in response to message #65 by Marcus von Cube, Germany 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).

 Re: RPN Programming exercise (HP-42S)Message #71 Posted by Marcus von Cube, Germany on 26 Feb 2012, 1:50 p.m.,in response to message #70 by Gerson W. Barbosa 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.

 Re: RPN Programming exercise (HP-42S)Message #72 Posted by Valentin Albillo on 26 Feb 2012, 11:48 a.m.,in response to message #63 by Thomas Klemm 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. ``` ```

Go back to the main exhibit hall