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

Ого, не только я булевыми функциями занимаюсь. Какая у тебя глобальная задача?

 

Camarada
Когда-то давно делал преобразования Уолша.
Суть не помню, но код нашел.
Правильность и эффективность кода не гаранитрую.

Код (Text):

1. //---------Быстрое преобразование Уолша, упорядоченное по Уолшу--------------
2.  
3. void FWTW( float s[], int N )
4. {
5.     float *_s = new float [N];
6.     int VZ;
7.     for( int k = N/2; k >= 1 ; k /= 2 )
8.     {
9.         for( int j = 0; j < N; j += 2*k )
10.         {
11.             VZ = - 1;
12.             for( int i = 0; i < k; i ++ )
13.             {
14.                 VZ = - VZ;
15.                 _s[i+j]   = s[2*i+j] + s[2*i+j+1];
16.                 _s[i+j+k] = VZ * ( s[2*i+j] - s[2*i+j+1] );
17.             }
18.         }
19.         for( int i = 0; i < N; i ++ )
20.             s[i] = _s[i];
21.     }
22.     delete[] _s;
23. }
24. //---------Быстрое преобразование Уолша, упорядоченное по Пэли---------------
25.  
26. void FWTP( float s[], int N )
27. {
28.     float *_s = new float [N];
29.     int l;
30.     for ( int i = 1;  i < N;  i *= 2 )
31.     {
32.         l = 0;
33.         for ( int j = 0;  j < N;  j += 2*i )
34.             for ( int k = 0;  k < i;  k ++ )
35.             {
36.                 _s[l]   = s[k+j] + s[k+j+i];
37.                 _s[l+1] = s[k+j] - s[k+j+i];
38.                 l += 2;
39.             }
40.             for ( int j = 0;  j < N;  j ++ )
41.                 s[j] = _s[j];
42.     }
43.     delete[] _s;
44. }
45. //---------Быстрое преобразование Уолша, упорядоченное по Адамару------------
46.  
47. void FWTH( float s[], int N )
48. {
49.         float _s;
50.         for ( int i = 1;  i < N;  i *= 2 )
51.             for ( int j = 0;  j < N;  j += 2*i )
52.                 for ( int k = 0;  k < i;  k ++ )
53.                 {
54.                     _s       = s[k+j];
55.                     s[k+j]   = _s + s[k+j+i];
56.                     s[k+j+i] = _s - s[k+j+i];
57.                 }
58. }

 

_G3, я тоже делал. Сюда написал в поисках эффективности.

 

Camarada

Так покажи свой код. Или хотя бы проверь работает ли мой.
Есть подозрение, что ты делал просто преобразование Уолша, а не "Быстрое преобразование Уолша".

 

Я делал оба. Сейчас меня волнует вопрос быстрой генерации значений функций Уолша и хранение этих данных, а так же оптимизация умножения.
Код выкладывать не буду, он действительно плох, я тогда был начинающим и не имел времени для оптимизации. Эти функции вычислил, сохранил в файл (для больших N и забыл). Если очень нужно могу привести код, но пользы от этого будет мало.

 

К сожалению, b double, но спасибо все равно.

 

Самое время об этом между делом упомянуть.

 

l_inc, а такой код не поможет?

Код (Text):

1. _asm
2. mov eax, [w]
3. add eax, 1 (Есть инструкция вроде inc eax)
4. shl eax, 30
5. mov ecx, [b] (Старшее слово double значения)
6. xor eax, ecx ;eax содержит старшее слово double b*w
7. Затем операции по соединению младшей части b и eax ; Как реализовать?
8. Затем сложение [a] и вновь полученного числа. Как реализовать?

Да и все еще жду советов по поводу размещения в памяти таблиц функций Уолша либо быстрого их вычисления . В принципе мне удалось неплохо оптимизировать функции Радемахера, и код Грея заменяется вообще двумя операциями. Но все равно вычисление функций Уолша довольно много операций занимает, поэтому в цикле к примеру 1024x1024 вычисление самой функции займет заметное время по сравнению с вычислением преобразования. Плиз, дайте совет.

 

ОК, согласен

а w типа int? А то можно вот так сделать:

Код (Text):

