128-bit

Понадобилось на днях умножать и считать остаток от деления для 128 битных чисел на плюсах: (a * b) % c, где все числа 64 битные, а это значит что надо оперировать именно с 128 битами.
Нашел класс uint128_t, который использует два 64 битных числа. и в нем куча функционала. так как boost использовать нельзя было.
Быстро отпилил его, написав вручную недостоющие операторы. Отлично! Даже работает быстро. Но когда запустил на машине для которой создавался код все оказалось медленне раз в 10.
Немного покопав узнал, что дело в 32 битной системе (у меня на ноуте 64 бита). Очень огорчился и уж было думал что всё пропало и ничего сделать нельзя, но потом решил переписать вручную.
Сложить два 128 битных числа можно так:

inline void a_add_b_inplace(uint64_t& a0, uint64_t& a1, const uint64_t b0, const uint64_t b1)
{
 if(a1 >= 0xffffffffffffffffULL - b1)
 {
  ++a0;
 }
 a1 += b1;
 a0 += b0;
}

Умножение двух 64 битных чисел можно эфективно сделать используя три 32 битных числа и сохранить это все в 2 64 битных числа (получится 128 бит информации). Что то типа:

inline void a_mul_b(const uint64_t& a, const uint64_t& b, uint64_t& d0, uint64_t& d1)
{
 uint32_t a0 = (a >> 32) & 0x00ffffffffU;
 uint32_t a1 = a & 0x00ffffffffU;
 uint32_t b0 = (b >> 32);
 uint32_t b1 = b & 0x00ffffffffU;
 uint64_t c0 = ((uint64_t)a0) * b0; // << 64
 uint64_t c1 = ((uint64_t)a0) * b1 + ((uint64_t)a1) * b0; // << 32
 uint64_t c2 = ((uint64_t)a1) * b1;
 d0 = c0; // << 64
 d1 = c2;
 uint64_t c10 = (c1 >> 32) & 0x00ffffffffU;
 uint64_t c11 = c1 & 0x00ffffffffU;
 a_add_b_inplace(d0, d1, c10, c11<<32);
}

Остаток от деления можно получить уже не так просто. Для этого необходимо реализовать ещё несколько операций. Но удивил сам результат - на 32 битной платформе этот код работал в 5 раз бытрее чем класс uint128_t. А ещё на 64 битке эта реализация по скорости почти не отличается от 32-ной. Ура. В итоге я смог реализовать алгоритм Miller-Rabin-а для 64 битных чисел, который работал бы всего в несколько раз меленне на 32-х битной системе, чем на 64-х битной.