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

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

Я попытался опубликовать информацию о программистах и компьютерных науках SE, но они перенаправили меня на этот сайт.

Вопрос о том, как я могу написать код/программу машинного реестра, который вычисляет число Фибоначчи. Синтаксис кода на самом деле очень простой.

(Ниже приведены только для справки, извините за длинный пост)
(Более подробное объяснение см. В книге "Формальная логика: ее масштабы и ограничения" Ричарда Карла Джеффри)

Согласно Википедии, машина регистрации - это общий класс абстрактных машин, используемый способом, подобным машине Тьюринга. Регистр (процессор) - это небольшой объем хранилища, доступный как часть процессора или другого цифрового процессора.

Мы можем упростить задачу, моделируя регистры как пустые ведра, и мы можем позволить помещать мрамор или камни в регистр ( "ведро" ). Правило состоит в том, чтобы добавлять или удалять мрамор из ведра для выполнения вычислений.

Правила:
1. Регистрационная машина использует конечное число ведер и бесконечную поставку мрамора.
2. Каждое ведро можно идентифицировать индивидуально. Мрамор не нужно различать.
3. Программа машинного регистра - это конечный набор инструкций:
- добавить мрамор в ведро (а затем перейти к следующей инструкции).
- Или взять мрамор из ведра (и перейти к следующему если вы можете, или другое, если вы не можете).
4. Программа может быть записана в блок-схеме или в списке инструкций.

Вот пример программы машинного регистра, который выполняет добавление.
Пусть A, B, C - ведра.
1. (-B; 2,4) означает отнять один мрамор из ведра B, перейти к инструкции 2, если может, или 4, если не может 2. (+ A; 3) означает добавить один мрамор в ведро A, затем перейти к инструкции 3
3. (+ C; 1) означает добавление одного мрамора в ведро C, затем перейдите к инструкции 1
4. (-C; 5, -) означает отнять один мрамор из ведра C, перейти к инструкции 2, если может, или выйти, если не может 5. (+ B; 4) означает добавить один мрамор в ведро B, затем перейти к инструкции 4

Нетрудно показать, что предположим, что мы имеем 3 мрамора в ковше A и 2 мрамора в ковше B и 4 мрамора в ковше C. После выполнения этого алгоритма будет | A | + | B | = 3 + 2 = 5 мраморов в ковше A и | B | + | C | = 2 + 4 = 6 мрамора в ковше B.

(Я надеюсь, что приведенный выше пример достаточно ясен для иллюстрации)

(Теперь вот вопрос)

Теперь я хотел бы написать машинный код регистра, который при задании ввода n в ведро A возвращает (также в ковше A) n-й номер Фибоначчи. Числа Фибоначчи равны 0 (0-й), 1 (1-й), 1 = 0 + 1 (второй) и т.д. Мы можем использовать любое количество ковшей, цель состоит в том, чтобы написать код как можно более простым (т.е. с наименьшее количество инструкций). Рекуррентное соотношение Фибоначчи есть F (n) = F (n-1) + F (n-2), если F (0) = 0 и F (1) = 1.

Вот моя попытка и код:
Моя идея состоит в том, чтобы использовать ведро A в качестве входного сигнала и, наконец, как выход F (n) (поскольку вопрос требует вывода в ковше A), ведро B в качестве "счетчика", ведро C в качестве F (n-1) и ведро D как 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, -)

Но мой код работает только до n = 2, я изо всех сил стараюсь, чтобы код работал для любого n > 2.

Я думал за эти дни и ночи, я был бы признателен, если бы кто-нибудь мог мне помочь в этом. Пожалуйста, не стесняйтесь спрашивать меня о разъяснении, если что-то неясно.

Большое спасибо заранее!

Ответ 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

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

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