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

Mikl__
У меня такой вариант группировки крутился в голове, но я так и не понял, как он будет работать при (a-b) < 0 и\или (d-c) < 0

 

leo
Вариант uv=(a * c) << 32 + ((a - b) * (d - c) + a * c + b * d) << 16 + b * d
у меня получился вот такой

Код (Text):

1.         mov ax,c1   ;bp:bx:cx:ax
2.         mul a           ;a*c=di:si=bp:si
3.     mov si,ax
4.     mov di,dx
5.     mov bp,di
6.         mov ax,b        ;b*d=dx:ax=cx:bx
7.     mul d
8.     mov word ptr [Z4],ax            ;bp:bx:cx:ax
9.     mov bx,ax;                             dx:ax=b*d
10.     mov cx,dx;                          dx:ax   =b*d
11.     add bx,dx;                          di:si   =a*c
12.     adc cx,di;                       di:si      =a*c
13.     adc bp,0;                           dx:ax   =(a-b)*(d-c)
14.     add bx,si
15.     adc cx,si
16.     adc bp,0
17.     mov ax,a
18.     sub ax,b ;ax=a-b
19.     sbb si,si;if a>=b then si=0 else si=-1
20.     xor ax,si;if si=0 then ax=ax else ax=not ax
21.     sub ax,si;if si=0 then ax=ax else ax=-ax
22.     mov dx,d
23.     sub dx,c1;dx=d-c
24.     sbb di,di;if d>=c then di=0 else di=-1
25.     xor dx,di;if di=0 then dx=dx else dx=not dx
26.     sub dx,di;if di=0 then dx=dx else dx=-dx
27.     mul dx;перемножаем модули |a-b|*|d-c|
28.     xor si,di;if si<>di then (a-b)*(d-c) < 0
29.     xor ax,si;если si=-1 вычитаем иначе складываем
30.     xor dx,si
31.     sub ax,si
32.     add bx,ax
33.     adc cx,dx
34.     adc bp,si
35.     mov word ptr [Z4+2],bx
36.         mov word ptr [Z4+4],cx
37.     mov word ptr [Z4+6],bp

А вот с пересчетом тиков, помоему у меня получается ерунда, посмотри пожалуйста в чем ошибка... В аттаче сорц и ехе. В сорце рассматриваются еще два варианта из 4-х умножений

 

Mikl__

Ес-но, параноидальная экономия байтов до добра не доведет )) Ты зачем все xor eax,eax перед cpuid закомментировал ?! При недопустимых значениях eax задержка cpuid получается сильно завышенной и зависит от eax. В результате у тебя задержка при измерении оверхеда получается больше, чем в тестах и результат простого mul получается отрицательным.
Плюс к этому при наличи записи в память использование cpuid перед вторым rdtsc приводит к завышенным результатам. Выход - либо заменить вторую cpuid на cld (на пеньках работает нормально, на атлонах не проверял), либо добавить инструкцию записи в память в расчет оверхеда

 

Google rulez!
u=b+a<<16 v=d+c<<16
uv=ac<<32 + (ad + bc)<<16 + bd
Алгоритм Карацубы
uv=ac << 32 + ((a - b)(d - c) + ac + bd) << 16 + bd
Алгоритм Тоома-Кука
1) Найти bd
2) Найти (a+b)(c+d)
3) Найти (b-a)(d-c)
ac=((a+b)(c+d)+(b-a)(d-c))>>1 - bd
bc+ad=((a+b)(c+d)-(b-a)(d-c))>>1

 

алгоритм Шёнхаге-Штрассена
Сплошная математика, может кто-нибудь напишет понятным языком для случая
u=b+a<<16 v=d+c<<16 ?