Добавление нескольких слов в C

У меня есть программа C, которая использует GCC __uint128_t это здорово, но теперь мои потребности выросли за пределы этого.

Какие у меня варианты быстрой арифметики с 196 или 256 битами?

Единственное, что мне нужно, это сложение (и мне не нужен бит переноса, т.е. я буду работать в моде 2^192 или 2^256).

Скорость важна, поэтому я не хочу переходить к общей многоцелевой точности, если это вообще возможно. (На самом деле мой код в некоторых местах использует multiprecision, но он находится в критическом цикле и будет выполняться десятки миллиардов раз. До сих пор multiprecision должен выполняться только десятки тысяч раз.)

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

Что вы посоветуете, о большое переполнение стека?

Пояснение: GMP слишком медленный для моих нужд. Хотя я на самом деле использую мультипрецизионность в своем коде, он не во внутреннем цикле и выполняется менее 10^5 раз. Горячая петля работает больше как 10^12 раз. Когда я изменил свой код (увеличив размер параметра), чтобы мультиточностная часть работала чаще по сравнению с одинарной точностью, у меня было 100-кратное замедление (я думаю, что это связано главным образом с проблемами управления памятью, а не с лишними мопами). Я хотел бы снизить это до 4-х кратного замедления или лучше.

Источник

2 ответа

Решение

256-битная версия

__uint128_t a[2], b[2], c[2];  // c = a + b
c[0] = a[0] + b[0];
c[1] = a[1] + b[1] + (c[0] < a[0]);

Если вы используете это много раз в цикле, вы должны рассмотреть возможность сделать его параллельным по SIMD и многопоточности

Редактировать: 192-битная версия. Таким образом, вы можете исключить 128-битное сравнение, как в @harold:

struct __uint192_t {
    __uint128_t H;
    __uint64_t L;
} a, b, c;  // c = a + b
c.L = a.L + b.L;
c.H = a.H + b.H + (c.L < a.L);
Источник

Вы можете проверить, если "добавить (low < oldlow) смоделировать перенос "-техники из этого ответа достаточно быстро. Это немного усложняется тем, что low является __uint128_t здесь, это может повредить генерацию кода. Вы можете попробовать это с 4 uint64_tТакже я не знаю, будет ли это лучше или хуже.

Если этого недостаточно, перейдите к встроенной сборке и напрямую используйте флаг переноса - лучше не будет, но у вас будут обычные недостатки использования встроенной сборки.

Источник
Другие вопросы по тегам