The Museum of HP Calculators

HP Forum Archive 17

 35s/42S mini challengeMessage #1 Posted by Egan Ford on 20 Sept 2007, 1:22 p.m. Write in 9 steps or less of logic (LBL/RTN not counted) a program that can identify if a positive integer can be represented as 2j-2k where j>=k>=0. If so return a 0, if not return > 0. There is no need to identify j and k. NOTE: No EQN to keep it 42S friendly.

 Re: 35s/42S mini challengeMessage #2 Posted by Paul Dale on 20 Sept 2007, 5:29 p.m.,in response to message #1 by Egan Ford I've got an almost solution in 9 steps, 6 if I'm allowed to keeps a constant in a register (enter the code at step 4 in this case): ```1: 1 2: STO 00 3: X<>Y 4: RCL- 00 5: LASTx 6: OR 7: RCL+ 00 8: LASTx 9: AND ``` This is for the 42s. For the 35s, replace register 00 with A. [edit: ignore this next paragraph, I erred] The reason I said almost is that this routine returns zero for inputs of (2^n)-1 where it should return non-zero. In essence, this code is identifying the presence of a single block of binary 1's in the number rather than a single block of binary 1's with at least one lower order 0 digit. - Pauli [edit: clarified the 2^n-1 in the exception] Edited: 20 Sept 2007, 6:39 p.m. after one or more responses were posted

 Re: 35s/42S mini challengeMessage #3 Posted by Egan Ford on 20 Sept 2007, 6:27 p.m.,in response to message #2 by Paul Dale Similar to my solution, but mine is exactly the same 9 steps for the 35s, 42S, and the 16C and it returns 0 for 2j-1 (i.e. k=0). Edited: 20 Sept 2007, 6:30 p.m.

 Re: 35s/42S mini challengeMessage #4 Posted by Paul Dale on 20 Sept 2007, 6:37 p.m.,in response to message #3 by Egan Ford My mistake, the routine should return 0 for the (2^n)-1 case and my code does this. Don't know what I was thinking thinking it should return non-zero here :-( - Pauli

 Re: 35s/42S mini challengeMessage #5 Posted by Paul Dale on 20 Sept 2007, 6:40 p.m.,in response to message #3 by Egan Ford But I get down to six if I can keep the constant 1 in a register ahead of time. I'd be surprised if the 16c couldn't do this in less steps or at least in a more interesting way... - Pauli

 Re: 35s/42S mini challengeMessage #6 Posted by Paul Dale on 20 Sept 2007, 6:47 p.m.,in response to message #5 by Paul Dale Got one for the 16c: ```1: LJ 2: X<>Y 3: LBL 0 4: SL 5: F? 4 6: GT0 0 ``` Shorter and mostly slower :-) Well shorter if I don't get my pre-filled register. Only more instructions executed for cases with more than 2 sequential bits set. - Pauli Edited: 20 Sept 2007, 6:49 p.m.

 Re: 35s/42S mini challengeMessage #7 Posted by Paul Brogger on 20 Sept 2007, 7:07 p.m.,in response to message #1 by Egan Ford I tried the "divide by two, finite state machine" approach: ```A001 LBL A A002 STO A A003 0 A004 RCL A A005 IP A006 2 A007 A008 STO A A009 FP A010 x=y? A011 GTO A004 A012 X>0? A013 GTO A004 A014 RCL A A015 RTN ``` (Obviously, I miss the target # of steps.) It initializes its state (in the Y register) to zero and then starts shifting bits to the right. As long as the bit shifted into the fractional portion is a zero, it continues. When the first non-zero bit is encountered, line A013 leaves it for the new state and continues shifting right. The first zero bit encountered after encountering any non-zero bits causes the test at A012 to fail, and the last value stored is the result. (It falls into an endless loop with a zero input, but the problem specifically states "a positive integer".) I suspect there may be a way to trim it down by skipping the storage register (A) and using LASTx carefully, but I don't have the time right now. Edited: 20 Sept 2007, 7:27 p.m.

 Re: 35s/42S mini challengeMessage #8 Posted by Paul Brogger on 21 Sept 2007, 1:59 p.m.,in response to message #7 by Paul Brogger Here's a stack-only version: ```S001 LBL S S002 XEQ S013 S003 XEQ S009 S004 x<>y? S005 x>0? S006 GTO S003 S007 LASTx S008 RTN S009 LASTx S010 IP S011 2 S012 S013 FP S014 RTN ``` Same logic as before. The comparison test trick on lines S004 & 5 could be used to reduce the previous version by 1 instruction. If I may assume 0 in y, then the following requires only 10 steps of logic: ```S001 LBL S S002 GTO S007 S003 LASTx S004 IP S005 2 S006 S007 FP S008 x<>y? S009 x>0? S010 GTO S003 S011 LASTx S012 RTN ``` If I further require the user to enter "XEQ S006" to initiate the program, I can get rid of S002 and get down to the target of 9. (I suspect that won't work for the 42s, though.) Edited: 21 Sept 2007, 2:04 p.m.

 Re: 35s/42S mini challengeMessage #9 Posted by Egan Ford on 21 Sept 2007, 4:08 p.m.,in response to message #8 by Paul Brogger Quote: ...get down to the target of 9. That would be impressive; a non-bitwise operator solution in 9 steps. Thanks.

 Re: 35s/42S mini challengeMessage #10 Posted by Paul Brogger on 21 Sept 2007, 5:09 p.m.,in response to message #9 by Egan Ford Thanks to you for the challenge! And, just to spell it out: ```S001 LBL S S002 LASTx S003 IP S004 2 S005 S006 FP S007 x<>y? S008 x>0? S009 GTO S002 S010 LASTx S011 RTN ``` Enter 0 in y, the integer in question in x, and then XEQ S006. Edited: 21 Sept 2007, 5:10 p.m.

 Re: 35s/42S mini challengeMessage #11 Posted by Namir on 21 Sept 2007, 10:37 a.m.,in response to message #1 by Egan Ford My contribution wins the longest listing award!! The theory behind my program is based on finding j and k for X = 2^j - 2^k): ```X = 2^j - 2^k X + 2^k = 2^j log(X + 2^k) = j log(2) log(X + 2^k) / log(2) = j ``` When the calculated value of j has a zero fractional part we find an answer. The program loops for the values of k, starting with 0 (2^0 = 1 as the initial value of 2^k). If at the end of the loop we find that 2^k > 2^j then we stop the iteration, because it means that k > j which violates one of the requirements for the solution. The listing is: ``` A001 LBL A A002 STO X A003 1 A004 STO K A005 RCL X A006 RCL K A007 + A008 LOG A009 2 A010 STO* K A011 LOG A012 / A013 RND A014 FP A015 x=0? A016 STOP A017 LASTx A018 2 A019 y^x A020 RCL K A021 x<=y? A022 GTO A005 A023 RTN ``` I inserted the RND because dividing log values sometimes lead to .9999999999 fractions. Also note that register K stores the value of 2^k. The above approach (and program) can easily be adapted for integers other than 2. Edited: 21 Sept 2007, 12:22 p.m.

 Re: 35s/42S mini challengeMessage #12 Posted by Egan Ford on 21 Sept 2007, 4:00 p.m.,in response to message #11 by Namir Quote: My contribution wins the longest listing award!! Long, but portable. Thanks for providing a non-bitwise solution. I had hoped for one or two like this.

