128-битное деление без знака на 64-битной машине

Question

У меня 128-битное число хранится как 2 64-битных числа ("Привет" и "Ло"). Мне нужно только разделить его на 32-битное число. Как я мог это сделать, используя родные 64-битные операции с процессором?

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

Answer 1

Если вы храните значение (128 бит) с использованием максимально возможного собственного представления, которое ваша архитектура может обработать (64 бит), у вас будут проблемы с обработкой промежуточных результатов деления (как вы уже нашли:)).

Но вы всегда можете использовать более маленькое представление. А как насчет ЧЕТЫРЕ числа 32-битных? Таким образом, вы можете использовать собственные 64-битные операции без проблем переполнения.

Простую реализацию (в Delphi) можно найти здесь.

Answer 2

Подзаголовок второго тома « Искусства компьютерного программирования» — «Получисловые алгоритмы» . Это уместно, так как решение довольно простое, когда вы думаете о числе как об уравнении, а не как о числе.

Думайте о числе какHx + L, где х равно 2⁶⁴. Если мы делим на, назовем это Y, то тривиально верно, чтоHx = (N + M)xгде N делится на Y, а M меньше Y. Зачем мне это делать?(Hx + L) / Yтеперь можно выразить как(N / Y)x + (Mx + L) / Y. Значения N, N / Y и M являются целыми числами: N простоH / Yи М естьH % YОднако, поскольку x равно 2⁶⁴ , это все еще приводит нас к 128 делению на что-то, что вызовет аппаратную ошибку (как уже отмечали люди), если Y равно 1.

Итак, что вы можете сделать, так это переформулировать задачу как (Ax³ + Bx² + Cx + D) / Y , где x равно 2³². Теперь вы можете перейти вниз: (A / Y)x³ + (((A % Y)x + B) / Y)x² + (((((A % Y)x + B) % Y)x + C) / Y)x + ((((((A % Y)x + B) % Y)x + C) / Y)x + D) / Y. Если у вас есть только 64-битные деления: вы делаете четыре деления, а в первых трех берете остаток и сдвигаете его на 32 бита и/или в следующем коэффициенте для следующего деления.

Это математика, стоящая за решением, которое уже было дано дважды.

Answer 3

У меня есть DECIMAL структура, состоящая из трех 32-битных значений: Lo32, Mid32 и Hi32 = всего 96 бит.

Вы можете легко расширить мой код на C для деления на 128, 256, 512 или даже 1024 бит.

// in-place divide Dividend / Divisor including previous rest and returning new rest
static void Divide32(DWORD* pu32_Dividend, DWORD u32_Divisor, DWORD* pu32_Rest)
{
    ULONGLONG u64_Dividend = *pu32_Rest;
    u64_Dividend <<= 32;
    u64_Dividend |= *pu32_Dividend;

    *pu32_Dividend = (DWORD)(u64_Dividend / u32_Divisor);
    *pu32_Rest     = (DWORD)(u64_Dividend % u32_Divisor);
}

// in-place divide 96 bit DECIMAL structure
static bool DivideByDword(DECIMAL* pk_Decimal, DWORD u32_Divisor)
{
    if (u32_Divisor == 0)
        return false;

    if (u32_Divisor > 1)
    {
        DWORD u32_Rest = 0;
        Divide32(&pk_Decimal->Hi32,  u32_Divisor, &u32_Rest); // Hi FIRST!
        Divide32(&pk_Decimal->Mid32, u32_Divisor, &u32_Rest);
        Divide32(&pk_Decimal->Lo32,  u32_Divisor, &u32_Rest);
    }
    return true;
}

Answer 4

Как я мог это сделать, используя собственные 64-битные операции с CPU?

Поскольку вам нужны собственные операции, вам придется использовать некоторые встроенные типы или внутренние функции. Все приведенные выше ответы дадут вам только общие решения C, которые не будут скомпилированы в инструкции деления.

У большинства современных 64-битных компиляторов есть несколько способов деления 128 на 64. В MSVC используйте _div128() а также _udiv128() так что тебе просто нужно позвонить _udiv128(hi, lo, divisor, &remainder)

В _div128intrinsic делит 128-битное целое число на 64-битное целое число. Возвращаемое значение содержит частное, а внутренняя функция возвращает остаток через параметр указателя._div128 специфичен для Microsoft.

В Clang, GCC и ICC есть __int128 введите, и вы можете использовать это напрямую

unsigned __int128 div128by32(unsigned __int128 x, uint64_t y)
{
    return x/y;
}

Answer 5

Некоторый код c здесь.

Answer 6

Я попытался опубликовать машинный код, но ваша платформа жалуется на форматирование.