Make any number by repeatedly adding 2 numbers You are given a machine with two 16-bit registers, x and y. The registers are initialized x=1 and y=0. The only operation the machine can do is addition modulo 65536. That is:


x+=y - x is replaced by (x + y) mod 65536; y is unchanged
y+=x - similarly for y
x+=x - x is replaced by 2x mod 65536; legal only if x is even
y+=y - similarly for y


The goal is to get a predetermined number in one of the registers (either x or y).

Write a program or a subroutine that receives a number (in stdin, argv, function parameter, top of stack or any other conventional place), and outputs a program to get this number. The output should go to stdout, or (if your language has no stdout) to any other conventional output device.

The output program can be up to 100% plus 2 steps far from optimal. That is, if the shortest program to get the target number has n steps, your solution cannot be longer than 2n+2. This restriction is to avoid "too easy" solutions (e.g. counting 1, 2, 3, ...) but not require full optimization; I expect that the shortest program is easiest to find, but cannot be sure...

For example: Input = 25. Output:

y+=x
x+=y
x+=y
x+=x
x+=x
x+=x
y+=x


Another example: For any fibonacci number, the output has this alternating pattern. For Input = 21, output is

y+=x
x+=y
y+=x
x+=y
y+=x
x+=y
y+=x


Shortest code (measured in bytes) wins.

(this puzzle was inspired by some code for a 16-bit processor I had to generate recently)

P.S. I wonder - for which number the optimal program is longest?
Perl 107 97

First post, so here goes.

sub h{($i)=@_;return if(($i%=65536)==0);($i%4==0)?do{h($i/2);say"y+=y";}:do{h($i-1);say"y+=x";}}


Which fits all of the register addition criteria, but I didn't run an exhaustive check to see if my answer was always within 2n+2 of the optimal number of steps.  It is well inside the limit for every Fibonacci number, though.

Here is a more detailed breakdown

sub h{                           # Declare the subroutine, it should be called referencing an integer value
   ($i)=@_;                      # Assign the i variable to the integer used in the call
   return if(($i%=65536)==0);    # Check for base condition of called by 0, and enforce modulo from the start.
   ($i%4==0) ?                   # If the value passed is even, and will result in an even number if we halve it
   do{h($i/2);say"y+=y";}        # Then do so and recurse 
   :do{h($i-1);say"y+=x";}       # Otherwise "subtract one" and recurse
}                                # Note that the print statements get called in reverse order as we exit.


As I mentioned, this is my first attempt at golfing, so I'm sure this can be improved upon.  Also, I'm not sure if the initial subroutine call has to be counted in a recursive call or not, which could drive us up a few chars.

Interestingly we can reduce the code by 11 bytes* and improve our "efficiency" in terms of the number of register operations, by relaxing the requirement that only even values can be "doubled".  I've included that for fun here:

sub h{($i)=@_;return if(($i%=65536)==0);($i%2==0)?do{h($i/2);say"y+=y";}:do{h($i-1);say"y+=x";}}


Begin addendum:

Really liked this problem, and I've been fiddling with it off and on for the last couple weeks.  Thought I would post my results.

Some numbers:

Using a BFS algorithm to find an optimal solution, in the first 2^16 numbers there are only 18 numbers that require 23 steps.  They are: 58558, 59894, 60110, 61182, 61278, 62295, 62430, 62910, 63422, 63462, 63979, 64230, 64314, 4486, 64510, 64698, 64854, 65295.

Using the recursive algorithm described above, The "most difficult" number to reach is 65535, at 45 operations.  ( 65534 takes 44, and there are 14 numbers that take 43 steps)  65535 is also the largest departure from optimal, 45 vs 22.  The 23 step difference is 2n+1.  (Only three numbers hit 2n: 65534, 32767, 32751.)  Excepting the trivial (zero-step) cases, over the defined range, the recursive method averages approximately 1.4 times the optimal solution.

Bottom line: For the numbers 1-2^16, the recursive algorithm never crosses the defined threshold of 2n+2, so the answer is valid.  I suspect that it would begin to depart too far from the optimal solution for larger registers/more bits, however.

The code I used to create the BFS was sloppy, memory intensive, not commented, and quite deliberately not included.  So... you don't have to trust my results, but I'm pretty confident in them.