35s/42S mini challenge

The Museum of HP Calculators

HP Forum Archive 17

35s/42S mini challenge
Message #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 2^j-2^k 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 challenge
Message #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 challenge
Message #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 2^j-1 (i.e. k=0).
Edited: 20 Sept 2007, 6:30 p.m.

Re: 35s/42S mini challenge
Message #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 challenge
Message #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 challenge
Message #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 challenge
Message #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 <divide> 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 challenge
Message #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 <divide> 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 <divide> 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 challenge
Message #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 challenge
Message #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 <divide> 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 challenge
Message #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 challenge
Message #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 2^j-2^k 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 2²⁵-2¹⁷ = 33423360.
2²⁵ = 00000010000000000000000000000000 = 33554432 2¹⁷ = 00000000000000100000000000000000 = 131072 2²⁵ - 2¹⁷ = 00000001111111100000000000000000 = 33423360
As Paul pointed out it this problem is about identifying an single contiguous block of 1s. 2^j - 2^k will always be a single block of bits with the range 2^k to 2^j-1.
Let x = 2²⁵-2¹⁷,
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 2ⁿ 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 2ⁿ 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 2^j or 2^k. Obviously if you can identify one you can find the other and then use log₂ to get j and k. I have a 3 step solution for 2^k that is identical on the 35s/42S/16C.

Re: 35s/42S mini challenge, my solution and part 2
Message #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 2
Message #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 2
Message #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 2
Message #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 2
Message #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 2^j or 2^k. 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 2^k that is identical on the 35s/42S/16C.
Part 2 Solution
Here is my 3 step solution for 2^k.
ENTER +/- AND
To find 2^k we just need to isolate the last bit, e.g.:
x = 00000001111111100000000000000000 = 33423360 -x = 11111110000000100000000000000000 = -33423360 (-x) & x = 00000000000000100000000000000000 = 131072
Thanks for playing.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall