О программной реализации умножения и деления «в столбик»
Умножение положительных чисел может быть сравнительно легко реализовано путём разложения множителя по степеням двойки с последующим суммированием умножаемого, сдвинутого на соответствующее число битов влево
- 757 * 18
== 10111101012 * 100102
== 10111101012 * 102 + 10111101012 * 100002
== 101111010102 + 101111010100002
- == 13626
- Такое умножение потребует не более k-1 операций сдвига и столько же операций сложения, где k — номер старшего значащего бита положительного (беззнакового) множителя
- Следовательно, операция умножения будет работать слегка быстрее, если умножаемое больше множителя, а не наоборот
Внимательный наблюдатель может распознать в этом алгоритме умножение в столбик
Вот как это можно написать на ассемблере 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
- Здесь второй множитель считается знаковым и положительным
- Переполнение при умножении не проверяется
О реализации деления
Реализация деления положительных чисел также восходит к делению в столбик. В упрощённом варианте оно выглядит так:
757 / 18 = 10111101012 / 100102
1011110101|10010 10010 |______ 10110 |101010 10010 10010 10010 1
Или как нас учили в школе:
10111101012 / 100102
в делимом 10 значащих цифр, в делителе — 5, сдвигаем делитель на (10-5)=5 влево, т. е. умножаем на 25
10111101012 > 10010000002, первая цифра частного — 1
вычтем 10111101012 - 10010000002 = 101101012
- делитель сдвинем на 4
101101012 < 1001000002, следующая цифра частного — 0
делитель сдвинем на 3
101101012 > 100100002, следующая цифра частного — 1
вычтем 101101012 - 100100002 = 1001012
делитель сдвинем на 2
1001012 < 10010002, следующая цифра частного — 0
- делитель сдвинем на 1
1001012 > 1001002, следующая цифра частного — 1
вычтем 1001012 = 1001002 = 1
- делитель сдвинем на 0
1 < 100102 , последняя цифра — 0
Остаток — эта самая 1
Запишем результат: 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. Когда-то это заметка называлась «Об аппаратной реализации умножения и деления»: предполагалось, что описанные действия можно изваять в кремнии. Однако принципиальная схема такого «примитивного умножатора» настолько поразила моё воображение своей запутанностью, что до аппаратной реализации я так и не дошёл.