Целочисленное деление всегда равно полу регулярного деления?

Ответ 1

Причина, по которой коэффициенты в вашем тестовом примере не равны, заключается в том, что в случае math.floor(a/b) результат рассчитывается с помощью арифметики с плавающей запятой (64-битная IEEE-754), что означает максимальную точность. Коэффициент, который у вас есть, больше, чем предел 2 ⁵³, выше которого плавающая точка больше не точна до единицы.

Однако с помощью целочисленного деления Python использует неограниченный диапазон целых чисел, поэтому результат верен.

См. также "Семантика истинного разделения" в PEP 238:

Обратите внимание, что для аргументов int и long истинное деление может потерять информацию; это в природе истинного разделения (пока рациональное не в языке). Алгоритмы, которые сознательно используют длинные, должны учитывать использование //, поскольку истинное разделение длин сохраняет не более 53 бит точности (на большинстве платформ).

Ответ 2

Вы можете иметь дело с целочисленными значениями, которые слишком велики для того, чтобы выражать их в точности как числа с плавающей точкой. Ваше число значительно больше, чем 2 ^ 53, в котором промежутки между соседними числами с плавающей запятой начинают становиться больше 1. Таким образом, вы теряете некоторую точность при выполнении деления с плавающей запятой.

Целочисленное деление, с другой стороны, вычисляется точно.

Ответ 3

Ваша проблема в том, что, несмотря на то, что "/" иногда называют "оператором истинного деления" и его именем метода является __truediv__, его поведение с целыми числами не является "истинным математическим делением". Вместо этого он выдает результат с плавающей запятой, который неизбежно имеет ограниченную точность.

Для достаточно больших чисел даже неотъемлемая часть числа может страдать от ошибок округления с плавающей запятой. Когда 648705536316023400 преобразуется в число с плавающей точкой Python (IEEE double), оно округляется до 648705536316023424 ¹.

Кажется, я не могу найти авторитетную документацию о точном поведении операторов встроенных типов в текущем Python. Исходный PEP, который представил функцию, утверждает, что "/" эквивалентно преобразованию целых чисел в число с плавающей запятой и затем выполнению деления с плавающей запятой. Однако быстрый тест в Python 3.5 показывает, что это не так. Если бы это было так, следующий код не дал бы результата.

for i in range(648705536316023400,648705536316123400):
    if math.floor(i/7) != math.floor(float(i)/7):
        print(i)

Но, по крайней мере, для меня это действительно результат.

Вместо этого мне кажется, что Python выполняет деление по представленным числам и округляет результат, чтобы уместить его в число с плавающей запятой. Возьмем пример из вывода этих программ.

648705536316123383 // 7                   == 92672219473731911
math.floor(648705536316123383 / 7)        == 92672219473731904
math.floor(float(648705536316123383) / 7) == 92672219473731920
int(float(92672219473731911))             == 92672219473731904

Стандартная библиотека Python предоставляет тип дроби, а оператор деления для дроби, деленной на int, выполняет "истинное математическое деление".

math.floor(Fraction(648705536316023400) / 7) == 92672219473717628
math.floor(Fraction(648705536316123383) / 7) == 92672219473731911

Однако вы должны знать о потенциально серьезных последствиях для производительности и памяти при использовании типа дроби. Помните, что фракции могут увеличиваться в требованиях к хранению без увеличения величины.

Чтобы дополнительно проверить мою теорию "одно округление против двух", я провел тест со следующим кодом.

#!/usr/bin/python3
from fractions import Fraction
edt = 0
eft = 0
base = 1000000000010000000000
top = base + 1000000
for i in range(base,top):
    ex = (Fraction(i)/7)
    di = (i/7)
    fl = (float(i)/7)
    ed = abs(ex-Fraction(di))
    ef = abs(ex-Fraction(fl))
    edt += ed
    eft += ef
print(edt/10000000000)
print(eft/10000000000)

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

¹ Обратите внимание, что прямая печать числа с плавающей запятой не показывает его точное значение, вместо этого оно показывает самое короткое десятичное число, которое округляется до этого значения (позволяя преобразование туда и обратно без потерь из числа с плавающей точкой в строку и обратно в число с плавающей точкой).

Ответ 4

Под "математическим делением" документы Python означают точное деление на действительные числа.

Теперь, возвращаясь к вашему вопросу о целочисленном делении (также известном как евклидово деление) по отношению к полу деления с плавающей запятой (лучше, чем "обычное деление"), я изучил эту проблему в 2005 году. Я доказал, что для округления до ближайшего в основание 2, если x − y точно представимо, то пол деления с плавающей точкой x/y, то есть math.floor(x/y), равен целочисленному делению. Вы можете получить статью на моем веб-сайте или в HAL.