Конспект: арифметика без ветвлений и деление на константу

Понятия

Предсказатель переходов - часть процессора, которая угадывает, выполнится ли условный переход, чтобы не ждать. Ошибка стоит 15-20 тактов.

Маска из знака - x >> 31 для 32-битного знакового числа: 0 при x ≥ 0, −1 (все единицы) при x < 0.

Переполнение - настоящий результат не поместился в слово и заменён числом, сравнимым с ним по модулю 2ⁿ.

Целый корень из n - наибольшее r с r² ≤ n.

Что унести

БЕЗ ВЕТВЛЕНИЙ, 32 бита со знаком
маска        m = x >> 31                        0 или −1
модуль       (x ^ m) − m                        −17 → 16 → 17
минимум      b + ((a − b) & m),  m = (a − b) >> 31
максимум     a − ((a − b) & m)
знак         x >> 31 | −x >> 31 & 1             −1, 0, 1
выбор        b ^ ((a ^ b) & m)                  a при m = −1, b при m = 0;  m = −условие

модуль в том же знаковом типе: x ≠ −2³¹
формулы с a − b верны, пока разность не переполняется

данные, 2000 чисел	ошибок двухбитного предсказателя
случайный порядок	1017
те же, отсортированы	3

Маска выигрывает на непредсказуемом условии и там, где время не должно зависеть от данных. На предсказуемом условии ветвление дешевле: вторая ветка не считается. В тренажёре маска дороже - 6002 шага против 5008: он считает строки, а не ошибки предсказателя.

СЛОЖЕНИЕ = СУММА БЕЗ ПЕРЕНОСА + ПЕРЕНОС
a + b = (a ^ b) + ((a & b) << 1)                 повторять, пока перенос не ноль
7 + 1: 4 круга     255 + 1: 9 кругов     170 + 85: 1 круг     случайные 31-битные: 5,34 в среднем

СРЕДНЕЕ БЕЗ СУММЫ
(a & b) + ((a ^ b) >> 1)                         любые знаки, округление вниз
lo + (hi − lo) / 2                               для lo ≤ hi, пока разность помещается
(lo + hi) / 2 в 32 битах при 2 000 000 000 и 2 100 000 000:  −97 483 648

ПРИЗНАК ПЕРЕПОЛНЕНИЯ
знаковое  s = a + b:   (a ^ s) & (b ^ s) < 0     знаки слагаемых одинаковы, у суммы другой
беззнаковое:           s < a
умножение:             признака нет              65536² → 0,  46341² → −2 147 479 015
                       считать в двойной ширине, или  a > наибольшее / b  до умножения

УМНОЖЕНИЕ НА КОНСТАНТУ
x · 10 = (x << 3) + (x << 1)        x · 7 = (x << 3) − x        x · 31 = (x << 5) − x

ДЕЛЕНИЕ НА КОНСТАНТУ d:   x // d = x · M >> s,   M = ⌈2ˢ / d⌉  (вверх!)
d      M              s      ширина x     ошибок на всех 16-битных x
3      43691          17     16           0
3      43690 (вниз)   17     16           21 845, первая на x = 3
3      21846          16     16           10 923, первая на x = 32 768
10     52429          19     16           0
7      74899          19     16           0, но M - 17 битов: «неудобный» делитель
3      0xAAAAAAAB     33     32
10     0xCCCCCCCD     35     32

точное деление, если x кратно 3:   x · 43691 mod 2¹⁶        369 → 123
проверка делимости:                результат > 0xFFFF // 3  →  не делилось
деление знакового на 2ᵏ:           (x + (x >> 31 & (2ᵏ − 1))) >> k        −7 / 2 = −3

ПО БИТУ ЗА КРУГ
умножение   для каждого единичного бита i множителя:  p = p + (a << i)
деление     r = r << 1 | бит;  если r ≥ d:  r = r − d, бит частного 1        100 / 7 = 14 ост. 2
корень      если остаток ≥ r + bit:  остаток −= r + bit,  r = (r >> 1) + bit;  иначе r >>= 1;  bit >>= 2
            bit - степени четвёрки сверху вниз;  180 → 13, остаток 11

4 000 000 000 // 7 сдвигами: 132 шага, 32 круга
корень из 94 906 265² − 1:  по битам 27 кругов,  Ньютоном 6,  через n ** 0.5 - неверно на единицу

В Python: math.isqrt(n) - точный целый корень; hmac.compare_digest - сравнение за постоянное время. В C: __builtin_add_overflow, __builtin_mul_overflow, в C23 - ckd_add, ckd_mul.

Граница слова: умножение при b>0 безопасно, если a ≤ MAX//b; округление вверх требует отдельной проверки результата, а корень - целочисленного контракта.

Ловушки джокера

Разность переполнилась. Минимум через маску из a − b возвращает большее число для 2 000 000 000 и −2 000 000 000.

Сдвиг не той ширины. x >> 31 - маска только для 32 битов и только для знакового числа.

Обмен через ^ одной ячейки с собой. Обнуляет её.

Ранний выход при сравнении секрета. Время ответа сообщает, сколько байтов совпало.

(lo + hi) / 2. Девять лет ошибки в двоичном поиске стандартной библиотеки Java.

Проверка после переполнения в C. if (a + b < a) для знаковых компилятор вправе заменить на b < 0.

Размер как произведение. n * k переполнилось - выделено мало, записано много.

Множитель округлён вниз. Деление на 3 ломается на каждом числе, кратном трём.

Младшая половина произведения. Для деления на константу нужна старшая; в 32-битном произведении её нет.

Квадрат кандидата. (r + b)² переполняется, когда n ещё помещается. Сравнивать через остаток или делением: r <= n // r.

Корень через дробные. int(n ** 0.5) точен до 2⁵², дальше ошибается у полных квадратов.

Самодельное деление на ноль. Цикл не падает, а возвращает частное из одних единиц.

Куда это ведёт

До сих пор биты были средством: ими ускоряли то, что можно сделать и без них. В последней главе раздела они - сама задача. Код Грея - нумерация, в которой соседние числа отличаются одним битом. CRC - контрольная сумма, построенная на делении, в котором вместо вычитания стоит ^. И дробное число, которое до сих пор было чёрным ящиком с погрешностью, раскрывается как три битовых поля.

Понятия

Что унести

Ловушки джокера

Куда это ведёт

Комментарии

Оставить комментарий