64/32-битное деление на процессоре с 32/16-битным делением - PullRequest
Новая
       16

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

21 голосов
/ 23 января 2011

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

Ответы [ 4 ]

11 голосов
/ 23 января 2011

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

Базовая концепция (возвращаясь к Кнуту) - рассмотреть вашу проблему в терминах base-65536.Тогда у вас возникает проблема деления на 4 цифры на 2 цифры с делением на 2/1 цифры в качестве примитива.

Код C находится здесь: http://www.hackersdelight.org/hdcodetxt/divmnu.c.txt

4 голосов
/ 23 января 2011

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

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 бита) использовать следующую процедуру, сродни длинному делению:

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

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

(Предполагается, что частное не больше 32-разрядного, что необходимо знать заранее, и его можно легко проверить заранее.)

1 голос
/ 23 января 2011

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

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

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

В основном включает в себя сдвиг и сложение или вычитание.

1 голос
/ 23 января 2011

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

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

...