Подтвердить что ты не робот

64/32-разрядное деление на процессор с 32/16-разрядным делением

Мой процессор, маленький 16-разрядный микроконтроллер без FPU и целочисленной математики имеет только разделение 16/16 и 32/16, которые оба возьмите 18 циклов. В настоящий момент я использую очень медленную программную программу (~ 7500 циклов) для разделения 64/32. Есть ли способ использовать эти двигатели для расчета 64/32 деления? Подобно тому, как я уже использую множитель 16x16 и сумматор для вычисления умножения 32x32? Я использую C, но могу работать с любым общим объяснением того, как это можно сделать... Я надеюсь направить 200 циклов (если это вообще возможно).

4b9b3361

ОТВЕТЫ

Ответ 1

См. "Хакерский восторг", разделение многословного текста (стр. 140-145).

Основная концепция (возвращение к Кнуту) заключается в том, чтобы думать о вашей проблеме в терминах base-65536. Затем у вас есть проблема с делением на 4 цифры на 2 разряда с делением на 2 цифры в качестве примитива.

Код C здесь: http://www.hackersdelight.org/hdcodetxt/divmnu.c.txt

Ответ 2

Моя копия Knuth ( "Искусство программирования" ) работает, поэтому я не могу проверить ее до понедельника, но это будет мой первый источник. Он имеет целый раздел по арифметике.

edit: ваше сообщение о "16/16 делении и 32/16 делении, которые занимают 18 циклов". - dsPIC имеют операцию условного вычитания в сборке. Подумайте об использовании этого в качестве своего вычислительного примитива.

Также обратите внимание, что если X = XH * 2 32 + XL и D = DH * 2 16 + DL, то если вы ищете

(Q, R) = X/D, где X = Q * D + R

где Q = QH * 2 16 + QL, R = RH * 2 16 + RL, то

XH * 2 32 + XL = DH * QH * 2 32 + (DL * QH + DH * QL) * 2 16 + (DL * QL) + RH * 2 16 + RL

Это позволяет (взглянув на термины с высокими 32 битами), чтобы использовать следующую процедуру, сродни длинному делению:

  • (QH, R0) = XH/(DH + 1) → XH = QH * (DH + 1) + R0 [32/16 деление]
  • R1 = X - (QH * 2 16) * D [требуется умножение 16 * 32, сдвиг-левый на 16 и 64-битный вычитание]
  • вычислить R1 '= R1 - D * 2 16
  • while R1 ' >= 0, отрегулируйте QH вверх на 1, установите R1 = R1' и перейдите к шагу 3
  • (QL, R2) = (R1 → 16)/(DH + 1) → R1 = QL * (DH + 1) + R2 [32/16 разделение]
  • R3 = R1 - (QL * D) [требуется умножение 16 * 32 и 48-битное вычитание]
  • вычислить R3 '= R3 - D
  • пока R3 ' >= 0, отрегулируйте QL вверх на 1, установите R3 = R3' и перейдите к шагу 7

Ваш 32-битный фактор - это пара (QH, QL) и 32-разрядный остаток R3.

(Это предполагает, что коэффициент не превышает 32 бит, который вам нужно знать заранее, и его можно легко проверить заранее).

Ответ 3

Отправной точкой будет: D. Knuth, "Искусство программирования", том 2, раздел 4.3.1, "Алгоритм D

Но я полагаю, вам может понадобиться оптимизировать алгоритм.

Ответ 4

Вы можете посмотреть Booth Algorithm (http://www.scribd.com/doc/3132888/Booths-Algorithm-Multiplication-Division).

Часть, которую вы хотите, составляет около 1/2 пути вниз по странице.

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

В основном подразумевается смещение, добавление или вычитание.

Ответ 5

Я могу только предложить получить результат путем последовательного вычитания и приращения регистра результата. Попытка разбить 64-битный регистр на 2 или 4 части и делить их по отдельности - это не-go, поскольку целочисленное деление вводит ошибку.