Настройка коэффициента целочисленного деления в C ++ - PullRequest
Новая
       52

Настройка коэффициента целочисленного деления в C ++

0 голосов
/ 19 декабря 2018

Пример: деревья B +

Учитывая N кортежей в дереве, самое большее di дочерних элементов на внутренний узел и самое большее dl значений на лист, минимальная высота дерева B + будет h = ceil(log_di((N + dl - 1) / dl)) если я не ошибаюсь.Это верно только в том случае, если / обозначает целочисленное деление, и я, вероятно, мог бы заменить (N + dl - 1) / dl на static_cast<double>(N) / dl. 

#include <cmath>
int minHeight(int N)
{
    constexpr int di = 256;
    constexpr int dl = 255;
    return std::lround(std::ceil(log((N + (dl - 1)) / dl) / log(di)));
}

Мой интерес заключается в схеме: (N + d - 1) /d.Это, кажется, используется при вычислении наименьшего кратного делителя (d), который больше или равен делимому (N).

Вопросы

  1. Имеет ли этот шаблон какое-либо имясвязано с этим?Насколько часто это происходит при разработке структур данных и алгоритмов?
  2. Есть ли другой способ написать этот код на c ++, чтобы его было легче понять, если он необычен?

1 Ответ

0 голосов
/ 19 декабря 2018

(N + d - 1) / d - это совершенно нормальный способ написания целочисленного выражения в C ++.Все члены в этом выражении имеют целочисленный тип, поэтому, в частности, числитель и знаменатель деления / также int.Следовательно, C ++ будет применять / в качестве оператора деления для int типов.

Я не совсем уверен, что именно вы задаете в любом из ваших вопросов.У этого «шаблона» нет определенного имени, о котором я знаю, но я не уверен, почему вы думаете, что оно должно иметь его.Это просто математическое выражение.

Что касается «облегчения понимания», это, конечно, субъективно, но (кроме того факта, что переменные не имеют информативных имен), я нахожу его отлично читаемым.Если вы ищете алгебраическое упрощение выражения, то я бы предостерег вас от этого.Хотя (N/d) + (1/d) - 1, например, выглядит математически эквивалентным, в общем случае это не так.Это происходит главным образом из-за вышеупомянутого факта, что это целочисленные деления, но также и потому, что тип int имеет конечную точность, которая может повлиять на результат в некоторых случаях (например, с целочисленным переполнением).

...