Минимальный набор системы команд

Тема в разделе "WASM.ZEN", создана пользователем fplab, 5 мар 2007.

  1. nobodyzzz

    nobodyzzz New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2005
    Сообщения:
    475
    fplab
    Ну у нас в университете был курс теория алгоритмов я о машине Шёнфилда услышал там. Могу пошустрить конспект лекций. Если надо еще...
     
  2. Mikl_

    Mikl_ New Member

    Публикаций:
    0
    Регистрация:
    14 ноя 2006
    Сообщения:
    907
    nobodyzzz
    Интересно как XOR или MOV организовать через INC/DEC?
     
  3. fplab

    fplab Алексей

    Публикаций:
    0
    Регистрация:
    10 мар 2005
    Сообщения:
    24
    Адрес:
    Russia
    Если несложно, пошустрите, пожалуйста :)
     
  4. Freeman

    Freeman New Member

    Публикаций:
    0
    Регистрация:
    10 фев 2005
    Сообщения:
    1.385
    Адрес:
    Ukraine
    вобщето в алгебра логики любая ЛФ может быть представлена в базисе И-ИЛИ-НЕ, при чем И и ИЛИ взаимозаменяемы. по крайней мере нас так учили. на этих элементах строили и суматоры, рассматреволе схему умножения деления. по этому сколнен согласится с Mikl__ насчет mov/or/not
     
  5. Mikl_

    Mikl_ New Member

    Публикаций:
    0
    Регистрация:
    14 ноя 2006
    Сообщения:
    907
    Atlantic
    Сложение через логические операции и сдвиг: пусть мы складываем X=1011b Y=1110b
    +1011 = X X + Y = (X xor Y) + 2(X & Y) на каждом шаге будем получать частичную сумму
    1110 = Y и переносы из предыдущих разрядов, до тех пор пока либо частичная сумма,
    0101 = X xor Y частичная сумма либо переносы не станут равными нулю, причем если
    10100 = 2(X&Y) переносы слагаемые равны, получаем сдвиг влево на первом шаге
    10001
    001000
    11001
    0000000
    0011001
     
  6. Freeman

    Freeman New Member

    Публикаций:
    0
    Регистрация:
    10 фев 2005
    Сообщения:
    1.385
    Адрес:
    Ukraine
    ага. и если не ошибаюсь на той же схеме можно получить вычитание в допкодах.
     
  7. Mikl_

    Mikl_ New Member

    Публикаций:
    0
    Регистрация:
    14 ноя 2006
    Сообщения:
    907
    FreeManCPM
    Не ошибаешься;)
     
  8. Atlantic

    Atlantic Member

    Публикаций:
    0
    Регистрация:
    22 июн 2005
    Сообщения:
    322
    Адрес:
    Швеция
    Mikl__
    Плюс справа - это, я так понимаю, XOR? В итоге, обошлись стрелкой Пирса и сдвигом влево на 1 бит - 2 операции.
     
  9. Mikl_

    Mikl_ New Member

    Публикаций:
    0
    Регистрация:
    14 ноя 2006
    Сообщения:
    907
    Atlantic
    Плюс справа - это арифметический плюс, подробности смотрите внимательно в #25 количество операций для сложения, в конечном итоге, (так же как и для умножения) зависит от вида слагаемых (сомножителей) Минимальный набор: стрелка Пирса, mov, shl/shr, jcc
     
  10. Atlantic

    Atlantic Member

    Публикаций:
    0
    Регистрация:
    22 июн 2005
    Сообщения:
    322
    Адрес:
    Швеция
    Mikl__
    А, вот теперь врубился - это было тождество записано. Применяя его последовательно, можно свести второе слагаемое к нулю, и тогда первое будет равно искомой сумме.
     
  11. Mikl_

    Mikl_ New Member

    Публикаций:
    0
    Регистрация:
    14 ноя 2006
    Сообщения:
    907
    Atlantic
    IMHO операции INC/DEC внутри АЛУ организованы схемотехнически в виде двоичных счетчиков, а не на основе сложения/вычитания с 1
    Для любителей "прятать" операции:
    X xor Y = (X or Y)-(X and Y)
    X and Y = (X or Y)-(X xor Y)
    X + Y = (X or Y)+(X and Y)
     
  12. GanDJuStas

    GanDJuStas New Member

    Публикаций:
    0
    Регистрация:
    11 мар 2003
    Сообщения:
    21
    Адрес:
    Russia
    В универе был курс "Теория программирования" на котором доказали, что система опреаций
    mov [переменная],0
    mov [переменная1],[переменная2]
    inc [переменная]
    cmp [переменная1],[переменная2]
    jz/jnz
    Является полной, то есть с её помощью можно реализовать любой вычислительный алгоритм для натуральных чисел.
    А если зафиксировать рамер переменной, то можно реализовывать алгоритмы для целых чисел.
     
  13. nobodyzzz

    nobodyzzz New Member

    Публикаций:
    0
    Регистрация:
    13 июл 2005
    Сообщения:
    475
    вот собсно пошустрил. соре за задержку=))
    http://ifolder.ru/2246727
     
  14. fplab

    fplab Алексей

    Публикаций:
    0
    Регистрация:
    10 мар 2005
    Сообщения:
    24
    Адрес:
    Russia
    Благодарствую !!! Непременно посмотрю
     
  15. fplab

    fplab Алексей

    Публикаций:
    0
    Регистрация:
    10 мар 2005
    Сообщения:
    24
    Адрес:
    Russia
    После перерыва, вызванного тяжким внедрением очередного проекта, появилось, наконец, время почитать о машинах Шенфилда. Все показалось странно знакомым, все это когда-то встречалось. Поясню.
    Открываю книгу Марвина Минского "Вычисления и автоматы" в которой весьма подробно, с примерами и картинками описана машина практически в точности совпадающая с описанием машины Шенфилда. Правда, о самом Шенфилде - почему-то ни слова :)
    Ладно, думаю, поищу дальше - может корифей забыл о Шенфилде или переводчики "постарались" (что, кстати, вряд ли - в те времена книги по математике переводили профессионалы, да и редакторскую работу выполняли минимум КФМ, а часто и доктора).
    Открываю книгу Дж.Булоса и Р.Джеффри "Вычислимость и логика". То же самое: главы 6 и 7 посвящены вычислениям на абаке - по сути той же машине Шенфилда. О самом Шенфилде - ни слова. Авторы солидные, издательство солидное, не первое издание - ну не могли они не упомянуть Шенфилда :)
    Открываю, наконец, самого Шенфилда и его "Математическую логику"; никакой машины и близко не нахожу.
    То, что называется машиной Шенфилда - по сути обычные регистровые машины, рассмотренные не раз и не два в самых различных книгах и курсах. Обычно, сначала описывают машины Тьюринга, потом плавно переходят к тезису Черча после чего рассказывают о регистровых машинах. Вопрос, конечно, риторический, но, может, знатоки матлогики просветят - при чем тут Шенфилд ?
     
  16. fplab

    fplab Алексей

    Публикаций:
    0
    Регистрация:
    10 мар 2005
    Сообщения:
    24
    Адрес:
    Russia
    Вот, нарыл чуток: http://en.wikipedia.org/wiki/Counter_machine_models
    Кстати, забавная подборка :)
     
  17. Ra_

    Ra_ New Member

    Публикаций:
    0
    Регистрация:
    4 мар 2007
    Сообщения:
    289