Make any number by repeatedly adding 2 numbers
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.