35s/42S mini challenge



#2

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.


#3

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


#4

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.


#5

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

#6

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


#7

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.

#8

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.


#9

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.


#10

Quote:
...get down to the target of 9.

That would be impressive; a non-bitwise operator solution in 9 steps.

Thanks.


#11

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.

#12

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.


#13

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.
#14

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.


#15

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


#16

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.


#17

Can such short programs be written to manipulate bits if the problem was using powers of 3 or powers of 5?

Namir


#18

I do not think so.

#19

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
#20

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.

Possibly Related Threads...
Thread Author Replies Views Last Post
  HPCC Mini Conference 2013 hugh steers 6 544 09-13-2013, 04:27 PM
Last Post: BruceH
  33s, 35s & 42s--The Timex(R) Factor Matt Agajanian 7 596 09-13-2013, 12:28 AM
Last Post: Matt Agajanian
  Picture from the Mini-HHC (LA) Geir Isene 11 819 07-07-2013, 01:06 PM
Last Post: Jim Horn
  My birthday, so a little commemorative mini-challenge ! Valentin Albillo 43 2,479 03-07-2013, 03:44 AM
Last Post: Walter B
  WP 34S mini-challenge (B) Gerson W. Barbosa 17 1,029 12-27-2012, 04:39 PM
Last Post: Marcus von Cube, Germany
  Maximum number of program steps in HP-42S, 33S, and 35S? Walter B 3 410 12-18-2012, 03:44 PM
Last Post: Eric Smith
  Mini-challenge: HHC2012 RPL programming contest with larger input David Hayden 14 1,042 10-05-2012, 10:36 PM
Last Post: David Hayden
  HP41 / SY41CL Mini-B USB Power Connector (Module) Matt Kernal 5 1,287 07-08-2012, 06:23 PM
Last Post: Diego Diaz
  HP-15C (& LE!) 11-11-11 Mini-Challenge Valentin Albillo 28 1,545 11-14-2011, 08:12 AM
Last Post: Valentin Albillo
  Mini challenge. CEIL / FLOOR in RPN M. Joury 47 2,730 10-31-2011, 10:11 AM
Last Post: M. Joury

Forum Jump: