How to write register machine code for Fibonacci

Question

I am not sure whether this is the right place to ask this question, but since it involves programming and code, hopefully this is the right place.

I have tried to post on Programmers and Computer Science SE, but they redirected me to this site.

The question is about how can I write a register machine code/program that computes the Fibonacci number. The syntax of the code is actually really simple.

(Below are just for reference only, sorry for the long post)
(For more explanation see the book on Formal Logic: Its Scope And Limits by Richard Carl Jeffrey)

According to Wikipedia a register machine is a generic class of abstract machines used in a manner similar to a Turing machine. A (processor) register is a small amount of storage available as part of a CPU or other digital processor.

We can simplify the problem by modelling the registers as empty buckets, and we can let marbles or rocks to be put into the register ("bucket"). The rule is to add or remove marbles from the bucket to perform computations.

The rules are:
1. A register machine uses of a finite number of buckets, and an unending supply of marbles.
2. Each bucket can be individually identified. The marbles need not be distinguishable.
3. A register machine program is a finite set of instructions:
- To add marble to a bucket (and then to go on to the next instruction).
- Or to take a marble away from a bucket (and to go on to one next instruction if you can, or another one, if you can’t).
4. The program can be written in a flowchart or in a list of instructions.

Here is an example of a register machine program that performs addition.
Let A, B, C be buckets.
1. (-B; 2,4) means take away one marble from bucket B, go to instruction 2 if can, or 4 if cannot
2. (+A; 3) means add one marble to bucket A, then go to instruction 3
3. (+C; 1) means add one marble to bucket C, then go to instruction 1
4. (-C; 5,-) means take away one marble from bucket C, go to instruction 2 if can, or exit if cannot
5. (+B; 4) means add one marble to bucket B, then go to instruction 4

It is easily shown that suppose we have 3 marbles in bucket A and 2 marbles in bucket B, and 4 marbles in bucket C. After performing this algorithm, there will be |A|+|B| = 3+2 = 5 marbles in bucket A and |B|+|C| = 2+4 = 6 marbles in bucket B.

(I hope the example above is clear enough for illustration purpose)

(Now here comes the question)

Now, I would like to write a register machine code which when given an input of n in bucket A, returns (also in bucket A) the nth Fibonacci number. The Fibonacci numbers are 0 (the 0th), 1 (the 1st), 1 = 0 + 1 (the 2nd), etc. We can use any number of buckets, the goal is to write the code as simple as possible (i.e. with fewest instructions). Fibonacci recurrence relation is F(n)=F(n-1)+F(n-2) given F(0)=0 and F(1)=1.

Here is my attempt and the code:
My idea is to use bucket A as input and finally as output F(n) (since the question requires the output in bucket A), bucket B as the "counter", bucket C as the F(n-1) and bucket D as F(n-2).
1. (+C; 2)
2. (-A; 3,4)
3. (+B; 2)
4. (-D; 5,7)
5. (+A; 4)
6. (-C; 5,7)
7. (-B; 6,-)

But my code only works for up to n=2 sadly, I am struggling to make the code works for any n>2.

I have been thinking for this days and nights, I would appreciate if anyone could help me on this. Please do not hesitate to ask me for clarification if anything is unclear.

Many many thanks in advance!

Answer 1

Here is some example Python code to simulate a register machine that does the task in 11 instructions:

# Store loop counter in 4
# Store F(n) in 1
# Store F(n+1) in 2
# Redistribute 2 to 1 and 3 to get F(n+1)+F(n),0,F(n+1)
# then move back to the order F(n+1),F(n+1)+F(n),0
code={1:(-1,2,3),   # Move n to 
      2:(+4,1),     #    bin 4 to act as loop counter
      3:(+2,4),     # Initialise bin 2 with F(1)=1
      4:(-4,5,0),   # Check for completion
      5:(-2,6,8),   # redistribute F(n+1)
      6:(+1,7),     #    to bin 1
      7:(+3,5),     #    and bin 3
      8:(-1,9,10),  # Move bin 1 to
      9:(+2,8),     #    bin 2
      10:(-3,11,4), # and bin 3
      11:(+1,10)}   #    to bin 1

