Вопрос к коллегам-программистам

[lumag]

Коллеги,

В кои-то веки столкнулся с задачкой, которую я не знаю как оптимизировать. Надо побитово умножить число на матрицу.

Псевдокод:

unsigned val;
unsigned A[];
unsigned res;
int i;
...
res = 0;
for (i = 0; i < 32; i++)
  if (val & (1 << i))
    res ^= A[i];

Пара моих попыток подойти в лоб не увенчалась серьезным ускорением.

Кто-нибудь может что-нибудь хорошее подсказать/сообразить? А то я, кажется, отвык решать такие задачи.

UPD: Получил ускорение ~30% тупо раскрыв цикл. Все равно очень медленно. Хочется чего-то более радикального.

UPD2: Матрица - фиксированная, число изменяется.

Comments

[denspb.livejournal.com]

Это одиночное действие?
И если повторяющееся, то матрица/число оказываются одинаковыми?

[lumag]

Повторяющееся, матрица фиксирована.

[antilamer.livejournal.com]

Можно попробовать так:
* для каждого из 256 возможных байтов закешировать результат умножения A на вектор этого байта: m
* разбить val на 4 байта b1, b2, b3, b4
* res ^= m[b1] ^ m[b2] ^ m[b3] ^ m[b4]

UPD: увидел вконтакте, что тебе Саша Аланов то же самое написал, и что это ускоряет в 8 раз. Ну что ж, круто :)

[denspb.livejournal.com]

Тогда та же идея то и у antilamer.

[lumag]

Да, спасибо.

[lumag]

:)