Многословное добавление в C

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

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

Единственное, что мне нужно, это сложение (и мне не нужен бит переноса, то есть я буду работать с модом 2 ¹⁹² или 2 ²⁵⁶).

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

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

Какой твой совет, о великий Кару?

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

Ответ 1

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);

Ответ 2

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

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