Re: 35s/42S mini challenge, my solution and part 2
Message #13 Posted by Egan Ford on 21 Sept 2007, 3:47 p.m.,
in response to message #1 by Egan Ford

Thank you all for participating in this mini challenge. I selected this challenge because there was more than one way to do it. The most economical way was to use the bitwise operators in the LOGIC menu of the 35s/42S. (I left a hint to consider using logic.)

Paul Dale did come up with a logical 9 step solution. Congratulations Paul!

## Part 1 Problem

Write in 9 steps or less of logic (LBL/RTN not counted) a program that can identify if a positive integer can be represented as 2j-2k where j>=k>=0. If so return a 0, if not return > 0. There is no need to identify j and k.

## Part 1 Solution

My solution is similar to Paul's and will work unmodified on the 35s, 42S, 16C, and possibility other models with bitwise operators. I have been unable to get it down to less than 9 steps.

```ENTER
ENTER
ENTER
1
-
OR
1
+
AND
```

Below is a play-by-play to explain how this works.

Consider the expression 225-217 = 33423360.

```      225 = 00000010000000000000000000000000 = 33554432
217 = 00000000000000100000000000000000 =   131072
225 - 217 = 00000001111111100000000000000000 = 33423360
```
As Paul pointed out it this problem is about identifying an single contiguous block of 1s. 2j - 2k will always be a single block of bits with the range 2k to 2j-1.

