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 бит и т.д.
Как вывести результат на экран читайте здесь.
31-07-2010 20:34
что такое dq?? 8 байт?
31-07-2010 21:31
Да. Подробнее можно прочитать здесь:
http://asmworld.ru/uchebnyj-kurs/005-direktivy-obyavleniya-dannyx/
25-12-2010 22:07
А каким образом результат вывести на экран?
25-12-2010 22:16
Для этого нужно преобразовать число в строку символов, а затем строку вывести на экран. Подробно об этом написано тут:
http://asmworld.ru/uchebnyj-kurs/022-vyvod-chisel-na-konsol/
26-12-2010 11:31
Спасибо, мне было известно как вывести слово на экран, но в результате этого умножения результат будет хранится в 4 словах (64 бита)
26-12-2010 19:58
Аа, понял… Проблема в том, что делить на 10 большое число просто так не получится. Наверно, придётся делить число по частям на степени 10. Надо подумать, как это можно реализовать.
26-12-2010 20:16
Если нужен пример кода, могу написать 🙂
26-12-2010 21:55
Я был бы безмерно благодарен:). Потому что. например при побайтном делении у меня нарушался вид числа (7500=1D4С, переводя побайтно получим 29 и 76). Вобщем я замучался и голова уже не варит…
27-12-2010 23:46
Написал пример:
http://asmworld.ru/isxodniki/preobrazovanie-64-bitnogo-chisla-v-stroku/
14-04-2011 15:29
Оптимизированный по скорости код умножения двух 32-битных чисел с получением
64-битного. Используются регистры общего назначения ax,bx,cx,dx. Из-за
уменьшения операций работы с памятью данный код работает в 7.5 раз быстрее
кода, приведенного автором задачи.
Алгоритм приведен в качестве анализа альтернативного метода реализации
указанной задачи.
Возможно можно еще как-то модифицировать, упростить, но исходя из изученных
мной уроков (остановился на 11-м) алгоритм мозг выдал такой 🙂
;z = x * y: x,y — 32bit unsigned, z — 64bit unsigned
;x — A:B; y — C:D; A,B,C,D — byte
use16
org 100h
mov ax,[x]
mov bx,ax
mov ax,[y]
mov cx,ax
mov al,bl
mul cl ;(1)ax=B*D
mov dx,ax ;dx=B*D
mov al,bh
mul cl ;(2)ax=A*D
add dh,al
adc ah,0
mov cl,ah ;(1+2)cl:dx
mov al,bl
mul ch ;(3)ax=B*C
add dh,al
adc ah,0
xor bl,bl
adc bl,0
add cl,ah
adc bl,0 ;(1+2+3)bl:cl:dx
mov al,bh
mul ch ;(4)ax=A*C
add al,cl
adc ah,0
add ah,bl ;(1+2+3+4)ax:dx
mov word[z+2],ax
mov ax,dx
mov word[z],ax
mov ax,4c00h
int 21h
x dw 0xFFFF
y dw 0xEEEE
z rd 1
14-04-2011 15:42
Извините, накосячил 🙂 только что сообразил — я не 32 битные числа перемножаю, а 16 битные :))) Но сам принцип мне понравился.
15-04-2011 00:17
Действительно 16-битные, зато таким же способом — по частям.
Можно умножить одной командой 😉
Мне интересно другое — как ты посчитал, что код будет быстрее в 7,5 раз?
15-04-2011 07:41
Конечно можно и одной командой, если не думаешь, что это 32-битные числа 😉
Скорость посчитал через такты команд из справочника.
Помню,что можно через асмовские команды тоже такты считать. По крайней мере на С++ у Фэнь Юаня в книге по WindowsAPI пример был — счетчик тактов
15-04-2011 09:52
Пример счетчика был написан не на С++, а на асме
15-04-2011 15:14
можна пример ?? всегда интерисовала производительность … интересно другое насколько он универсален? у каждой комманды есть определенное количество тактов например MUL:
r8 == 70-77, r16 == 118-133 — инфа из книги пирогова … было б неплохо посмотреть на исходник или программу
P.S: и не мусори сдесь для етого есть форум
15-04-2011 23:11
пример запостил в форум, раздел для начинающих, тока пока тема еще не добавилась…
постараюсь больше не мусорить 🙂
15-04-2011 14:27
Такой расчет врядли будет правильным.
Во-первых, современные процессоры могут выполнять несколько команд параллельно. Например, одна команда выполняет действие с регистрами, а другая в это время читает данные из памяти.
Во-вторых, ты не учитываешь кэш. Если данных немного, то они целиком помещаются в кэш и процессор работает с ними не обращаясь напрямую к памяти.
Наконец, процессоров сейчас очень много. Они по-разному выполняют обработку команд. Например, код оптимизированный под Intel Pentium 4, может медленно выполняться на процессорах AMD. Количество тактов для каждой команды тоже зависит от конкретного процессора.
Проще посчитать время выполнения кода специальной программой -профайлером. Теоретически предсказать трудно.
15-04-2011 14:29
а он 7.5 раз считал ))
15-04-2011 09:48
;вот мой вариант (уже правильный :)) перемножения 32-битных чисел
;отличие от авторского — использование только регистров общего назначения
;суть метода такая же, оптимизация в 1,5 раза быстрее за счет меньшего
обращения к памяти (но увеличение объема программы на 8% — 6 байт :))
;кстати, к сведению читателей — обращение к памяти происходит в _десятки_
раз быстрее через регистр аккумулятора ax, поэтому прежде чем
инициализировать значением какой-либо регистр
;сначала делаем mov ax,[memory]
;потом mov [reg],ax
use16
org 100h
mov ax,word[x]
mul word[y]
mov word[z],ax
mov bx,dx
mov ax,word[x]
mul word[y+2]
add bx,ax
mov cx,dx
mov ax,word[x+2]
mul word[y]
add ax,bx
mov word[z+2],ax
adc cx,dx
mov bx,0
adc bx,0
mov ax,word[x+2]
mul word[y+2]
add ax,cx
adc dx,bx
mov word[z+4],ax
mov ax,dx
mov word[z+6],ax
mov ax,4c00h
int 21h
x dd 0xFFFFFFFF
y dd 0xEEEEEEEE
z rq 1
;Уважаемые, вы не подумайте, что я выступаю в какой-либо конфронтации с
автором. Ничего подобного. Я так же как и вы учусь у него программированию
на асме. Просто это у меня натура такая, поковыряться везде 🙂
;А автору большой респект! Очень уважаю людей, которые делятся своим опытом
с другими.
15-04-2011 14:36
Вот тут возможно будет быстрее. Но чтобы быть уверенным, надо протестировать на нескольких разных процессорах. Оптимизация по скорости — довольно сложная тема.
Про обращение к памяти через ax не слышал. Где можно про это почитать подробнее?
Кстати, можно ещё немного оптимизировать твой код:
mov bx,0 => xor bx,bx
15-04-2011 22:45
xor bx,bx делать низзя, т.к. флаг переноса сбрасывается необходимый для дальнейшего сложения
про ах давно уже слышал, да и в справочнике команд по тактам можно посмотреть
mov reg,reg ;2 такта
mov reg,mem ;9+ea тактов
mov mem,reg ;8+ea тактов
mov mem,const ;10+ea тактов
mov reg,const ;4 такта
mov acc,mem ;10 тактов
mov mem,acc ;10 тактов
плюс еще доступ через сегментные регистры тоже 8(9)+еа тактов занимает
вообще самый долгий доступ идет именно к памяти (не считая ессно физических носителей информации), быстрее к кэшу 1 уровня
по тактам можно посмотреть, например, тут: http://develab.narod.ru/asm/index.htm
16-04-2011 16:29
Действительно, я не подумал про флаг переноса.
Такты, скорее всего, для оригинального Intel 8086. Для современных процессоров это будет неверно.
17-04-2011 11:16
Насчет операций с регистром-аккумулятором. Хотел поискать в манах Intel’а, но пока конкретного указания на то, что обработка команд при операциях с АХ происходит быстрее не нашел. Однако, для таких операций MOV AX,mem, MOV mem,AX предуспотрен отдельный оп-код. Как мне кажется там как-то проще происходит расчет доступа к области памяти при использовании АХ.
Короче, можно посмотреть тут: http://www.intel.com/Assets/PDF/manual/253667.pdf (стр.681). По этому же пути можно скачать мануалы по архитектуре процессоров Intel и описание для девелоперов (документы с 253665 по 253669)
20-03-2014 08:51
Здравствуйте, как реализовать умножение двух 4-х байтных чисел, не используя команду умножения (т.е. с помощью команд сложения и сдвига)? Не могу понять смысл.
12-11-2015 06:23
V_A DD ?
V_B DD ?
V_C DQ ?
;…
MOV EAX,DWORD[V_A]
MOV ECX,DWORD[V_B]
XOR EDX,EDX
MOV ESI,EDX
MOV EDI,EDX
JMP LB
L1: ADD ESI,EAX
ADC EDI,EDX
L0: SHL EAX,1
RCL EDX,1
LB: SHR ECX,1
JC L1
JNZ L0
MOV DWORD[V_C+0],ESI
MOV DWORD[V_C+4],EDI
27-05-2014 18:30
Доброго времени суток! для 16 бит*16 бит будет 32 бит. а если 32 бит * 64 бит, то результат какой разрядности будет?
есть пример умножения чисел, 32 x 64 бит ?
12-11-2015 07:38
«(2¹⁶-1)²=0FFFE0001₁₆» — 32 bit;
«(2³²-1)×(2⁶⁴-1)=0FFFFFFFEFFFFFFFF00000001₁₆» — 96 bit (12 bajt).
12-11-2015 05:14
; K.I.S.S. variant
;
mov ax, word[var_a+0]
mul word[var_b+0]
mov word[var_c+0] ,ax
mov word[var_c+2] ,dx
;
mov ax, word[var_a+2]
mul word[var_b+2]
mov word[var_c+4] ,ax
mov word[var_c+6] ,dx
;
mov ax, word[var_a+2]
mul word[var_b+0]
add word[var_c+2] ,ax
adc word[var_c+4] ,dx
adc word[var_c+6] ,0
;
mov ax, word[var_a+0]
mul word[var_b+2]
add word[var_c+2] ,ax
adc word[var_c+4] ,dx
adc word[var_c+6] ,0
12-11-2015 05:49
adc word[var_c+6] ,0
zamenitj na
rol word[var_c+6] ,1
12-11-2015 06:18
izvinitje, nje «rol» a «rcl»
10-12-2015 18:30
xrnd, поясни, пожалуйста, следующие строчки 22 и 37, а именно:
adc bx,bx ;/ с учётом переноса
align 4
И еще, строчки 10 и 11
sub cx,cx ;CX = 0
sub bx,bx ;BX = 0
отвечают за то, чтобы избавить эти регистры от всякого мусора? Или есть какой-то иной смысл? Спасибо.
18-12-2015 14:27
Всем привет! А кто знает, как можно реализовать умножения со сложением для 64-битных аргументов; и за одно в конце проверить флаг переполнения/потери точности?
22-03-2016 20:42
Здравствуйте. Можно ли Вас попросить помочь мне с умножением 32-битных чисел на 8-ми битном процессоре?
16-10-2016 00:48
use16; z = (x * y) / (x + y). 32 бит
org 100h
mov ax, word[x]
mul word[y]
mov di, ax
mov si, dx
sub cx, cx
sub bx, bx
mov ax, word[x]
mul word[y+2]
add si, ax
adc cx, dx
mov ax, word[x+2]
mul word[y]
add si, ax
adc cx, dx
adc bx, bx
mov ax, word[x+2]
mul word[y+2]
add cx, ax
adc bx, dx
mov ax, bx
mov dx, cx
mov cx, si
mov esi, [x]
add esi, [y]
div esi
mov word[z+6],ax
mov word[z+4],dx
mov dx, cx
mov ax, di
div esi
mov word[z+2],ax
mov word[z],dx
mov ax, 4C00h
int 21h
;________________________________
x dd $FFFFFFFF
y dd $FFFFFFFF
z dq ?
27-10-2016 01:38
Не смотрите на этот мой пример — он не правильный!!!
Я уже разобрался:) …ну почти