Хотелось бы увидеть реализацию простого алгоритма

Два 32 битных числа перемножить в 16 ти битовых регистрах
Есть классический алгоритм в четыре умножения
А есть другой классический алгоритм в три умножения
(a * c) << 32 + ((a + b) * (c + d) - a * c - b * d) << 16 + b * d
При операциях a + b и c + d может возникать переполнение
Если переполнение только a + b или c + d мы можем добавить сдвиг и сложение
А если переполнение и a + b и c + d то мы будем вынуждены перейти на классический алгоритм в четыре умножения
Хотелось бы увидеть это в коде. Если можно...
upd: Для ассемблера x86

Выделю на всякий случай все три умножения
1)(a * c) << 32 + ((a + b) * (c + d) - a * c - b * d) << 16 + b * d
2)(a * c) << 32 + ((a + b) * (c + d) - a * c - b * d) << 16 + b * d
3)(a * c) << 32 + ((a + b) * (c + d) - a * c - b * d) << 16 + b * d

 

X*Y=Z,
где X=a*2^16 + b и Y= c1*2^16 + d
X*Y= (a*2^16 + b)*(c1*2^16 + d) = a*c1*2^32 + (a*d + b*c1) *2^16 + b*d

Код (Text):

1.        mov ax,b
2.        mul d
3.        mov word ptr Z,ax
4.        mov word ptr [Z+2],dx
5.        mov ax,b
6.        mul c1
7.        add word ptr [Z+2],ax
8.        adc word ptr [Z+4],dx
9.        adc word ptr [Z+6],0;если был перенос увеличим [Z+6]
10.        mov ax,a
11.        mul d
12.        add word ptr [Z+2],ax
13.        adc word ptr [Z+4],dx
14.        adc word ptr [Z+6],0;если был перенос увеличим [Z+6]
15.        mov ax,a
16.        mul c1
17.        add word ptr [Z+4],ax
18.        adc word ptr [Z+6],dx
19.        ret      ;выход из программы
20. b dw    0FFFFh      ;сомножители
21. a dw    0FFFFh      ;X и Y
22. d dw    0FFFFh
23. c1 dw   0FFFFh
24. Z dd 2 dup (0)                 ;результат

PS. При замене word->dword, ax->eax, dx->edx и умножении смещения при Z на 2 т.е. [Z+6]->[Z+12] фрагмент легко переделывается для умножения 64-разрядных чисел

 

Не совсем понял где у вас реализация умножения двух чисел
X=a*2^16 + b и Y= c1*2^16 + d
в три умножения. Судя по формуле и коду у вас классический алгоритм в 4 умножения

 

lamer19

[censored]
Дарагой, а сам-то почему не пишешь? Или решил у других зачеты принимать, так я не студент

 

Единственное что могу сказать - "Я не решил принимать зачеты". Данный раздел форума как я понял предназначен для "Обсуждение алгоритмов и техник оптимизации кода.". Почему не пишу сам очевидно даже по нику lamer19, мозгов не хватает. Я когда-то занимался ассемблером для души, но последние несколько лет я тупой одинэсник .
А тут что-то потянул на старое. Сначала я не мог вспомнить данный алгоритм, но
Тут напомнили. А задался я этой темой исключительно потому что в свое время не реализовал его сам. И есть у меня нехорошее подозрение, что под такие алгоритмы ассемблер x86 не заточен. Система адресации несколько не та (байты местами меняются при сохранении в память и нельзя всю память представить как одно большое число). То есть некоторое подозрение что ассемблер x86 спроектирован не совсем правильно. Или возможно проблема в моих мозгах, а не в ассемблере. Во всяком случае пока нигде и никто не привел мне исходника данного алгоритма. Если действительно проблема в проектирование процессора, то данный алгоритм можно будет записать в хорошие, показательный тесты для определения качества реализации процессора.

 

lamer19
Объясни, чего ты хочешь добится? Выигрышь по скорости? Выигрышь по компактности?
Мой вариант: a*c1*2^32 + (a*d + b*c1) *2^16 + b*d -- 4 умножения, 3 сложения и я обошелся без сдвигов
Твой вариант: (a * c) << 32 + ((a + b) * (c + d) - (a * c) - (b * d)) << 16 + b * d
3 умножения, 4 сложения, 2 вычитания, без сдвигов тоже можно обойтись, команды MOV я не учитывал, но думаю в твоем варианте их больше
по скорости IMHO оба варианта одинаковы, можно замерить командой RDTSC, все будет зависеть от конкретного процессора, но с этим лучше к leo
Если по объему, то мой вариант можно утрамбовать в 2 раза...

 