Let x = 225-217,

First subtract 1 from x then OR it with x. This replaces all right trailing zeros with 1s:

```                      x = 00000001111111100000000000000000 = 33423360
x - 1 = 00000001111111011111111111111111 = 33423359
(x - 1) | x = 00000001111111111111111111111111 = 33554431
```
Next add 1 to create a 2n number > x:
```      ((x - 1) | x) + 1 = 00000010000000000000000000000000 = 33554432
```
Lastly AND that number with x to get 0:
```      ((x - 1) | x) + 1 = 00000010000000000000000000000000 = 33554432
x = 00000001111111100000000000000000 = 33423360
(((x - 1) | x) + 1) & x = 00000000000000000000000000000000 = 0
```
Any other number without a single contigous block of 1s will fail, e.g.:
```                      x = 00000000101111000110000101001110 = 12345678
x - 1 = 00000000101111000110000101001101 = 12345677
(x - 1) | x = 00000000101111000110000101001111 = 12345679
```
The last operation did replace all the right trailing zeros with 1s (all one of them), but when adding 1 a 2n number > x is not obtained:
```      ((x - 1) | x) + 1 = 00000000101111000110000101010000 = 12345680
```
ANDing it with x does not yield 0:
```      ((x - 1) | x) + 1 = 00000000101111000110000101010000 = 12345680
x = 00000000101111000110000101001110 = 12345678
(((x - 1) | x) + 1) & x = 00000000101111000110000101000000 = 12345664
```

## Part 2 Problem

In as few steps as possible identify 2j or 2k. Obviously if you can identify one you can find the other and then use log2 to get j and k. I have a 3 step solution for 2k that is identical on the 35s/42S/16C.

 Re: 35s/42S mini challenge, my solution and part 2Message #14 Posted by Patrice on 21 Sept 2007, 8:46 p.m.,in response to message #13 by Egan Ford Part One: my Short Solution Here is my solution for HP16C, don't know for other models. Thinking this one will be hard to beat :-)) ``` LJ / left justify X<>Y / need the result rather than the number of shifts LAST X / recall original value (ENTER is OK too) B# / ask how many bits set MASKL / create a mask on left XOR / Xoring gives 0's if bits match and 1's if not ```

 Re: 35s/42S mini challenge, my solution and part 2Message #15 Posted by Egan Ford on 21 Sept 2007, 9:29 p.m.,in response to message #14 by Patrice Paul Dale also create a 6 stepper for the 16C (above). But yours is loopless. Nice. The 16C is an incredible machine with no clear replacement. It is the most unique calculator I own. I knew it'd be easy on the 16C, that is why I set the challenge for the 35s/42S. Can you do part 2? Thanks.

 Re: 35s/42S mini challenge, my solution and part 2Message #16 Posted by Namir on 23 Sept 2007, 11:05 a.m.,in response to message #15 by Egan Ford Can such short programs be written to manipulate bits if the problem was using powers of 3 or powers of 5? Namir

 Re: 35s/42S mini challenge, my solution and part 2Message #17 Posted by Egan Ford on 2 Oct 2007, 9:16 p.m.,in response to message #16 by Namir I do not think so.

 Re: 35s/42S mini challenge, my solution and part 2Message #18 Posted by Patrice on 23 Sept 2007, 4:57 p.m.,in response to message #15 by Egan Ford My solution for part2 so far. The 16C does not have the log function ```#B =k-j LST X LJ number of zeros to top X<>Y NOT #B number of zeros X<>Y - =k R/S + =j ```

Re: 35s/42S mini challenge, part 2 solution
Message #19 Posted by Egan Ford on 2 Oct 2007, 9:15 p.m.,
in response to message #13 by Egan Ford

## Part 2 Problem

In as few steps as possible identify 2j or 2k. Obviously if you can identify one you can find the other and then use log2 to get j and k. I have a 3 step solution for 2k that is identical on the 35s/42S/16C.

## Part 2 Solution

Here is my 3 step solution for 2k.
```ENTER
+/-
AND
```
To find 2k we just need to isolate the last bit, e.g.:
```       x = 00000001111111100000000000000000 = 33423360
-x = 11111110000000100000000000000000 = -33423360
(-x) & x = 00000000000000100000000000000000 = 131072
```
Thanks for playing.

Go back to the main exhibit hall