Эффективное умножение / деление двух 128-битных целых чисел на x86 (без 64-битных)
Компилятор: MinGW / GCC
Проблемы: Код GPL / LGPL не разрешен (GMP или любая другая библиотека bignum, если на то пошло, для этой проблемы слишком много. , так как класс у меня уже реализован).
Я создал свой собственный 128-битный большой целочисленный класс фиксированного размера (предназначенный для использования в игровом движке, но может быть обобщен для любого случая использования), и я нахожу производительность текущего умножения и Операции разделения должны быть довольно ужасными (да, я рассчитал их по времени, см. ниже), и я хотел бы улучшить (или изменить) алгоритмы, выполняющие низкоуровневую обработку чисел.
Когда дело доходит до операторов умножения и деления, они невыносимо медленны по сравнению практически со всем остальным в классе.
Это приблизительные измерения относительно моего собственного компьютера:
Raw times as defined by QueryPerformanceFrequency:
1/60sec 31080833u
Addition: ~8u
Subtraction: ~8u
Multiplication: ~546u
Division: ~4760u (with maximum bit count)
Как видите, простое умножение во много-много раз медленнее, чем сложение или вычитание. Деление примерно в 10 раз медленнее умножения.
Я хотел бы повысить скорость этих двух операторов, потому что может быть очень большой объем вычислений, выполняемых за один кадр (скалярные произведения, различные методы обнаружения столкновений и т. Д.).
Структура (методы опущены) выглядит примерно так:
class uint128_t
{
public:
unsigned long int dw3, dw2, dw1, dw0;
//...
}
Умножение в настоящее время выполняется с использованием типичного метода длинного умножения (в сборке, чтобы я мог поймать EDX ), игнорируя слова, выходящие за пределы допустимого диапазона (то есть я делаю только 10 mull по сравнению с 16).
В разделе используется алгоритм сдвиг-вычитание (скорость зависит от количества бит в операндах). Однако в сборке это не делается. Я обнаружил, что это слишком сложно понять, и решил позволить компилятору оптимизировать это.
Я несколько дней ходил в Google, просматривая страницы, описывающие такие алгоритмы, как Умножение Карацубы , деление с высоким основанием и Деление Ньютона-Рэпсона , но математические символы представляют собой немного слишком далеко над моей головой. Я хотел бы использовать некоторые из этих продвинутых методов для ускорения моего кода, но сначала мне нужно было бы перевести «греческий» во что-то понятное.
Для тех, кто считает мои усилия «преждевременной оптимизацией»; Я считаю этот код узким местом, потому что сами операции элементарной математики становятся медленными. Я могу игнорировать такие типы оптимизации в коде более высокого уровня, но этот код будет вызываться / использоваться достаточно, чтобы это имело значение.
Я хотел бы получить предложения о том, какой алгоритм мне следует использовать для улучшения умножения и деления (если это возможно), и простое (надеюсь, легкое для понимания) объяснение того, как работает предлагаемый алгоритм, будет высоко оценено .
РЕДАКТИРОВАТЬ: Улучшения умножения
Мне удалось улучшить операцию умножения, вставив код в оператор * =, и это кажется максимально быстрым.
Updated raw times:
1/60sec 31080833u
Addition: ~8u
Subtraction: ~8u
Multiplication: ~100u (lowest ~86u, highest around ~256u)
Division: ~4760u (with maximum bit count)
Вот небольшой код для вашего изучения (обратите внимание, что мои имена типов на самом деле разные, это было отредактировано для простоты):
//File: "int128_t.h"
class int128_t
{
uint32_t dw3, dw2, dw1, dw0;
// Various constrctors, operators, etc...
int128_t& operator*=(const int128_t& rhs) __attribute__((always_inline))
{
int128_t Urhs(rhs);
uint32_t lhs_xor_mask = (int32_t(dw3) >> 31);
uint32_t rhs_xor_mask = (int32_t(Urhs.dw3) >> 31);
uint32_t result_xor_mask = (lhs_xor_mask ^ rhs_xor_mask);
dw0 ^= lhs_xor_mask;
dw1 ^= lhs_xor_mask;
dw2 ^= lhs_xor_mask;
dw3 ^= lhs_xor_mask;
Urhs.dw0 ^= rhs_xor_mask;
Urhs.dw1 ^= rhs_xor_mask;
Urhs.dw2 ^= rhs_xor_mask;
Urhs.dw3 ^= rhs_xor_mask;
*this += (lhs_xor_mask & 1);
Urhs += (rhs_xor_mask & 1);
struct mul128_t
{
int128_t dqw1, dqw0;
mul128_t(const int128_t& dqw1, const int128_t& dqw0): dqw1(dqw1), dqw0(dqw0){}
};
mul128_t data(Urhs,*this);
asm volatile(
"push %%ebp \n\
movl %%eax, %%ebp \n\
movl $0x00, %%ebx \n\
movl $0x00, %%ecx \n\
movl $0x00, %%esi \n\
movl $0x00, %%edi \n\
movl 28(%%ebp), %%eax #Calc: (dw0*dw0) \n\
mull 12(%%ebp) \n\
addl %%eax, %%ebx \n\
adcl %%edx, %%ecx \n\
adcl $0x00, %%esi \n\
adcl $0x00, %%edi \n\
movl 24(%%ebp), %%eax #Calc: (dw1*dw0) \n\
mull 12(%%ebp) \n\
addl %%eax, %%ecx \n\
adcl %%edx, %%esi \n\
adcl $0x00, %%edi \n\
movl 20(%%ebp), %%eax #Calc: (dw2*dw0) \n\
mull 12(%%ebp) \n\
addl %%eax, %%esi \n\
adcl %%edx, %%edi \n\
movl 16(%%ebp), %%eax #Calc: (dw3*dw0) \n\
mull 12(%%ebp) \n\
addl %%eax, %%edi \n\
movl 28(%%ebp), %%eax #Calc: (dw0*dw1) \n\
mull 8(%%ebp) \n\
addl %%eax, %%ecx \n\
adcl %%edx, %%esi \n\
adcl $0x00, %%edi \n\
movl 24(%%ebp), %%eax #Calc: (dw1*dw1) \n\
mull 8(%%ebp) \n\
addl %%eax, %%esi \n\
adcl %%edx, %%edi \n\
movl 20(%%ebp), %%eax #Calc: (dw2*dw1) \n\
mull 8(%%ebp) \n\
addl %%eax, %%edi \n\
movl 28(%%ebp), %%eax #Calc: (dw0*dw2) \n\
mull 4(%%ebp) \n\
addl %%eax, %%esi \n\
adcl %%edx, %%edi \n\
movl 24(%%ebp), %%eax #Calc: (dw1*dw2) \n\
mull 4(%%ebp) \n\
addl %%eax, %%edi \n\
movl 28(%%ebp), %%eax #Calc: (dw0*dw3) \n\
mull (%%ebp) \n\
addl %%eax, %%edi \n\
pop %%ebp \n"
:"=b"(this->dw0),"=c"(this->dw1),"=S"(this->dw2),"=D"(this->dw3)
:"a"(&data):"%ebp");
dw0 ^= result_xor_mask;
dw1 ^= result_xor_mask;
dw2 ^= result_xor_mask;
dw3 ^= result_xor_mask;
return (*this += (result_xor_mask & 1));
}
};
Что касается деления, изучение кода довольно бессмысленно, так как мне нужно будет изменить математический алгоритм, чтобы увидеть какие-либо существенные преимущества. Единственный возможный выбор, кажется, это деление с большим основанием, но мне еще предстоит сгладить (на мой взгляд) только , как это будет работать.