Как вычислить 2⁶⁴ / n в C? - PullRequest
Новая
       71

Как вычислить 2⁶⁴ / n в C?

10 голосов
/ 08 апреля 2019

Как вычислить целочисленное деление, 2 64 / n? Предполагая, что:

  • unsigned long - 64-битный
  • Мы используем 64-битный процессор
  • 1 64

Если мы сделаем 18446744073709551616ul / n, мы получим warning: integer constant is too large for its type во время компиляции. Это потому, что мы не можем выразить 2 64 в 64-битном процессоре. Другой способ заключается в следующем: 

#define IS_POWER_OF_TWO(x) ((x & (x - 1)) == 0)

unsigned long q = 18446744073709551615ul / n;
if (IS_POWER_OF_TWO(n))
    return q + 1;
else
    return q;

Есть ли более быстрая (с циклом процессора) или более чистая (с кодированием) реализация?

Ответы [ 4 ]

9 голосов
/ 09 апреля 2019
Идея

в phuclv использовать -n умна, но ее можно сделать намного проще.В качестве беззнаковых длин мы имеем -n = 2 64 -n, тогда (-n) / n = 2 64 / n - 1, и мы можем просто добавить обратно 1. 

unsigned long foo(unsigned long n) {
  return (-n)/n + 1;
}

Сгенерированный код - это то, что вы ожидаете (gcc 8.3 на x86-64 через godbolt ): 

    mov     rax, rdi
    xor     edx, edx
    neg     rax
    div     rdi
    add     rax, 1
    ret
4 голосов
/ 08 апреля 2019

Я нашел другое решение, которое было вдохновлено этим вопросом . Оттуда мы знаем, что

(a 1 + a 2 + a 3 + ... + a n ) / n =

(a 1 / n + a 2 / n + a 3 / n + ... + a n / n) + (a 1 % n + a 2 % n + a 3 % n + ... + a n % п) / п * +1032 *

Выбрав a 1 = a 2 = a 3 = ... = a n-1 = 1 и a n = 2 64 - n у нас будет

(a 1 + a 2 + a 3 + ... + a n ) / n = (1 + 1 + 1 + ... + (2 64 - n)) / n = 2 64 / n

= [(n - 1) * 1 / n + (2 64 - n) / n] + [(n - 1) * 0 + (2 64 - n)% n] / n

= (2 64 - n) / n + ((2 64 - n)% n) / n

2 64 - n - это 2-е дополнение к n, равное -n, или мы также можем записать его как ~0 - n + 1. Таким образом, окончательное решение будет 

uint64_t twoPow64div(uint64_t n)
{
    return (-n)/n + (n + (-n) % n)/n + (n > 1ULL << 63);
}

Последняя часть - исправить результат, потому что мы имеем дело с целыми числами без знака, а не со знаком, как в другом вопросе. Проверено на моем ПК в 32- и 64-битной версии, и результат соответствует вашему решению

В MSVC, однако, имеется встроенная функция 128-битного деления , поэтому вы можете использовать вот так 

uint64_t remainder;
return _udiv128(1, 0, n, &remainder);

, что приводит к чистому выводу 

    mov     edx, 1
    xor     eax, eax
    div     rcx
    ret     0

Вот демоверсия

На большинстве компиляторов x86 long double также имеет точность 64 бита, поэтому вы можете использовать любой из этих 

(uint64_t)(powl(2, 64)/n)
(uint64_t)(((long double)~0ULL + 1)/n)
(uint64_t)(18446744073709551616.0L/n)

хотя, вероятно, производительность будет хуже. Это также может быть применено к любым реализациям, где long double имеет более 63 бит значения, например, к PowerPC или Sparc

.

Есть связанный вопрос о вычислении ((UINT_MAX + 1)/x)*x - 1: Целочисленная арифметика: добавьте 1 к UINT_MAX и разделите на n без переполнения , используя также умные решения. Исходя из этого мы имеем

2 64 / n = (2 64 - n + n) / n = (2 64 - n) / n + 1 = (- n) / n + 1

что по сути является просто еще одним способом получить ответ Нейта Элдриджа

Вот некоторая демонстрация для других компиляторов на godbolt

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

2 голосов
/ 09 апреля 2019

Мы используем 64-битный процессор

Какой 64-битный процессор?

В общем случае, если вы умножаете число с N битами на другое число, которое имеетM битов, результат будет иметь до N + M битов.Для целочисленного деления это аналогично - если число с N битами делится на число с M битами, результат будет иметь N-M + 1 бит.

Поскольку умножение естественным образом «расширяется» (результат имеет больше цифрчем любое из исходных чисел), а целочисленное деление естественно «сужается» (результат имеет меньше цифр);некоторые процессоры поддерживают «умножение с расширением» и «деление сужения».

Другими словами, некоторые 64-разрядные процессоры поддерживают деление 128-разрядного числа на 64-разрядное число, чтобы получить 64-разрядный результат.Например, в 80x86 это одна инструкция DIV.

К сожалению, C не поддерживает "умножение с расширением" или "сужение деления".Он поддерживает только «результат того же размера, что и исходные операнды».

По иронии судьбы (для 64-разрядных делителей без знака на 64-разрядных 80x86) другого выбора нет, и компилятор должен использовать инструкцию DIV, которая будетразделите 128-битное число на 64-битное число.Это означает, что язык C вынуждает вас использовать 64-битный числитель, затем код, сгенерированный компилятором, расширяет ваш 64-битный числитель до 128 бит и делит его на 64-битное число, чтобы получить 64-битный результат;а затем вы пишете дополнительный код, чтобы обойти тот факт, что язык не позволил вам использовать 128-битный числитель для начала.

Надеемся, вы сможете увидеть, как эту ситуацию можно считать "не идеальной".

Что бы я хотел, это способ заставить компилятор поддерживать "сужение деления".Например, возможно, злоупотребляя приведениями и надеясь, что оптимизатор достаточно умен, например: 

  __uint128_t numerator = (__uint128_t)1 << 64;
  if(n > 1) {
      return (uint64_t)(numerator/n);
  }

Я проверил это для последних версий GCC, CLANG и ICC (используя https://godbolt.org/)и обнаружил, что (для 64-битных 80x86) ни один из компиляторов не достаточно умен, чтобы понять, что единственная инструкция DIV - это все, что нужно (все они сгенерировали код, который выполняет call __udivti3, что является дорогой функцией для получения128-битный результат).Компиляторы будут использовать DIV только тогда, когда (128-битный) числитель равен 64 битам (и ему будет предшествовать XOR RDX,RDX, чтобы установить наибольшую половину 128-битного числителя в нули).

Другими словами, вполне вероятно, что единственный способ получить идеальный код (сама инструкция DIV на 64-битной 80x86) - прибегнуть к встроенной сборке.

Например, лучший код, который вы 'Вы получите без встроенной сборки (из ответа Нейта Элдриджа): 

    mov     rax, rdi
    xor     edx, edx
    neg     rax
    div     rdi
    add     rax, 1
    ret

... и лучший возможный код: 

    mov     edx, 1
    xor     rax, rax
    div     rdi
    ret
1 голос
/ 08 апреля 2019

Ваш путь довольно хорош. может лучше написать так: 

return 18446744073709551615ul / n + ((n&(n-1)) ? 0:1);

Надеемся, что компилятор заметит, что он может выполнить условное перемещение вместо ветки.

Компилировать и разбирать.

...