1. double bs[3] = {-b,0,b};
2. ...
3. s=a+bs[w[i]+1];

типа быстро должно быть

 

Camarada

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

Зачем формировать таблицу 1024х1024 и думать чем заменить умножение на +-1, если можно без всяких таблиц и ухищрений посчитать быстрое преобразование по Адамару (см.пост _G3 #22), а затем (если нужно) переупорядочить полученный массив по Уолшу. Правда тут кроме кода Грэя (вроде как) нужна инверсия порядка бит индекса, но зато и массивчик всего лишь 1024 элемента

 

На самом деле самые быстрые формулы получаются для БПУ по Пэли. Спасибо за совет, в голову как-то не приходило.

Люди прокомментируйте. Правда ли это будет быстро? Вроде интересный вариант, но не будет ли накладно лишнее обращение к памяти?

 

Но если уже есть массив значений b, то можно пройтись по нему и поксорить старший бит...

Код (Text):

1. cycle:
2. mov eax, [w]
3. and eax, 0x80000000
4. ; b указывает на старшее слово
5. xor [b], eax
6. add w, 4
7. add b, 8
8. dec ecx
9. jnz cycle

Но, судя по всему, массива значений b нет?

 

есть привожу код "медленного" преобразования.

Код (Text):

1. for (int i=0; i<N; i++)
2. {
3.     double sum=0;
4.     for (int j=0; j<N; j++)
5.         sum+=incom[j]*wa[i][j];
6.     outcom[i]=sum;
7. }
8. /*wa[i][j] - (char**)2мерный массив NxN функций Уолша.
9. incom  -  (double*) как раз наш преобразуемый массив.
10. outcom - (double*) посчтитанное преобразование*/

 

Camarada

По крайней мере быстрее, чем перексоривать b для каждой строки
Но тогда лучше w[i,j] формировать не из {-1,1}, а из {-1,0}, тогда можно использовать либо массив bs = {-b,b} удвоенной длины, либо два разных массива - исходный b и интвертированный bs. В сл.двух массивов быстрее формируется bs, но добавляется элементарная операция &:
sum+=(double*)(int(b)+delta & w[j])[j];
где delta = int(bs)-int(b); w[i,j] E {-1,0}

PS: кстати из-за приличной латентности fsub суммирование на FPU можно ускорить до 3х с лишним раз, если в цикле копить не одну сумму, а 4 одновременно для j,j+1,..,j+3

 

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

Разве такие вещи не должен делать компилятор???

В общим стоит попробовать все здесь предложенные варианты и выложить результаты.
Потом будем оптимизировать дальше))
Другой вопрос в том, что разница будет видна при больших N.
А для N = 4096 уже 16 Mb памяти требуется, возможно прийдется и увеличивать N. Ну в принципе могу максимум сделать для 8192. Конечно быстрый вариант алгоритма в этом плане супер-находка.

 

В процессе вычислений никаких доп.операций с памятью нет, т.к. на каждой итерации читаются только два значения: w[i,j] и либо b[j], либо bs[j] в завис-ти от значения w. Есть только затраты на предварительное создание массива интвертированных значений bs.

Может, но не обязан Посмотри в какой асм-листинг превращается твой код и скажешь "обязан" или нет

В том-то и дело, и ни в какой кэш эта "куча мусора" не поместится. Поэтому затея с формированием таблицы заведомо обречена на тормоза и особо оптимизировать замену умножения здесь тоже не имеет смысла, т.к. основное время будет тратиться на подгрузку элементов таблицы W из ОЗУ. Посему бросай ты эту дурную затею и реализуй быстрые адгоритмы по Пэли или Адамару без всяких таблиц

 

Такой вопрос еще в эту же тему, мне нужно в С++, используя директиву _asm руками сохраниять регистры, либо компилятор сгенерирует этот код. Если не сгенерирует, какие действия я должен произвести?

 

Camarada

Ну проще всего выбрать стандартный способ - сохранить в стеке : push
А в конце asm-блока - pop в обратном порядке.

 

valterg
Вопрос был о том, нужно ли, а не как.
Camarada
AFAIK компилятор сам сохранит. А вообще разве трудно проверить?

 

AFAIK ниче он не сохранит