Границы слова: умножение, округление и целый корень

Если проверяешь диапазон до умножения и обрабатываешь ноль при округлении, листай до «Теперь сам».

Как думаешь, помещается ли результат, если помещаются аргументы

Восьмибитное беззнаковое слово хранит числа от нуля до 255. Числа 17 и 16 допустимы каждое, но произведение 272 уже не помещается. А округление 129 вверх до степени двойки требует 256. Вычисление математически корректно; ошибка возникает при попытке уложить его результат в заранее выбранный тип.

Уже знакомые уроки показали переполнение сложения и сборку корня из сдвигов. Здесь не будем повторять алгоритм задания про корень. Сравним контракты операций и проверим их на всём маленьком диапазоне, где независимый перебор позволяет заметить граничный дефект.

На что это похоже

Представь ящик на 255 деталей. Две партии по 200 деталей по отдельности допустимы, вместе нет. Проверять только накладные на партии недостаточно: нужен контракт всей операции. А округление заказа до коробки стандартного размера может превратить заказ на 129 деталей в коробку вместимостью 256, для которой на складе нет места.

Механизм: сравнение вместо опасного результата

Для сложения неотрицательных целых безопасно проверять a ≤ MAX - b. Правая часть лежит в диапазоне типа, если оба аргумента уже проверены. Для умножения при ненулевом b делим предел на b. Если a больше частного, произведение не поместится. Нулевой множитель обрабатывается отдельно: деление на ноль в проверке было бы новым дефектом.

В Python целые расширяются, поэтому код ниже моделирует диапазон явно. Это не доказательство поведения переполненного знакового выражения в C: там само вычисление за границей диапазона не даёт переносимой основы для последующей проверки. Модель и язык реализации должны совпадать.

Степень двойки вниз определяется положением старшей единицы. Для положительного x это 1 << (bit_length(x)-1). Вверх можно посмотреть длину x-1: у точной степени двойки длина на единицу меньше, поэтому она сохраняется. У нуля математического положительного предшественника нет: выберем явный контракт - вниз ноль, вверх единица. Это выбранный здесь интерфейс: у Уоррена в §3.2 обе функции на нуле возвращают ноль. Математическая задача при положительном входе от выбора этого граничного значения не меняется.

Правило

Сначала проверь аргументы и достаточность диапазона, затем вычисляй. Для округления вверх отдельно проверь представимость результата. Корень сравнивай по целочисленному контракту, а не по округлённому float. Выбор поведения для нуля - часть интерфейса, его нельзя оставлять случайному сдвигу.

Разбор: исчерпывающая проверка на восьми битах

from math import isqrt

MAX = 255


def mul_checked(a, b):
    assert 0 <= a <= MAX and 0 <= b <= MAX
    if b and a > MAX // b:
        return None
    return a * b


def down(x):
    return 0 if x == 0 else 1 << (x.bit_length() - 1)


def up(x):
    result = 1 if x == 0 else 1 << (x - 1).bit_length()
    return result if result <= MAX else None


def root_contract(n, r):
    if not (0 <= n <= MAX and 0 <= r <= MAX):
        return False
    if r and r > n // r:
        return False
    # При r == MAX следующий кандидат не представим в слове.
    return r == MAX or r + 1 > n // (r + 1)


for a in range(MAX + 1):
    for b in range(MAX + 1):
        exact = a * b
        expected = exact if exact <= MAX else None
        assert mul_checked(a, b) == expected
for n in range(MAX + 1):
    for r in range(MAX + 1):
        assert root_contract(n, r) == (r == isqrt(n))
    powers = [1 << bit for bit in range(8)]
    expected_down = max([0] + [p for p in powers if p <= n])
    expected_up = next((p for p in powers if p >= n), None)
    assert down(n) == expected_down
    assert up(n) == expected_up
print("Все пары умножения:", (MAX + 1) ** 2)
for x in (0, 1, 128, 129, 255):
    print(x, down(x), up(x), isqrt(x))
print("15 * 17:", mul_checked(15, 17))
print("16 * 16:", mul_checked(16, 16))

Все пары умножения: 65536
0 0 1 0
1 1 1 1
128 128 128 11
129 128 None 11
255 128 None 15
15 * 17: 255
16 * 16: None

В тесте умножения Python вычисляет точное произведение, поэтому выступает независимым эталоном для модели узкого слова. Рабочая функция не вычисляет потенциально переполненный результат до проверки. Для больших слов такой полный перебор уже невозможен, но граничные пары вокруг MAX // b остаются полезными тестами.

Разбор: корень и последний допустимый кандидат

При n = 255 целый корень равен 15: 15² = 225, а 16² = 256 уже велик. Если проверяющая программа вычисляет второй квадрат в восьми битах, он превращается в ноль и может пропустить ошибку. Сравнение кандидата с n // candidate не переполняется; кандидат ноль обрабатывается отдельно. Сначала отвергаем слишком большой r, а при r = MAX не вычисляем r+1 в узком слове: следующий кандидат уже за его пределами. Проверка всех пар (n, r) ловит и принятие неверного корня, а не только отказ на правильном.

Округление 128 вверх сохраняет 128, 129 требует 256 и потому отвергается нашим контрактом. Округление вниз остаётся допустимым и для 255. Следовательно две функции округления имеют разные множества успешных входов, хотя обе получают тот же беззнаковый тип.

Что ломается без этого

Проверка a*b // b == a после умножения опоздала для языка, где переполнение знакового умножения не определено. Другая ошибка - считать ноль степенью двойки по формуле x & (x-1) == 0: нужно также условие x > 0. И ещё одна - надеяться, что больший тип результата автоматически расширил уже выполненное узкое умножение: расширять нужно операнды до действия.

Зачем это в работе

Программа получает размеры изображения и выделяет память на width*height*channels. Каждый множитель прошёл проверку типа, но произведение может переполниться и привести к слишком маленькому буферу. Цепочка проверенных умножений обеспечивает соответствие выделенного размера исходным параметрам. Округление размера таблицы до степени двойки требует такой же проверки конечного результата.

Теперь сам

Для диапазона [0,255] проверь пары (15,17) и (16,16). Чему равен целый корень 255 и что вернёт округление 255 вверх?