32-битное умножение

Автор: xrnd | Рубрика: Исходники | 31-07-2010 | Распечатать запись Распечатать запись

Эта статья посвящена разбору примера умножения 32-битных чисел на 16-битном процессоре. Как вы наверно знаете, команда MUL в 16-битном режиме позволяет умножать максимум 16-битные значения, поэтому для умножения 32-битных чисел необходим специальный алгоритм.

Умножать большие числа приходится по частям, а затем складывать эти промежуточные результаты. Чтобы всё стало понятно я напишу небольшую формулу. Допустим, нам надо умножить два 32-битных числа a и b. В результате должно получиться 64-битное число c. Обозначим как a1 — младшее слово a, a2 — старшее слово a, b1 — младшее слово b, b2 — старшее слово b. Тогда получается:

a = (a2<<16) + a1

b = (b2<<16) + b1

Символы <<16 обозначают сдвиг влево на 16 бит. По сути это то же самое, что умножить на 65536.

c = a x b = ((a2<<16) + a1) x ((b2<<16) + b2) =
= (a1 x b1) + ((a2 x b1)<<16) + ((a1 x b2)<<16) + ((a2 x b2)<<32)

Алгоритм очень напоминает способ умножения в столбик. Графически можно изобразить следующим образом:

Таким образом, в программе будет 4 этапа умножения и 3 сложения промежуточных результатов (обязательно с учётом переноса). У меня получился такой код:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
use16                   ;Генерировать 16-битный код
org 100h                ;Программа начинается с адреса 100h
 
;Полный результат умножения будет находиться в регистрах BX:CX:SI:DI
 
    mov ax,word[a]      ;AX = младшее слово a
    mul word[b]         ;Умножение на младшее слово b
    mov di,ax           ;DI = младшая часть результата
    mov si,dx           ;SI = старшая часть результата
    sub cx,cx           ;CX = 0
    sub bx,bx           ;BX = 0
 
    mov ax,word[a+2]    ;AX = старшее слово a
    mul word[b]         ;Умножение на младшее слово b
    add si,ax           ;\ Прибавление промежуточного результата
    adc cx,dx           ;/ с учётом переноса
 
    mov ax,word[a]      ;AX = младшее слово a
    mul word[b+2]       ;Умножение на старшее слово b
    add si,ax           ;\
    adc cx,dx           ; > Прибавление промежуточного результата
    adc bx,bx           ;/  с учётом переноса
 
    mov ax,word[a+2]    ;AX = старшее слово a
    mul word[b+2]       ;Умножение на старшее слово b
    add cx,ax           ;\ Прибавление промежуточного результата
    adc bx,dx           ;/ с учётом переноса
 
    mov word[c],di      ;\
    mov word[c+2],si    ; \
    mov word[c+4],cx    ; / Сохранение результата в переменной c
    mov word[c+6],bx    ;/
 
    mov ax,4C00h        ;\
    int 21h             ;/ Завершение программы
;---------------------------------------------------------------------
align 4
a   dd $FFFFFFFF
b   dd $FFFFFFFF
c   dq ?

Подобным образом можно выполнять умножение чисел любой разрядности, причём необязательно одинаковой. Например, 64 x 64 бит, 32 x 64 бит, 16 x 32 бит и т.д.

Как вывести результат на экран читайте здесь.

Комментарии: