Отмена умножения на единицу во время выполнения

А если конкретно стоит задача выполнения преобразования Уолша.
Его плюс в том, что значениями функции Уолша являются либо +1, либо -1.
Выполняется очень много операций a+b*w, где w - значение функции Уолша.
Как сделать так, чтобы это выражение выполнялось как a+b или a-b в зависимости от значения w. Это нужно реализовать, так как основной выигрыш в производительности достигается именно заменой умножения более простыми операциями.
Спасибо заранее, что-то у меня разумных мыслей нет на сей счет.

 

if (w == 1)
s = a + b;
else
s = a - b;

чем такой вариант не подходит?

 

Я думал об этом, но решил, что есть получше что-нибудь. Все таки лишние je.

 

если b и (*w) типа int, то можно так:
_asm
{
mov eax,[wi]
cdq
mov ecx,
xor ecx,edx
sub ecx,edx
}

 

Не силен в ассемблере, но можно еще вот так:

__asm {
mov ebx, [wi]
and bl, bh
xor , ebx
shr ebx, 31
add ebx,

add [a], ebx

}

 

Спасибо всем, кто предоставил asm-код, но это точно производительнее чем то, что привожу в цитате???

 

в данных вариантах асм-кода специально убраны ветвления. Плюс в моём нет таких операций как сдвиг, который есть у Novi4ek. Скорее всего, будет производительнее. Проще попробовать все варианты и выбрать наиболее производительный.

 

Camarada

нет)) еще нуно регистры используемые сохранять
кроме того код на асме зависит от типа данных s и b
на сях можно так: s=a+(b^(w&(1<<(8*sizeof(w)-1)))) при условии, что s и b имеют типы одного размера

 

10110111
test eax,eax зачем?
dec ecx,edx - недокумментированная инструкция от интел?
Логический сдвиг - один такт. Зато Ваш cdq - два такта.
Camarada

Сильно зависимо от частоты рассчета a+b*w и от распределения w. Если P(w=1):P(w=-1)=10:1, то вероятность сброса ковейера во время условного перехода мала и лучше использовать je.
Если слегка подправить код Novi4ek (лишние операции с памятью и ее порча все таки не очень хорошо сказываются на производительности кода, а ebx портить в контексте windows не кошерно), то можете еще вот этот код потестировать (результат в eax):

Код (Text):

1. mov edx,[wi]
2. mov ecx,[b]
3. mov eax,[a]
4. and dl,dh
5. xor ecx,edx
6. shr edx,31
7. add eax,ecx
8. add eax,edx

 

непредсказанные ветвления сбрасывают конвеер. это основной их минус. Советую протестировать каждый из вариантов и посмотреть результат.

 

KeSqueer
>>s=a+(b^(w&(1<<(8*sizeof(w)-1))))
неправильно. так как отрицательные числа хранятся в дополнительном коде
правильно будет так: s=a+(b^w>>1)-(w>>1),
при этом w должен быть знаковым (это вроде по условию задачи подразумевается), чтобы при сдвиге знаковый разряд не обнулялся

 

Вероятность появления единицы ровно 0.5.

Когда займусь реализацией попробую протестить все варианты.
А сейчас такой вопрос. Как лучше генерить функции. Значение функции вычисляется не тривиально, соответственно в огромном цикле будет очень накладно ее вычислять. Поэтому нужно вычислять эту функцию заранее. Как предложите это делать. Хранить в файле матрицы Уолша для нескольких размерностей и загружать нужную в память перед выполнением преобразованием, что также потребует времени в случае размерности преобразования например 2048 (Матрица будет 2048x2048). Или как?

 

А если быть точным, то значение функции Уолша (wal) формируются из значений функции Радемахера (rad). Для этих функций есть понятие размерность (как раз размер матрицы).
Так вот формулы исходя из размерности N.
rad(m,t) = sign(sin(2^m*Pi*t)). ^ - степень. 0 <= t <= 1
sign(x) = {x>0 => sign(x) = 1. x<0 => sign(x) = -1. sign(0) = 0}
wal(m,t) формируется из произведений функций Радемахера соответствующих разрядам числа m в коде Грея.
Код Грея.
Возьмем представление числа в 2чной форме, содержащее log2(N) разрядов. То есть в случае N=8 три разряда. Представим его как a[0]..a[n-1]. Число в коде Грея будет следующим. b[0]..b[n-1]. b = a ^ a[i+1]. b[n-1] = a[n-1]. Здесь ^ - оператор С.

Таким образом число 3 = 011 в коде Грея будет 010. Таким образом wal(3,t) = rad(1,t)
А если взять число 5 - 101, то в коде Грея 111 значит
wal(5,t) = rad(1,t)*rad(2,t)*rad(3,t).

Вот такие пироги. Все это очень долго выполняется поэтому хочу максимально оптимизировать. Я понимаю, что это тяжеловато читать, но мне показалось люди заинтересовались, поэтому я выложил.

 

У меня подозрение, что умножение дешевле будет))))

 

Camarada
если компилятор представит это как:
register signed x = w >> 1;
s=a+(b^x)-x;
то получится вместо одного умножения - один сдвиг, один xor и одно вычитание.
стоит побробовать

 

l_inc

Да, ступил, показалось, что cdq действует по флагу.

Имелась ввиду sub.

На P4 афаик сдвиги - одни из самых медленных операций.

 

10110111

Сильно сказано, но, конечно, подольше выполняются. Тем не менее не известно, под что оптимизируем.
Хотя сам сейчас думаю, нафига там shr, если есть sub.

 

Что-то я не просмотрю, где здесь s=a+b*w. Допустим wi = 1, тогда в 4ой строке есх ксоритсяс нулем, а дальше из есх вычитается ноль ну и что?..

 

Novi4ek
Ну там не хватает только add ecx,[a]. И в ecx будет результат.

 

Ага согласен тогда.