Make any number by repeatedly adding 2 numbers

Question

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?

Answer 1

CJam, 31

Like @Tobia's answer, my algorithm is also shamelessly stolen inspired by @CChak's answer. But, wielding the black magic that is CJam, I managed to make an even smaller implementation of the algorithm.

Try it here.

Golfed:

qi{_4%!:X)/X!-'xX+"
y+="@}h;]W%`

Ungolfed:

qi          "Read input and convert to integer.";
{           "Do...";
  _4%!:X    "Assign (value mod 4 == 0) to X.";
  )/X!-     "If X, divide value by 2. If not X, decrement value.";
  'xX+      "If X, put 'y' on the stack. If not X, put 'x' on the stack.";
  "
y+="        "Put '\ny+=' on the stack.";
  @         "Rotate top 3 elements of stack left so the value is on top.";
}h          "... while value is not zero.";
;           "Discard zero value on stack.";
]W%         "Collect stack into array and reverse.";

Please correct me if I'm wrong, but I believed that the modulo 65536 operation used in answers with a similar algorithm is unnecessary. I interpreted the question such that we can assume that the input will be a valid unsigned 16-bit integer, and any intermediate values or results of this algorithm will be as well.

Answer 2

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.

Answer 3

Python 3, 202 bytes

def S(n):
 q=[(1,0,"")];k=65536
 while q:
  x,y,z=q.pop(0)
  if n in{x,y}:print(z);return
  q+=[((x+y)%k,y,z+"x+=y\n"),(x,(x+y)%k,z+"y+=x\n")]+[(2*x%k,y,z+"x+=x\n")]*(~x&1)+[(x,2*y%k,z+"y+=y\n")]*(~y&1)

(Thanks to @rationalis for a few bytes)

Here's an extremely basic solution. I wish I could golf the last line better, but I'm currently out of ideas. Call with S(25).

The program just does a simple BFS with no caching, so is very slow. Here is S(97), for some sample output:

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

Answer 4

Dyalog APL, 49 chars / bytes*

{0=N←⍵|⍨2*16:⍬⋄0=4|N:⎕←'y+=y'⊣∇N÷2⋄⎕←'y+=x'⊣∇N-1}

Algorithm shamelessly inspired by @CChak's answer.

Example:

    {0=N←⍵|⍨2*16:⍬⋄0=4|N:⎕←'y+=y'⊣∇N÷2⋄⎕←'y+=x'⊣∇N-1} 25
y+=x
y+=x
y+=y
y+=x
y+=x
y+=y
y+=y
y+=x

Ungolfed:

{
    N←(2*16)|⍵                 # assign the argument modulo 65536 to N
    0=N: ⍬                     # if N = 0, return an empty value (that's a Zilde, not a 0)
    0=4|N: ⎕←'y+=y' ⊣ ∇N÷2     # if N mod 4 = 0, recurse with N÷2 and *then* print 'y+=y'
    ⎕←'y+=x' ⊣ ∇N-1            # otherwise, recurse with N-1 and *then* print 'y+=x'
}

_{* Dyalog APL supports a legacy charset which has the APL symbols mapped to the upper 128 byte values. Therefore an APL program that only uses ASCII characters and APL symbols can be considered to be bytes == chars.}

Answer 5

Python, 183

def S(n):
 b,c,e=16,'x+=x\n','x+=y\n';s=d='y+=x\n';a=i=0
 if n<2:return
 while~n&1:n>>=1;a+=1
 while n:n>>=1;s+=[e,c][i]+d*(n&1);i=1;b-=1
 while a:s+=[c,c*b+e*2][i];i=0;a-=1
 print(s)

I can't guarantee this stays within 2x the optimal program for even numbers, but it is efficient. For all valid inputs 0 <= n < 65536, it's essentially instantaneous, and generates a program of at most 33 instructions. For an arbitrary register size n (after fixing that constant), it would take O(n) time with at most 2n+1 instructions.

Some Binary Logic

