Какой самый простой способ вычислить наименьшее целое число, большее или равное a / b?

Question

r, a и b являются целыми числами.

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

r = (a / b) + (((a % b) != 0) ? 1 : 0);

если b - степень 2, то a / b можно заменить на a >> log2(b)

и a % b с a & (b-1), что должно сэкономить много вычислительного времени.

Знаете ли вы лучшее решение?

Answer 1

val r = (a + b - 1) / b

Например:

scala> for(a <- 1 to 10; b <- 1 to a) println("a: "+a+"\tb: "+b+"\tr: "+((a+b-1)/b))
a: 1    b: 1    r: 1
a: 2    b: 1    r: 2
a: 2    b: 2    r: 1
a: 3    b: 1    r: 3
a: 3    b: 2    r: 2
a: 3    b: 3    r: 1
a: 4    b: 1    r: 4
a: 4    b: 2    r: 2
a: 4    b: 3    r: 2
a: 4    b: 4    r: 1
a: 5    b: 1    r: 5
a: 5    b: 2    r: 3
a: 5    b: 3    r: 2
a: 5    b: 4    r: 2
a: 5    b: 5    r: 1
a: 6    b: 1    r: 6
a: 6    b: 2    r: 3
a: 6    b: 3    r: 2
a: 6    b: 4    r: 2
a: 6    b: 5    r: 2
a: 6    b: 6    r: 1
a: 7    b: 1    r: 7
a: 7    b: 2    r: 4
a: 7    b: 3    r: 3
a: 7    b: 4    r: 2
a: 7    b: 5    r: 2
a: 7    b: 6    r: 2
a: 7    b: 7    r: 1
a: 8    b: 1    r: 8
a: 8    b: 2    r: 4
a: 8    b: 3    r: 3
a: 8    b: 4    r: 2
a: 8    b: 5    r: 2
a: 8    b: 6    r: 2
a: 8    b: 7    r: 2
a: 8    b: 8    r: 1
a: 9    b: 1    r: 9
a: 9    b: 2    r: 5
a: 9    b: 3    r: 3
a: 9    b: 4    r: 3
a: 9    b: 5    r: 2
a: 9    b: 6    r: 2
a: 9    b: 7    r: 2
a: 9    b: 8    r: 2
a: 9    b: 9    r: 1
a: 10   b: 1    r: 10
a: 10   b: 2    r: 5
a: 10   b: 3    r: 4
a: 10   b: 4    r: 3
a: 10   b: 5    r: 2
a: 10   b: 6    r: 2
a: 10   b: 7    r: 2
a: 10   b: 8    r: 2
a: 10   b: 9    r: 2
a: 10   b: 10   r: 1

Предполагается, что a и b положительные. Если любой из них отрицательный, это зависит от того, является ли деление симметричным или промежуточным (современные языки и платформы симметричны), а также сигнал a и b.

Если a*b >= 0, то формула работает как дано. Если деление симметричное и a*b < 0, то a / b дает правильный ответ.

Answer 2

В заголовке вы спрашиваете о «простейших» - но вопрос намекает на наиболее «эффективный». Какой тебе нужен? На практике самое простое не всегда приравнивается к самому эффективному.

Так что, если вам нужен самый простой метод, вы, вероятно, должны использовать функцию потолка вашего языка (обычно называемую ceil ), если вам нужен самый эффективный - это действительно очень зависит на используемом процессоре (реализует ли он аппаратное деление и другие подобные факторы)

Кроме того, я немного скептически отношусь к производительности log2 - но я могу ошибаться. Однако ясно одно: оптимизация ради оптимизации почти всегда не очень хорошая идея.

Answer 3

А как же:

(a - 1) / b + 1;

Очевидно, вы должны следить за собой, если a может быть 0 или меньше. Отрицательные числа не обязательно разделяют, как вы ожидаете, это зависит от языка и реализации.

Answer 4

по модулю может быть реализовано% n = a - (n * (a / n);

Таким образом, учитывая это, вы можете переписать как

const int div = a / b;
r = div + (((a - (n * div)) != 0) ? 1 : 0 );

, что будет незначительно быстрее, поскольку вы делаете только один дел вместо 2 *.

Редактировать: Если b является константой, то вы можете полностью удалить деление и заменить его умножением на «магическое число» (относящееся к делителю константы), которое снова будет немного быстрее Затем компилятор снова выполнит эту оптимизацию в любом случае с постоянным делителем.

Answer 5

Поскольку язык не указан, я собираюсь написать решение и в ANS Forth ...

: div ( a b -- r)
  FM/MOD     \ a b -- q rest
  IF 1+ THEN \ q rest -- r
;

Answer 6

Если вы находитесь на рабочем столе, попробуйте числа с плавающей запятой и округлите их. Но я сомневаюсь, что вы можете найти что-нибудь более дешевое, чем два int-решения плюс дополнение.

Единственным другим вариантом является оператор DIVMOD, который поддерживается некоторыми процессорами. Это даст вам и разделение и остальное в одном вызове.

Answer 7

Это может или не может подходить для того, что вы ищете, но большинство (если не все) языки предоставляют доступ к функции математического потолка. Например, в C # запись Math.Ceiling(5/2) дает 3.