128-битная арифметика на x64 в C

При реализации bignums на x86, очевидно, самый эффективный выбор для размера цифр - 32 бита. Тем не менее, вам нужна арифметика, в два раза превышающая размер цифры (т.е. 32+32=33, 32*32=64, 64/32=32). К счастью, x86 не только обеспечивает это, но и доступен из переносимого C (uint64_t).

Аналогично, на x64 хотелось бы использовать 64-битные цифры. Для этого потребуется 128-битная арифметика (то есть 64+64=65, 64*64=128, 128/64=64). К счастью, x64 обеспечивает это. К сожалению, это не доступно из портативного C, хотя, очевидно, можно было бы погрузиться в сборку.

Поэтому мой вопрос: доступен ли он из непортативного C. Предоставляют ли к этому доступ компиляторы C на x64, и если да, то каков синтаксис?

(Обратите внимание, что я говорю не о 128-битных векторах, которые строго рассматриваются как наборы из 32 или 64-битных слов без переноса между ними, а о реальных 128-битных целочисленных операциях.)

Источник

2 ответа

Решение

GCC имеет __uint128_t а также __int128_t как расширения.

Источник

GCC 4.1 представил начальную поддержку 128-битных целых чисел с __int128_t и __uint128_tвстроенные типы, но 128-битный тип был официально выпущен с GCC 4.6 как __int128 / unsigned __int128

Clang также поддерживает эти типы, хотя я не знаю с каких пор. Первая версия Godbolt (3.0.0) поддерживает __int128_t хотя

ICC получил такую ​​же поддержку, начиная с версии 13.0.0: 128-битные целые числа, поддерживающие +, -, *, / и% в компиляторе Intel C?

Смотрите также

Если вы используете MSVC, то нет прямой поддержки 128-битного типа, но есть много встроенных функций, помогающих вам выполнять 128-битные операции:

  • 64*64 = 128: _mul128(), _umul128(), __mulh(), __umulh()

  • 128/64 = 64: _div128(), _udiv128()

  • 64+64 = 65: перенос в сложении можно легко получить, сравнив младшую часть суммы с любым из операндов:

    struct uint128 {
    uint64_t H, L;
};

inline uint128 add(uint128 a, uint128 b)
{
    uint128 c;
    c.L = a.L + b.L;                // add low parts
    c.H = a.H + b.H + (c.L < a.L);  // add high parts and carry
    return c;
}

    То же самое можно использовать для 128-битного вычитания.

Есть также встроенные функции для переключения, хотя их реализация тривиальна: __shiftleft128(), __shiftright128()

Если вы используете неподдерживаемый компилятор, просто используйте некоторые типы фиксированной ширины из многих доступных библиотек, это будет намного быстрее. Например ttmath:UInt<4> (128-битный тип int с четырьмя 32-битными конечностями) или (u)int128_tв Boost.Multiprecision и https://github.com/calccrypto/uint128_t. Арифметическая библиотека произвольной точности, такая как GMP, слишком дорога для этого. Один пример: история оптимизации: переход с GMP на gcc __int128 уменьшено время работы на 95%

Источник

Вы можете проверить арифметическую библиотеку GNU Multiple Precision:

http://gmplib.org/

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