Мелкие задачки для крупных мозгов №15

Очередная мелкая задачка по избавлению от имликаций (по простому от ветвлений)

Задачка такая простейшая:

даны два числа a,b.

Найти процентое отклонение меньшего от большего.

например a=100,b=99

отклонение = 1

при a=99,b=100

отклонение = 1 также.

При расчёте сколько процентов меньшее число занимает от большего дробная часть процентов округляется в большую сторону.

Пример

a=200, b=1

a - большее значит 200 принимается за сто процентов.

1 от 200 это 1/2 процента - округляется до 1%

отклонение будет равно 99%

если в примере выше b=4 то это будет 2% если 3 то тоже 2.

Понятно, что если меньше число составляет 99 + x процентов

где 0<x<1 то округление произойдёт до 100% и отклонение будет равно 0.

Теперь вычислив это отклонение нужно вернуть его со знаком

минус если большим было число a, и со знаком + если большим было число b.

Область значений понятно Z(целые) от 0 до 99, область определений для a,b N(натуральные) меньше 2³¹.



Задача простая, но может оказаться не так просто сделать её безбранчевой (все Xcc инструкции исключаются).

Однако, это можно сделать даже несколькими способами.

Условие - выполнить вышеописанную задачу минимальным по размеру безбранчевым кодом.

 

Код (Text):

1. Если это не считать:
2.         mov ax,[a];
3.         mov bx,[b];
4. Тогда 9 команд по 2 байта:
5.         sub ax,bx;
6.         sbb cx,cx;
7.         not cx;
8.         and cx,ax;
9.         add bx,cx;
10.         push -100;
11.         pop dx;
12.         imul dx;
13.         idiv bx;

 

The Svin

А cmovcc можно?

 

Неа. Никаких сс

 

В таком случае код Black_mirror и есть оптимальный, только a и b должны быть 32-битными. Алгоритм max(a,b) может быть короче только если использовать cmovcc Так пишет Warren. А без функции max решение что-то не придумывается...

 

Ага, Black_mirror, как всегда очень качественно написал У меня было несколько других вариантов, но менее компактные. Смотрю код на ошибки - пока не разглядел.

Дык, "крупный мозг", обычно ленив - его разбудить надо

А Уоррена (которого сам же и популизировал всегда) бивали, и бивать будем, возможно и здесь придумается

 

The Svin

Да, я решил не позориться выкладывая свой вариант

Разве что idiv нужно обезопасить от нулевого делителя.

Код Black_mirror и так на пару инструкций оптимальнее уорреновского. Можно считать, что уже побили.

 

По математике вроде всё верно, модули разности коммутативны а 100-(x*100/y)=100(y-x)/y т.что всё сводится к определению максимума. Молодец. Можно сократить not IMHO если операнды в другом порядке сделать.

 

Там по мат. определению его быть не может. Изначально а, b > 0.

Далее, прибавится к нему (b) может число только если a > b а значит число a-b положительное, следует положительное + положительное быть нулём не может.

Так же любопытно что при таком подходе, когда операнды равны модуль их разности соответсвенно ноль и мы опять получаем правильный результат. Голова

 

The Svin

А утебя есть сохроненные, старые задачи? А то в форуме не все есть.

 

они наверно в оффлайн копиях есть.

 

The Svin

Делитель будет равен нулю только если хотя бы один из операндов (a и b) выходит из диапазона (0, 2³¹).

Код (Text):

1. a = 80000000h
2. b = 80000000h
3.  
4. a = 80000001h
5. b = 7FFFFFFFh
6.  
7. a = 0
8. b = 0
9.  
10. ...

Мат. определение, конечно, рулит, но в программировании принято проверять правильность аргументов. К алгоритму это никакого отношения не имеет. Просто, если кто-то захочет поместить эту функцию в библиотеку или использовать в любой программе, должен будет предусмотреть проверку аргументов. Багов в самом алгоритме нет, как я уже написал раньше.

Код (Text):

1. r = (a-b)*100/max(a,b);
2. max(a,b) = ((a == b) & (a - b)) + b;
3. == : { true (0FFFFFFFFh), false (0h) };

 

Дык в определении задачи написано что 0< a,b <2³¹. Это значит, что аргументы идут уже подготовленные. Где то вне этого. Или подразумевается, что в принципе в задаче не могут оказаться такие аргумента от источника их значений. Пусть допустим рассматривается длительности последовательного сигнала в каких то единицах. 0 длина означала бы что сигнала (любого состояния) не было, а такое быть не могло так как сигналы анализируются из дампа к примеру длины < 2₃₁. Т.е. если дамп есть то сигнал там есть и если дамп < 2³¹ то и самый длинный возможный сигнал < 2³¹.