Any odd number n can be reached within 31 steps: do y+=x, getting x,y = 1,1, and then keep doubling x with x+=x (for the first doubling do x+=y, since x is odd to begin with). x will reach every power of 2 this way (it's just a left-shift), and so you can set any bit of y to be 1 by adding the corresponding power of 2. Since we're using 16-bit registers, and each bit except for the first takes one doubling to reach and one y+=x to set, we get a maximum of 31 ops.

Any even number n is just some power of 2, call it a, times an odd number, call it m; i.e. n = 2^a * m, or equivalently, n = m << a. Use the above process to get m, then reset x by left-shifting it until it's 0. Do a x+=y to set x = m, and then continue to double x, the first time using x+=y and subsequently using x+=x.

Whatever a is, it takes 16-a shifts of x to get y=m and an additional a shifts to reset x=0. Another a shifts of x will occur after x=m. So a total of 16+a shifts is used. There are up to 16-a bits that need to be set to get m, and each of those will take one y+=x. Finally we need an extra step when x=0 to set it to m, x+=y. So it takes at most 33 steps to get any even number.

You can, of course, generalize this to any size register, in which case it always takes at most 2n-1 and 2n+1 ops for odd and even n-bit integers, respectively.

Optimality

This algorithm produces a program that is near-optimal (i.e. within 2n+2 if n is the minimum number of steps) for odd numbers. For a given odd number n, if the mth bit is the leading 1, then any program takes at least m steps to get to x=n or y=n, since the operation which increases the registers' values fastest is x+=x or y+=y (i.e. doublings) and it takes m doublings to get to the mth bit from 1. Since this algorithm takes at most 2m steps (at most two per doubling, one for the shift and one y+=x), any odd number is represented near-optimally.

Even numbers are not quite so good, since it always uses 16 ops to reset x before anything else, and 8, for example, can be reached within 5 steps.

Interestingly, the above algorithm never uses y+=y at all, since y is always kept odd. In which case, it may actually find the shortest program for the restricted set of only 3 operations.

Testing

# Do an exhaustive breadth-first search to find the shortest program for
# each valid input
def bfs():
    d = {(0,1):0}
    k = 0xFFFF
    s = set(range(k+1))
    current = [(0,1)]
    nexts = []
    def add(pt, dist, n):
        if pt in d: return
        d[pt] = dist
        s.difference_update(pt)
        n.append(pt)
    i = 0
    while len(s) > 0:
        i += 1
        for p in current:
            x,y = p
            add((x,x+y&k), i, nexts)
            add((y,x+y&k), i, nexts)
            if y%2 == 0: add(tuple(sorted((x,y+y&k))), i, nexts)
            if x%2 == 0: add(tuple(sorted((x+x&k,y))), i, nexts)
        current = nexts
        nexts = []
        print(len(d),len(s))

# Mine (@rationalis)
def S(n):
    b,c,e=16,'x+=x\n','x+=y\n';s=d='y+=x\n';a=i=0
    if n<2:return ''
    while~n&1:n>>=1;a+=1
    while n:n>>=1;s+=[e,c][i]+d*(n&1);i=1;b-=1
    while a:s+=[c,c*b+e*2][i];i=0;a-=1
    return s

# @CChak's approach
def U(i):
    if i<1:return ''
    return U(i//2)+'y+=y\n' if i%4==0 else U(i-1)+'y+=x\n'

# Use mine on odd numbers and @CChak's on even numbers
def V(i):
    return S(i) if i % 2 == 1 else U(i)

# Simulate a program in the hypothetical machine language
def T(s):
    x,y = 1,0
    for l in s.split():
        if l == 'x+=x':
            if x % 2 == 1: return 1,0
            x += x
        elif l == 'y+=y':
            if y % 2 == 1: return 1,0
            y += y
        elif l == 'x+=y': x += y
        elif l == 'y+=x': y += x
        x %= 1<<16
        y %= 1<<16
    return x,y

# Test a solution on all values 0 to 65535 inclusive
# Max op limit only for my own solution
def test(f):
    max_ops = 33 if f==S else 1000
    for i in range(1<<16):
        s = f(i); t = T(s)
        if i not in t or len(s)//5 > max_ops:
            print(s,i,t)
            break

# Compare two solutions
def test2(f,g):
    lf = [len(f(i)) for i in range(2,1<<16)]
    lg = [len(g(i)) for i in range(2,1<<16)]
    l = [lf[i]/lg[i] for i in range(len(lf))]
    print(sum(l)/len(l))
    print(sum(lf)/sum(lg))

# Test by default if script is executed
def main():
    test()

if __name__ == '__main__':
    main()

I wrote a simple test to check that my solution indeed produces correct results, and never goes over 33 steps, for all valid inputs (0 <= n < 65536).

In addition, I attempted to do an empirical analysis to compare my solution's output against the optimal outputs -- however, it turns out that breadth-first search is too inefficient to obtain the minimum output length for every valid input n. For example, using BFS to find the output for n = 65535 does not terminate in a reasonable amount of time. Nonetheless I've left in bfs() and am open to suggestions.

I did, however, test my own solution against @CChak's (implemented in Python here as U). I expected mine would do worse, since it is drastically inefficient for smaller even numbers, but averaged across the whole range in two ways, mine produced output of length on average 10.8% to 12.3% shorter. I thought maybe this was due to better efficiency from my own solution on odd numbers, so V uses mine on odd numbers and @CChak's on even numbers, but V is in between (about 10% shorter than U, 3% longer than S).