Оптимизация деления.

Привет.
Что имеем.
Имеем массив:

Код (Text):

1. int h[4];

Переменную с максимальным значением из массива:

Код (Text):

1. int h_max;

Нужно найти целочисленное соотношение между каждым элементом массива и максимумом (округление в большую сторону).
Ограничение на данные - все значения входного массива h находятся в диапазоне 1-4: т.е. возможны только 1, 2, 3, 4.
Есть два варианта решения:

#1

Код (Text):

1. int i;
2. int h[4];
3. int hk[4];
4. int h_max;
5. for(i=0;i<4;i++)
6. {
7.     hk[i]=(h_max-1)/h[i]+1;
8. }

#2

Код (Text):

1. int i;
2. int k;
3. int h[4];
4. int hk[4];
5. int h_max;
6. for(i=0;i<4;i++)
7. {
8.     hk[i]=0;
9.     for(k=h_max;k>0;k-=h[i]) hk[i]++;
10. }

Вопрос - целесообразно ли заменять деление вычитанием в данном случае?
Т.е. будет ли быстрее (как-никак деление операция медленная) - при этом помним что в цикле будет максимум 4 итерации.
PS: вопрос по большому счёту относится к x86

 

я бы предложил сделать следующее:
загрузить массив в eax
вычесть 1010101h чтобы числа стали от 0 до 3
умножить на 40100401h чтобы все числа собрались в старшем байте
сдвинуть вправо на 24 разряда
прочитать (h_max-1)/h+1 из таблички на 256 dword'ов

 

Самый быстрый вариант - использовать таблицу: или в лоб 4*4=16 байт или упакованную в int

Зависит от проца и типа операнда. Если использовать 8-битное деление (тайпкастить к char\byte), то на атлонах и PM\Core2 заметного выигрыша не будет, т.к. штраф за непредсказанный переход при выходе из цикла сравним с латентностью деления r8.

 

О, кстати таблица это идея
Можно ж и вообще вот так сделать:

char coefs[4][4]=
{
// ....
}

и читать потом
hk=coefs[h_max-1][h-1];
и табличка выходит поменьше...

 

Угу, а если хочется поизвращаться, то можно вообще ее упаковать в int по 2 бита и использовать как константу magic:
hk=(magic >> ((h_max-1)*4+(h-1))) & 3 + 1;

 

К char приводить не получается - компилятор умничает.
У меня массивы и так в char лежат, компилятор всё равно до int расширяет и потом делит...

 

Вот ту-упые (С)
PS: "Сокращенное" деление в завис-ти не от размера, а от величины операнда используется только в старших PM и Core2, а в PIII и атлонах латентность деления определяется только размером r8\r16\r32.

 

Задача, случайно, не решается одной командой ассемблера XLATB?

 

^ забавно=)

 

Чего забавного?
Одним XLAT не решается.
Разве что таблицу большую делать.