Деление числа, представленного двумя словами, на число, представленное одним?

Question

У меня есть два числа, X и Y.

Y является одним целым примитивом без знака, например long unsigned int, (В этом случае нет более крупного примитива для upcast до выполнения операции.)

X представлен двумя примитивами: X0 того же типа, что и Y и представляет младшие биты X, а X1 того же типа и представляет старшие биты X.

X / Y всегда будет представимым с использованием того же типа, что и Y, т.е. можно предположить, что операция не переполняется. (Поскольку X случайно является произведением двух значений того же типа, что и Y, одно из которых меньше или равно Y.)

Какой эффективный способ определить результат этого деления?

Answer 1

Вы не указали платформу, которая имеет решающее значение для ответа.

X / Y всегда будет представимым с использованием того же типа, что и Y, т.е. можно предположить, что операция не переполняется. (Поскольку X случайно является произведением двух значений того же типа, что и Y, одно из которых меньше или равно Y.)

В архитектуре x86-64 вы можете воспользоваться этим фактом, разделив RDX:RAX пара, так что это на самом деле так же, как если бы у вас был один "склеенный" 128-битный регистр для дивидендов. Однако помните, что если вышеупомянутый инвариант не всегда выполняется, вы получите исключение деления из CPU.

Тем не менее, одна реализация должна использовать встроенную сборку, например:

/* divides x1:x0 pair by y, assumes that quotient <= UINT64_MAX  */
uint64_t udiv128_64_unsafe(uint64_t x0, uint64_t x1, uint64_t y)
{
    __asm__ (
        "divq\t%3"
        : "=a" (x0)
        : "0" (x0), "d" (x1), "rm" (y)
    );
    return x0;
}

который GCC 6.3.0 переводит хорошо (в -O1):

udiv128_64_unsafe:
        mov     rcx, rdx            ; place the y (divisor) in RCX 
        mov     rax, rdi            ; low part of the dividend (x0)
        mov     rdx, rsi            ; high part of the divided (x1)
        divq    rcx                 ; RAX = RDX:RAX / RCX
        ret                         ; RAX is return value

Например, для X = 65454567423355465643444545, Y = 86439334393432232:

#include <stdio.h>
#include <inttypes.h>

uint64_t udiv128_64_unsafe(uint64_t x0, uint64_t x1, uint64_t y) { ... }

int main(void)
{
    printf("%" PRIu64 "\n", udiv128_64_unsafe(0x35c0ecb3fea1c941ULL, 0x36248bULL,
        86439334393432232ULL));
    return 0;
}

данная программа тестового драйвера дает:

757231275

Answer 2

gcc имеет __int128 а также unsigned __int128 для архитектуры x86. В прошлом я успешно использовал его для выполнения описанных вами операций. Я уверен, что все основные компиляторы имеют эквиваленты.

Answer 3

"Делить двузначное число на 1 цифру, давая 1-значное частное и остаток" - это основной примитив, который вам нужен для синтеза больших делений. Если вы не имеете его (с цифрой == unsigned long int) в вашем оборудовании, вам нужно использовать меньшие цифры.

В вашем случае, разделите Y на 2 половинных целых числа и X на 4 половинных целых числа и делите таким образом.