О программной реализации умножения и деления «в столбик»

Умножение положительных чисел может быть сравнительно легко реализовано путём разложения множителя по степеням двойки с последующим суммированием умножаемого, сдвинутого на соответствующее число битов влево

Вот как это можно написать на ассемблере RISC-V (диалект RARS):

   1 # Умножение небольших положительных A и B
   2 .data
   3 A:      .word   757
   4 B:      .word   19
   5 C:      .word   0
   6 D:      .word   0
   7 
   8 .text
   9         lw      t0 A            # первый множитель
  10         lw      t1 B            # второй множитель
  11         
  12         li      t2 1            # маска бита из множителя
  13         li      t5 0            # произведение
  14         mv      t4 t1           # слагаемое = множитель * маска
  15         
  16 next:   bltz    t2 fin          # цикл остановится, когда маска заедет в знаковый бит
  17         and     t3 t0 t2        # выдекляем k-тый бит
  18         beqz    t3 noadd        # если k-ый бит == 0, складывать не надо
  19         add     t5 t5 t4        # добавляем слагаемое к результату
  20 noadd:  slli    t2 t2 1         # меняем маску: сдвигаем бит на 1
  21         slli    t4 t4 1         # умножаем слагаемое на 2
  22         b       next            # продолжаем цикл
  23 
  24 fin:    sw      t5 C t3         # сохраняем произведение
  25         mul     t6 t0 t1        # проверяем обычным умножением  
  26         sw      t6 D t3         # должно быть C == D

О реализации деления

Реализация деления положительных чисел также восходит к делению в столбик. В упрощённом варианте оно выглядит так:

Или как нас учили в школе:

Запишем результат: 101010

Вот как это можно написать на ассемблере RISC-V (диалект RARS):

   1 # Деление небольших положительных A и B с остатком
   2 .data
   3 A:      .word   757             # Делимое
   4 B:      .word   18              # Делитель
   5 C:      .word   0               # Частное
   6 D:      .word   0               # Остаток
   7 E:      .word   0               # Частное для проверки
   8 F:      .word   0               # Остаток для проверки
   9 
  10 .text
  11         lw      t1 A            # Делимое
  12         lw      t2 B            # Делитель
  13         li      t4 0            # Частное
  14         
  15         mv      t5 t1           # Остаток (он же уменьшенное делимое)
  16         mv      t3 t2           # Делитель, сдвинутый влево
  17 upper:  bgtu    t3 t1 dodiv     # Кратный делитель больше делимого :)
  18         slli    t3 t3 1         # Умножим делитель на 2
  19         b       upper
  20         
  21 dodiv:  bleu    t3 t2 done      # Кратный делитель уже меньше исходного
  22         slli    t4 t4 1         # Приписываем к частному справа 0
  23         srli    t3 t3 1         # Следующий кратный делитель
  24         blt     t5 t3 dodiv     # Остаток меньше кратного делителя, цифра 0
  25         sub     t5 t5 t3        # Вычитаем кратный делитель из остатка
  26         ori     t4 t4 1         # Цифра 1
  27         b       dodiv
  28         
  29 done:   sw      t4 C t0         # Частное
  30         sw      t5 D t0         # Остаток
  31         div     t3 t1 t2        # Проверим делением
  32         sw      t3 E t0         # Частное, должно быть C == E
  33         rem     t3 t1 t2
  34         sw      t3 F t0         # Остаток, должно быть D == F

Умножение и деление с отрицательными числами сводится к операциям с модулями и последующему определению знака (знаки сомножителей совпадают — результат положительный, знаки не совпадают — отрицательный).

P. S. Когда-то это заметка называлась «Об аппаратной реализации умножения и деления»: предполагалось, что описанные действия можно изваять в кремнии. Однако принципиальная схема такого «примитивного умножатора» настолько поразила моё воображение своей запутанностью, что до аппаратной реализации я так им не дошёл.

FrBrGeorge/InegerDivision (последним исправлял пользователь FrBrGeorge 2024-02-23 11:53:50)