Алгоритм быстрого деления двоичных чисел

В настоящее время я создаю 16-битный ALU с использованием Logisim (т.е. только логические вентили) и застрял в процессе деления. В настоящее время я просто использую простой стандартный «цикл алгоритма деления» (как показано ниже):

  1. Чтение входных значений;
  2. Сравните входные значения. Дождитесь завершения процесса сравнения;
  3. Если A‹B, перейдите к шагу 10. Если AB, перейдите к следующему шагу;
  4. Вычесть Б из А;
  5. Дождитесь завершения процесса вычитания;
  6. Добавьте один для подсчета;
  7. Дождитесь завершения процесса подсчета;
  8. Записать значение из процесса вычитания на вход;
  9. Перейти к шагу 1;
  10. Ответ: подсчет остатка A

Это, однако, занимает очень много времени для процессов с большими ответами (повторение цикла из 300 тиков 65 000 раз не весело). Мне просто интересно, есть ли аналогичные более быстрые алгоритмы (использующие исключительно сложение и/или вычитание и/или умножение и любую логическую логику), которые можно было бы реализовать с использованием логических вентилей. Будем признательны за любую помощь или идеи! Фрейзер


binary logic algorithm division
person Fraser Price    schedule 22.10.2013    source источник
comment
Наверняка есть и другие алгоритмы деления. На какие из них вы смотрели и что делает их непригодными для вашей работы?   -  person    schedule 23.10.2013

Ответы (2)


arrow_upward
4
arrow_downward

Используйте длинное деление. В двоичном формате нет умножения, поскольку частное в каждой битовой позиции может быть только 1 или 0. Таким образом, его можно реализовать как условное вычитание (вычитание, если результат неотрицательный) и сдвиг.

Это только грубый набросок, конечно.

person rici    schedule 22.10.2013

arrow_upward
2
arrow_downward

Типичным подходом для деления 32/16:16+16 было бы хранение делимого в паре 16-битных регистров (которые обновляются во время работы), а делителя в собственном регистре (который не обновляется). Шестнадцать раз вычесть из делителя старшие 17 бит делимого; если результат заимствования, отбросить результат и сдвинуть делитель влево на одну позицию, поставив 0 в младший бит. Если нет результатов заимствования, сохраните результат в делителе, сдвигая его влево, но поместите 1 в младший бит. После шестнадцати таких шагов младшие 16 бит регистра делимого будут содержать частное, а старшие 16 бит — остаток. Обратите внимание, что эта операция будет работать только в том случае, если частное может быть представлено 16 битами. Заметим также, что на процессоре, реализующем деление 32/16:16+16 таким образом, можно удобно делить произвольно большие числа на 16-битную величину, поскольку старшие 16 бит делимого для каждого шага должны быть остатком от предыдущий шаг.

person supercat    schedule 01.11.2013