Итеративное деление с фиксированной точкой на процессоре Zilog Z80

Большинство подпрограмм деления для Z80 используют некую форму восстанавливающего деления: побитовый алгоритм, который многократно сдвигает, вычитает и восстанавливает частичные остатки. Это надежный и хорошо изученный подход, но он не всегда является оптимальным для некоторых константных делителей. Вместо того чтобы вычислять частное по одному биту за раз, предложенный здесь метод многократно уточняет приближение, используя только операции сложения и сдвига. Частное получается через последовательные итерации, поскольку оно является устойчивой неподвижной точкой рекурсивного уравнения.

Чтобы объяснить эту идею, рассмотрим деление на 3:
y = x / 3
Мы можем переписать это как:
3 y = x, затем:
4 y = x + y и, наконец:
y = (x + y) / 4

Это уравнение рекурсивно: значение, которое мы пытаемся вычислить, присутствует в обеих частях. Это полезно, так как повторение итераций приближает оценку к уникальной неподвижной точке y = x / 3. Если текущая оценка слишком мала, следующая итерация увеличивает её; если слишком велика, следующая итерация уменьшает её. На Z80 деление на 4 — это просто двойной логический сдвиг вправо, поэтому мы можем многократно применять:
y = (x + y) >> 2

Полезное свойство заключается в том, что каждая итерация уменьшает остаточную ошибку примерно в четыре раза, поэтому приближение быстро улучшается. Итерация работает как построение обратной величины через геометрическую прогрессию:
1 / 3 = 1 / 4 + 1 / 16 + 1 / 64 + ...
где каждый проход добавляет новый член. Даже с учетом отбрасывания дробной части на каждом шаге, четырех итераций достаточно для получения правильного целочисленного частного во всем 8-битном диапазоне. Для 16-битных входных данных достаточно восьми итераций.

Остается один тонкий момент: каждый раз при сдвиге вправо мы теряем дробную часть значения. Это вносит небольшое смещение в меньшую сторону, которое можно компенсировать, предварительно загрузив в аккумулятор тщательно подобранную константу. Эта константа сдвигает процесс итерации вверх, чтобы итоговое значение сходилось к правильному результату. Для 8-битного делимого константа равна floor(256 / 3).

Для 16-битного делимого она равна floor(65536 / 3).

Результирующая реализация для Z80 при делении на 3 (A = B / 3) получается на удивление компактной:

      ld    a,256 / 3
      add   a,b
      rra
      srl   a
      add   a,b
      rra
      srl   a
      add   a,b
      rra
      srl   a
      add   a,b
      rra
      srl   a

Метод напрямую обобщается для более широких операндов. В отличие от 8-битного примера выше, приведенная ниже 16-битная подпрограмма (HL = DE / 3) представлена в виде цикла для краткости:

      ld    hl,65536 / 3
      ld    b,8
Div3  add   hl,de
      rr    h
      rr    l
      srl   h
      rr    l
      djnz  Div3

Обобщение идеи на делители вида 2^N - 1
Оказывается, рекурсивное уравнение имеет особенно элегантную форму для делителей, которые на единицу меньше степени двойки:
3: y = (x + y) >> 2
7: y = (x + y) >> 3
15: y = (x + y) >> 4
...

Например, деление на 7 (A = B / 7) превращается в:

      ld    c,%11111110
      ld    a,256 / 7
      add   a,b
      rra
      and   c
      rra
      rra
      add   a,b
      rra
      and   c
      rra
      rra
      add   a,b
      rra
      and   c
      rra
      rra

Маска %11111110 используется для сброса младшего бита и флага переноса, что гарантирует поведение инструкций RRA как цепочки логических сдвигов, для чего иначе потребовались бы более медленные операции SRL A.

Делители вида 2^N + 1
Другой класс элегантных подпрограмм возникает для делителей, которые на единицу больше степени двойки:
5: y = (x - y) >> 2
9: y = (x - y) >> 3
17: y = (x - y) >> 4
...

Это напоминает описанную выше рекуррентность на основе сложения. Однако в данном случае ошибка округления меняет знак между итерациями, поэтому смещение в значительной степени компенсируется само по себе. В результате константа предзагрузки не требуется.

Например, деление на 5 можно реализовать итерацией y = (x - y) >> 2, что приводит к следующей подпрограмме для A = B / 5:

      ld    c,b
      srl   c
      srl   c
      ld    a,b
      sub   c
      rra
      srl   a
      ld    c,a
      ld    a,b
      sub   c
      rra
      srl   a
      ld    c,a
      ld    a,b
      sub   c
      rra
      srl   a

Выражение x - y труднее реализовать эффективно, так как оно требует временного хранения. Однако его можно переписать как (y ^ 255) + x + 1. Инкремент можно включить в начальное значение до начала итераций. Кроме того, поскольку y никогда не превышает x, бит, сдвигаемый в аккумулятор через RRA, гарантированно равен нулю. Это позволяет использовать XOR C в коде ниже для инвертирования аккумулятора и сброса флага переноса, создавая более плотный внутренний цикл. Хотя количество циклов в данном случае не сокращается, это демонстрирует полезную контекстную оптимизацию:

      ld    c,255
      ld    a,b
      srl   a
      srl   a
      inc   b
      sub   b
      xor   c
      rra
      srl   a
      sub   b
      xor   c
      rra
      srl   a
      sub   b
      xor   c
      rra
      srl   a

Заключительные мысли
Эти подпрограммы не являются заменой делению общего назначения. Это специализированные итеративные решатели для определенных делителей, особенно для чисел рядом со степенями двойки. Но они представляют собой отличную альтернативу типичному делению: вместо извлечения битов частного по одному, они сходятся к результату, используя только сдвиги, сложения и обратную связь.

Для малых делителей оптимальный подход часто представляет собой гибрид прямого сдвига и этих специализированных решателей. Степени двойки эффективнее всего обрабатываются сдвигами вправо, в то время как близлежащие нечетные делители — хорошие кандидаты для специализированных решателей. Составные делители часто можно свести к решателю с последующим сдвигом: например, деление на 6 можно реализовать как деление на 3 с последующим сдвигом вправо, а деление на 10 — как деление на 5 с последующим сдвигом вправо.

На этом я завершаю статью. Даже спустя десятилетия есть чему поучиться.

baze / 3SC