Просто есть такое понятие как условие задачи и определение величин. И это не просто абстрактое понятие, оно как правило диктуется от конкретной задачи, например процедуре посылается текст если текст есть, т.е. не нулевой длины.

Если текста нет - процедура вообще не вызывается.

 

The Svin

Аргументы понятны ещё из предыдущего поста. В некоторых случаях данные просто не могут выходить за пределы диапазона, в других достаточно жирным шрифтом выделить в описании функции, что может произойти исключение, если данные не попадают в заданный интервал и разработчик сам обо всём позаботится. Всё же, IMHO, имеет смысл лишний раз это подчеркнуть.

 

Quantum

Понятно.

Пока надумал одну простую оптим. на байт. что сократить можно убрав not cx а перед sbb cx,cx поставить однобайтную cmc (11110101b)

Но интересней на команду сократить, мысль крутится никак не поймаю...

 

Придумал как можно эквиваленто заменить

5 инструкций

Код (Text):

1.  
2.         sub ax,bx;
3.         sbb cx,cx;
4.         not cx;
5.         and cx,ax;
6.         add bx,cx;
7.  

На другие 5 (никакого выигрыша - просто другой вариант на

случай если хочется для чего в cx именть обратное число)

Edit-добавил коментарии

Код (Text):

1.  
2.     sub ax,bx ;a-b
3.     add bx,ax ;предпологаем что а было больше и сразу складываем.
4.     sbb cx,cx ;маска для вычетателя если предположили неправильно
5.     and cx,ax ;cx=0 если правильно пред. cx=ax - неправильно
6.     sub bx,cx ;вычитает из bx 0 если правильно прибавили, ax - если не надо было прибавлять.
7.  

В cx на выходе где у Чёрного Зеркала 0..0 будет 1..1 и наоборот где 1..1 будет 0..0. Как следствие в конце где у Зеркала в cx был 0 окажется -|a-b|,а где a-b будет 0.

 

Код (Text):

1. not cx
2. and cx,ax

можно заменить на:

Код (Text):

1. sub bx,cx
2. or cx,ax

Если бы or не затирал C, было бы на 1 инструкцию меньше

 

Насчет экономии байтов. Т.к. числа положительные, то вместо sbb можно использовать cdq - на байт короче и не такая тормозная на P4 (хотя по сравнению с idiv прочие тормоза отдыхают

Ну и push+pop у Black_mirror'а ради экономии одного байта по сравнению с mov edx,-100 выглядит извращением При желании можно в те же 4 байта уложиться: xor edx,edx + mov dl,100; а инверсию знака сделать путем замены sbb ecx,ecx + not ecx на neg eax + cdq



Число инструкций здесь не уменьшишь - разве что казуистикой с операндами из памяти:

Код (Text):

1.   mov eax,a
2.   sub eax,b
3.   sbb ecx,ecx ;при cdq в данном случае потребуется доп. mov ecx,edx
4.   and ecx,eax
5.   sub ecx,a ;=-a или -b
6.   mov edx,100 ;для экономии 1 байта можно xor edx,edx + mov dl,100
7.   imul edx
8.   idiv ecx

Если a и b адресуются относительно ebp со смещением < 128, то размер в байтах будет <= чем в исходном варианте Black_mirror

 

Т.е. что-то вроде?:

Код (Text):

1.  
2. ;eax=[a],ebx=[b]
3.         sub eax,ebx;
4.         cdq
5.         not edx;
6.         and edx,eax;
7.         push -100;
8.  
9.         add ebx,edx;
10.     pop edx;
11.         imul edx;
12.         idiv ebx;
13.  

 

Для mov edx,-100 vs push -100 + pop edx это два байта.

Это очень легко считается.

Если префиксов нет то mov reg,imm это один байт + размер операнда. Т.е. для mov reg8,imm 1+1(8bit) для mov reg16,imm (если без префиксов в родном коде) 1+2(16 бит), mov reg32,imm 1+4. Один байт будет разница если mov reg24,imm.

Это что про машины типа Днепра

Для случая если Black_mirror писал для 16ного режима - выигрыша нет. Для 32х битного по 16и битными регистрами - тоже. А вот если перевести в 32х битные то выигрыш будет и именно два байта.

Мне это извращением не кажется в случае 32х битного кода, так как в данном алгоритме туча зависимых инструкций, а поскольку push imm. pop reg никаких флагов не меняет и от результатов других операций не зависит, то можно врезать две эти операции непоследовательно чтобы "размежевать" другие инструкции, в этом случае

1. Push pop - сыграют роль nop

2. При этом лишних тактов не сожрут а работу загрузки выполнят, причём возможно даже ускорят избавляя от хотя бы одного stall

3. Размер будет меньше, в кеш загрузится с большей вероятностью.