Как написать машинный код регистра для Fibonacci

Ответ 1

Вот пример кода Python для имитации машины регистрации, которая выполняет задачу в 11 инструкциях:

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

Ответ 2

Я взломаю это. Поскольку вам нужен машинный код, проще всего написать относительно низкоуровневый псевдокод и работать оттуда до машинного кода. Основные вещи, о которых вам нужно подумать, - это сделать оператор if, как установить один регистр равным другому и как сделать цикл.

Я могу практически гарантировать, что есть более эффективные способы сделать это, но это должно быть началом.

Здесь псевдокод я бы сделал, предполагая, что у вас уже есть ваше предполагаемое количество итераций, > 2, в регистре '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

Это не должно быть сложно превратить в регистр:

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

Вы можете видеть, что я сохранил две строки, которые мне не нужны, где я инициализировал A и D. Так как они начинаются с 0 и считываются до 0 каждого цикла, эти строки не нужны, что делает конечный результат следующим:

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

Опять же, я уверен, что он не идеален, но он должен закрыть вас. Надеюсь, это поможет!

Изменить

Перечитав вопрос, я вижу, что в A. начинается "N". Мой алгоритм не работает с этим, поэтому мне нужно будет добавить две строки, чтобы переместить его. Кроме того, я вижу, что мое форматирование не совпадает с оригинальным OP, поэтому я изменил свой вариант на соответствие (дайте или сделайте интервал и комментарии):

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

Ответ 3

Хорошо, я думаю, это будет работать (если это не даст мне знать, и я попытаюсь исправить его.) После запуска функции просто переходите к следующей строке (так что после F1 запускается и возвращается, сразу начинается с F2)

Buckets:
A: Initial Value and Final Answer
B: First Counter
C: Second Counter
D: Adding bucket
I: Copy of C for next iteration
J: temporary bucket used for copying

1: +B,3 //loads the first counter
2: +C,4 //loads the second counter
3: -A,3,L
4: F1, 4
5: F2, 5
6: F3, 3

F1:: //makes a copy of C
  Fa: -C,Fb,Fd
  Fb: +I,Fcv //I is now the copy of C
  Fc: +J,Fa
  Fd: -J,Ff,Fg
  Ff: +C,fd
  Fg: return

F2:: //Sums B and C
  Fa: -B,Fc,Fb //adds up B 
  Fb: -C,Fd,Fe //adds up C
  Fc: +D,Fa
  Fd: +D,Fb 
  Fe: -D,Ff,Fg
  Ff: +C,Fe //Copies result to C
  Fg: return

F3:: //copys old C into B
  Fa: -I,Fb,Fc
  Fb: +B,Fa
  Fc: //return

L:: //puts value of C into A for result
  Fa: -C,Fb,DONE
  Fb: +A,Fa

Ответ 4

Напишите в терминах макрокоманд, которые вы можете реализовать.

На самом деле вам нужна только одна макро-инструкция для этой задачи, и у вас уже есть (дополнение). Обнуление ведра тривиально (удалите мраморы по одному), а также скопируйте содержимое ковша в другое ведро (ноль затем добавьте).