Безопасно ли заменять "a/(b*c)" на "a/b/c" при использовании целочисленного деления?

Question

Безопасно ли заменить a/(b*c) с a/b/c при использовании целочисленного деления на натуральные числа a,b,cили я рискую потерять информацию?

Я сделал несколько случайных тестов и не смог найти пример a/(b*c) != a/b/cЯ уверен, что это безопасно, но не совсем уверен, как это доказать.

Спасибо.

Answer 1

Математика

Как математические выражения, ⌊a/(bc)⌋ а также ⌊⌊a/b⌋/c⌋ эквивалентны всякий раз, когда b ненулевой и c является положительным целым числом (и, в частности, для положительных чисел a, b, c). Стандартным справочником для подобных вещей является восхитительная книга Грэма, Кнута и Паташника " Конкретная математика: основа компьютерных наук ". В ней глава 3 в основном посвящена полам и потолкам, и это доказано на странице 71 как часть гораздо более общего результата:

В 3.10 выше, вы можете определить x = a/b (математическое, то есть реальное деление), и f(x) = x/c (точное деление снова), и включите их в результат слева ⌊f(x)⌋ = ⌊f(⌊x⌋)⌋ (после проверки того, что условия на f держать здесь), чтобы получить ⌊a/(bc)⌋ на LHS равно ⌊⌊a/b⌋/c⌋ на RHS.

Если мы не хотим полагаться на ссылку в книге, мы можем доказать ⌊a/(bc)⌋ = ⌊⌊a/b⌋/c⌋ напрямую используя свои методы. Обратите внимание, что с x = a/b (реальное число), мы пытаемся доказать, что ⌊x/c⌋ = ⌊⌊x⌋/c⌋, Так:

• если x целое число, то доказывать нечего, так как x = ⌊x⌋,
• Иначе, ⌊x⌋ < x, так ⌊x⌋/c < x/c Который означает, что ⌊⌊x⌋/c⌋ ≤ ⌊x/c⌋, (Мы хотим показать, что оно равно.) Предположим, что ради противоречия ⌊⌊x⌋/c⌋ < ⌊x/c⌋ тогда должно быть число y такое, что ⌊x⌋ < y ≤ x а также y/c = ⌊x/c⌋, (Как мы увеличиваем число от ⌊x⌋ в x и рассмотрим деление на cгде-то мы должны достичь точного значения ⌊x/c⌋.) Но это означает, что y = c*⌊x/c⌋ целое число между ⌊x⌋ а также xчто противоречие!

Это доказывает результат.

программирование

#include <stdio.h>

int main() {
  unsigned int a = 142857;
  unsigned int b = 65537;
  unsigned int c = 65537;

  printf("a/(b*c) = %d\n", a/(b*c));
  printf("a/b/c = %d\n", a/b/c);
}

печатные издания (с 32-разрядными целыми числами),

a/(b*c) = 1
a/b/c = 0

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

Но если у вас нет переполнения, то значения, которые вы получаете в своей программе, равны их математическим значениям (то есть a/(b*c) в вашем коде равно математическому значению ⌊a/(bc)⌋, а также a/b/c в коде равно математическому значению ⌊⌊a/b⌋/c⌋), которые мы доказали, равны. Так что безопасно заменить a/(b*c) в коде a/b/c когда b*c достаточно мал, чтобы не переполниться.

Answer 2

В то время как b*c может переполниться (в C) для исходного вычисления, a/b/c не может переполниться, поэтому нам не нужно беспокоиться о переполнении для прямой замены a/(b*c) -> a/b/c, Мы должны были бы беспокоиться об этом наоборот.

Позволять x = a/b/c, затем a/b == x*c + y для некоторых y < c, а также a == (x*c + y)*b + z для некоторых z < b,

Таким образом, a == x*b*c + y*b + z, y*b + z самое большее b*c-1, так x*b*c <= a <= (x+1)*b*c, а также a/(b*c) == x,

Таким образом, a/b/c == a/(b*c)и замена a/(b*c) от a/b/c безопасно.

Answer 3

Разделение на вложенные этажи можно изменить, если вы отслеживаете свои делители и дивиденды.

#python3.x
x // m // n = x // (m * n)

#python2.x
x / m / n = x / (m * n)

Доказательство (отстой без LaTeX:() в python3.x:

Let k = x // m
then k - 1 < x / m <= k
and (k - 1) / n < x / (m * n) <= k / n

In addition, (x // m) // n = k // n
and because x // m <= x / m and (x // m) // n <= (x / m) // n
k // n <= x // (m * n)

Now, if k // n < x // (m * n)
then k / n < x / (m * n)
and this contradicts the above statement that x / (m * n) <= k / n

so if k // n <= x // (m * n) and k // n !< x // (m * n)
then k // n = x // (m * n)

and (x // m) // n = x // (m * n)

https://en.wikipedia.org/wiki/Floor_and_ceiling_functions