1)Выигрыш по скорости? Команда mul дорогая команда насколько я помню. mov, add, sub, adc, sbb более дешевые
2)Реализацию алгоритма

 

Цитирую Зубкова (Assembler для DOS, Windows и UNIX) (Приложение 2)
Команда 286 386 486 P5 P6
ADD m,r 7 7 3 3UV 4m
ADC m,im 7 7 3 3PU 4m
SUB m,r 7 7 3 3UV 4m
SBB m,r 7 7 3 3PU 4m
MUL m16 24 12..25 13..26 11NP 4m
UV - может выполняться одновременно в любом конвейере
PU - может выполняться одновременно в U-конвейере
NP - не может выполняться одновременно
Так что для P6 (Pentium Pro и выше) для сложения и умножения скорость одинакова

 

То есть они там в алу типа множитель новый добавили, наверняка по типу лиспа . Это прикольно.
У меня такое подозрение что алгоритм который я описал в данной ветке было бы легко реализовывать если бы на интеле можно было бы представить всю доступную память как одно большое машинное слово, кажется такое было возможно на амиге с ее мотороловским ассемблером. Кстати на мотороловском стек системный и стек пользовательский изначально были два разных стека с разной адресацией. У меня к сожаление для реализации алгоритма не хватает воображения. Может быть попробовать рисовать для наглядности что куда и откуда будет переносится?

 

lamer19

Нормальная адресация, никакие байты местами не меняются, два последовательных байта можно представить как один ворд, а два ворда как один дворд и т.д. Вся разница в последовательности записи байтов - в х86 порядок нормальный, младшие байты по младшим адресам, старшие по старшим и в результате сложения\умножения переносы бегут "слева направо". А вот для представления на бумаге у нас прижились арабские цифры и арабский порядок записи - старшие цифры слева, младшие справа и при умножении\сложении столбиком мы как настоящие вахабиты производим действия справа налево )
Поэтому процессор спректирован правильно, а вот ты возможно записываешь числа по арабской привычке не правильно: если a - старший word, b младший, то в программе (в структуре данных) они должны объявляться - сначала b, затем a, тогда они вместе будут образовывать единый dword

Если ты хочешь реализовать этот алгоритм только ради спортивного интереса, то лучше плюнь на это дело, т.к. для современных компов он не даст никакого выигрыша и лишь проиграет как по размеру кода, так и по скорости. Mikl__ c Зубковым не совсем правы в отношении цифирек для P6, т.к. помимо латентности операций большую роль играет их зависимость\независимость и конвееризация операций mov и mul. В P6 mul выполняется 4 такта, но за счет конвееризации (pipelining) независимые mul могут идти друг за другом через 1 такт и в итоге 4 независимых умножения могут выполниться не за 4*4=16 тактов, а лишь за 3+4=7 тактов, а разница между 4 и 3 умножениями будет не 4 такта, а лишь 1 такт, который с лихвой скушается дополнительными зависимыми сложениями\вычитаниями (а сложения тут кстати не простые, а двойные add+adc). Одним словом для P6 и выше однозначно игра не стоит свеч.
А в отношении древних компов и инфы по латентностям маловато, и возиться с проблемой переноса при (а±b) и (с±d) не хочется, т.к. красивого решения с ходу не видно и выигрыш врядли какой будет, а проверить все равно не на чем

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

 

Именно это меня и гложет, то что я сам в своё время обломал зубы, ну не вытанцовывалось у меня что то в мозгах

 

lamer19
Если нет желания писать программу самому, может быть, имело смысл обратится в раздел BEGINNERS->Студентам с вопросами о лабораторных работах сюда

 

lamer19

Да чего там вытанцовываться, нужно просто нудно расписать (a+b)*(c+d) с учетом переносов, а затем также нудно все это за(ш)кодить
(a+b) * (c+d) = (x*2^16+(a+b).Lo) * (y*2^16+(c+d).Lo) =
x*y*2^32 + (x*(c+d).Lo+y*(a+b).Lo)*2^16 + (a+b).Lo*(c+d).Lo,
где .Lo - младшие 16 бит результата, x,y = {0,1} - биты переноса. Умножение на {0,1} ес-но заменяем логическими побитовыми операциями
x*y = -((-x) & (-y))
x*(c+d).Lo = (-x) & (c+d).Lo
y*(a+b).Lo = (-y) & (a+b).Lo
В итоге все "вытанцовывается" примерно в такую фигню:

Код (Text):

1. mov ax,[b]
2. mov si,ax
3. mul [d]     ;dx:ax = b*d
4. add si,[a]  ;si = (a+b).Lo
5. sbb cx,cx   ;признак переноса = -x = {0,-1}
6. mov [z0],ax ;z0 = (b*d).Lo
7. mov [z1],dx ;z1 = (b*d).Hi
8.  
9. mov ax,[c]
10. mov di,ax
11. mul [a]     ;dx:ax = a*c
12. add di,[d]  ;di = (c+d).Lo
13. sbb bx,bx   ;признак переноса = -y = {0,-1}
14. mov bp,cx
15. and cx,di   ;x*(c+d).Lo
16. and bp,bx   ;-x*y = {0,-1}
17. and bx,si   ;y*(a+b).Lo
18.  
19. xchg si,ax  ;ax = (a+b).Lo, si = (a*c).Lo
20. xchg di,dx  ;dx = (c+d).Lo, di = (a*c).Hi
21. mul dx      ;dx:ax = z2:z1' = (a+b).Lo*(c+d).Lo
22.  
23. sub ax,si   ;z1'-=(a*c).Lo
24. sbb dx,di   ;z2 -=(a*c).Hi
25. sbb di,bp   ;z3 -=(-x*y)
26.  
27. sub ax,[z0] ;z1'-=(b*d).Lo
28. sbb dx,[z1] ;z2 -=(b*d).Hi
29. sbb di,0    ;z3
30.  
31. add dx,cx   ;z2 +=x*(c+d).Lo
32. adc di,0    ;z3
33. add dx,bx   ;z2 +=y*(a+b).Lo
34. adc di,0    ;z3
35.  
36. add ax,[z1] ;z1 = z1' + (b*d).Hi
37. adc dx,si   ;z2 += (a*c).Lo
38. adc di,0    ;z3
39.  
40. mov [z1],ax
41. mov [z2],dx
42. mov [z3],di

 

leo
Хотел оценить разные способы умножения, но вот каждый раз разные числа, и по-моему я что-то сделал не так Подскажи, пожалуйста, где ошибка... Сорц и ехе в аттаче

 

Mikl__
1) Записывать данные в секцию кода нельзя. Это может прокатить только в P6, а в P4 и атлонах приводит к большим тормозам (сброс T-кэша в P4 и разметки длин преддекодера в L1-code в атлонах)
2) Первый проход вообще нельзя использовать для измерений, т.к. ни кода ни данных еще нет в кэше и они подгружаются из ОЗУ и соответственно основное время съедает именно загрузка (которая сама по себе может плавать, а на двухядерниках и HT особенно), а в P4 и атлонах еще и преддекодирование существенно сказывается. Поэтому для получения стабильных результатов нужно загнать все измерения в цикл как минимум из 3-4 проходов и брать последний результат. (Но на P4 с HT цифры все равно будут сильно "гулять", поэтому единственный выход - только отключать HT)
3) "Голые" rdtsc сами по себе могут давать существенный разброс, т.к. это не серийные инструкции и они могут выполняться вне очереди. Поэтому для точных измерений малых задержек, rdtsc нужно "обертывать" в cpuid, которые сами по себе вносят большую задержку и ее нужно учитывать отдельно (расчет оверхеда)

Примеры "правильных" измерений см.у А.Фога или поищи тут на форуме wintest.exe

 

leo
10x a lot!

 

Большое вам спасибо

 

lamer19
Подсчеты тиков на Celeron-2 и Pentium-4 показали, что разницы по времени между алгоритмом с 3 умножениями и алгоритмом с 4 умножениями нет!

 

Но бывает еще старое железо на котором вероятнее всего удасться получить выигрыш.
Лео даже сделал лучше чем я себе представлял
Сам алгоритм мне попался в сборнике лекций лауреатов премии Тьюринга.

 

lamer19
Дональд Э. Кнут "Искусство программирования" т.2 "Получисленные алгоритмы" глава "Насколько быстро можно выполнять умножение"
u=b+a*2^n v=d+c*2^n
uv=(2^2n + 2^n)ac+2^n (a-b)(d-b)+(2^n +1)bd
при n=16 uv=(a * c) << 32 + ((a - b) * (d - c) + a * c + b * d) << 16 + b * d