def fib(n):
    buckets=[0,n,0,0,0]
    instruction_pointer = 1
    while instruction_pointer:
        ins = code[instruction_pointer]
        x = ins[0]
        if x>0:
            buckets[x]+=1
            instruction_pointer = ins[1]
        else:
            x=-x
            if buckets[x]>0:
                buckets[x]-=1
                instruction_pointer = ins[1]
            else:
                instruction_pointer = ins[2]
    return buckets[1]

for n in xrange(10):
    print n,fib(n)

Answer 2

I'll take a crack at this. Since you want machine code, the easiest thing to do is write relatively low-level pseudo code, and work from there to the machine code. The major things you need to think about are how to make an if statement, how to set one register equal to another and how to do a loop.

I can practically guarantee there are more efficient ways to do this, but this should be a start.

Here's the pseudocode I would do, assuming you already have your intended number of iterations, >2, in register 'n':

A = 0
B = 1
C = 1
DO
  A = B + C // Note, this is really A = 0, A += B, A += C
  C = B  // Similarly, C = 0, C += B
  B = A  // B = 0, B += A
WHILE N- > 0

This shouldn't be hard to turn into register code:

1.   B+, 2 // B = 1
2.   C+, 3 // C = 1
3.   A-, 3, 4 // Get A down to 0 - not necessary, just here for clarity
4.   D-, 4, 5 // Get temporary variable D down to 0. - not necessary, just here for clarity
5.   B-, 6, 8 // Copy B into A (part of adding) and temporary variable D
6.     A+, 7  // A = B
7.     D+, 5  // D = B
8.   C-, 9, 10 // Add C into A = B
9.     A+, 8  // A += C
10.  N-, 11, -// Check your N count
11.    D-, 12, 13 // Copy D (the old B) into C
12.      C+, 11  // C = D
13.    A-, 14, 5 // Copy A into B
14.      B+, 13  // B = A

You can see I kept two lines I didn't need, where I initialized A and D. Since they start at 0 and get read down to 0 each loop, those lines are unnecessary, making the end result this:

1.   B+, 2                       // B = 1
2.   C+, 3                       // C = 1
3.   B-, 4, 6 // Copy B into A (part of adding) and temporary variable D
4.     A+, 5                     // A = B
5.     D+, 3                     // D = B
6.   C-, 7, 8 // Add C into A = B
7.     A+, 6                     // A += C
8.   N-, 9, -// Check your N count, or exit
9.     D-, 10, 11 // Copy D (the old B) into C
10.      C+, 9                   // C = D
11.    A-, 12, 3 // Copy A into B
12.      B+, 12                  // B = A

Again, I'm sure it's not perfect, but it should get you close. Hope this helps!

Edit

Re-reading the question, I see that "N" starts out in A. My algorithm doesn't work with that, so I would need to prepend two lines to move it. Also, I see my formatting doesn't match the original OP, so I modified mine to match (give or take spacing and comments):

1.   (-A; 2, 3) // Move the "N" value out of A into N
2.     (+N; 1)                     // N = A
3.   (+B; 4)                       // B = 1
4.   (+C; 5)                       // C = 1
5.   (-B; 6, 8) // Copy B into A (part of adding) and temporary variable D
6.     (+A; 7)                     // A = B
7.     (+D; 5)                     // D = B
8.   (-C; 9, 10) // Add C into A = B
9.     (+A; 8)                     // A += C
10.  (-N; 11, -)// Check your N count, or exit
11.    (-D; 11, 13) // Copy D (the old B) into C
12.      (+C; 11)                   // C = D
13.    (-A; 14, 5) // Copy A into B
14.      (+B; 13)                   // B = A