Вычитание функционально полное

Если конкретнее, то функционально полно вычитание с плавающей точкой по IEEE-754 . Это значит, что можно создать любую двоичную схему на одном только вычитании с плавающей запятой.

Чтобы понять, как это сделать, нужно начать снизу. Цитата из раздела 6.3 стандарта IEEE 754-2019:

6.3 Бит знака

[…] Когда ни входные данные, ни результат не являются NaN, […]; знак суммы или разности x−y, рассматриваемой как сумма x+(−y), знаком отличается максимум от одного из слагаемых; […]. Эти правила должны применяться, даже когда операнды или результаты равны нулю или бесконечности.

Когда сумма двух операндов с противоположными знаками (или разность двух операндов с одинаковыми знаками) равна нулю, знак этой суммы (или разности) должен быть +0 при всех атрибутах направления округления, за исключением roundTowardNegative; при этом атрибуте знак нулевой суммы (или разности) должен быть −0.

Давайте разберём это.

1. Вычитание x−y рассматривается как сумма x+(−y).

2. Ноль может иметь знак, −0 и 0 — это разные сущности (хотя при сравнении с помощью == они считаются равными).

3. Если оба слагаемых имеют одинаковый знак, то результат должен иметь этот знак. Однако для x−y это означает, что если x и y имеют разные знаки, результат должен иметь знак x.

4. Если x и y имеют одинаковый знак, а x−y равно нулю, то результатом будет +0 для всех режимов округления, за исключением roundTowardNegative, при котором он будет −0.

Так как практически в каждом контексте по умолчанию используется режим округления roundTiesToEven, мы будем считать, что применяется он. Однако всё работает аналогично даже для roundTowardNegative.

Таблица истинности

Так что же это даёт нам при вычитании нулей?

-0 - -0 = +0  # Одинаковый знак, должен быть +0. -0 - +0 = -0  # Разные знаки, знак от первого аргумента. +0 - -0 = +0  # Разные знаки, знак от первого аргумента. +0 - +0 = +0  # Одинаковый знак, должен быть +0.

Интересно… А если мы обозначим −0 как false, а +0 как true?

A B | O ----+-- 0 0 | 1 0 1 | 0 1 0 | 1 1 1 | 1

Получившаяся таблица истинности будет эквивалентом A∨¬B, или B→A (также известного как вентиль «импликация» (IMPLY), только с перестановленными аргументами). Оказывается, наша таблица истинности функционально полна, то есть при помощи одного этого вентиля можно создавать произвольные схемы.

Схемы вычитания

Давайте напишем демо на Python. Сначала определим константы и подготовим их красивый вывод:

Хотя это отдельные сущности, по правилам плавающей запятой в IEEE 754 +0 и −0 при сравнении считаются равными. То есть чтобы различать их, нам перед сравнением с 0 нужно извлечь знак.

import math  f_false = -0.0 f_true = 0.0 f_repr = lambda x: True if math.copysign(1, x) > 0 else False

Теперь мы можем создать вентиль NOT, воспользовавшись тем, что −0−x обращает знак нулевого x:

f_not = lambda x: f_false - x

Протестируем это:

>>> f_repr(f_not(f_false)) True >>> f_repr(f_not(f_true)) False

Отлично! Мы также можем создать вентиль OR, обратив внимание, что если мы перед вычитанием обращаем знак второго аргумента, то всегда получаем +0 (true), если только оба аргумента не равны −0 (false):

f_or = lambda a, b: a - f_not(b)

Протестируем это:

>>> f_repr(f_or(f_false, f_false)) False >>> f_repr(f_or(f_true,  f_false)) True >>> f_repr(f_or(f_false, f_true)) True >>> f_repr(f_or(f_true, f_true)) True

Теперь, когда у нас есть OR и NOT, можно изготовить все остальные вентили, например:

f_and = lambda a, b: f_not(f_or(f_not(a), f_not(b))) f_xor = lambda a, b: f_or(f_and(f_not(a), b), f_and(a, f_not(b)))

>>> f_repr(f_and(f_false, f_false)) False >>> f_repr(f_and(f_true,  f_false)) False >>> f_repr(f_and(f_false, f_true)) False >>> f_repr(f_and(f_true, f_true)) True  >>> f_repr(f_xor(f_false, f_false)) False >>> f_repr(f_xor(f_true,  f_false)) True >>> f_repr(f_xor(f_false, f_true)) True >>> f_repr(f_xor(f_true, f_true)) False

Программные целые числа

Возможно, вы слышали о soft-float — программных реализациях плавающей точки при помощи целых чисел. Давайте сделаем наоборот: создадим программную реализацию целых чисел при помощи одних операций с плавающей запятой. Реализуем её на Rust, чтобы можно было взглянуть на готовый ассемблерный код и убедиться в его ужасной тормознутости великолепии.

type Bit = f32; const ZERO: Bit = -0.0; const ONE: Bit = 0.0;  fn not(x: Bit) -> Bit { ZERO - x } fn or(a: Bit, b: Bit) -> Bit { a - not(b) } fn and(a: Bit, b: Bit) -> Bit { not(or(not(a), not(b))) } fn xor(a: Bit, b: Bit) -> Bit { or(and(not(a), b), and(a, not(b))) } fn adder(a: Bit, b: Bit, c: Bit) -> (Bit, Bit) {     let s = xor(xor(a, b), c);     let c = or(and(xor(a, b), c), and(a, b));     (s, c) }  type SoftU8 = [Bit; 8];  pub fn softu8_add(a: SoftU8, b: SoftU8) -> SoftU8 {     let (s0, c) = adder(a[0], b[0], ZERO);     let (s1, c) = adder(a[1], b[1], c);     let (s2, c) = adder(a[2], b[2], c);     let (s3, c) = adder(a[3], b[3], c);     let (s4, c) = adder(a[4], b[4], c);     let (s5, c) = adder(a[5], b[5], c);     let (s6, c) = adder(a[6], b[6], c);     let (s7, _) = adder(a[7], b[7], c);     [s0, s1, s2, s3, s4, s5, s6, s7] }  // Хм? u8? Что это? Тс-с-с-с.... pub fn to_softu8(x: u8) -> SoftU8 {     std::array::from_fn(|i| if (x >> i) & 1 == 1 { ONE } else { ZERO }) }  pub fn from_softu8(x: SoftU8) -> u8 {     (0..8).filter(|i| x[*i].signum() > 0.0).map(|i| 1 << i).sum() }  fn main() {     let a = to_softu8(23);     let b = to_softu8(19);     println!("{}", from_softu8(softu8_add(a, b))); }

Это ужасно, но работает и правильно выводит 42. И для сложения двух 8-битных целых чисел нужно всего ≈120 команд с плавающей запятой:

На x86-64 нет команды отрицания с плавающей запятой, вместо неё компилятор просто генерирует XOR с маской, переключающий старший бит, то есть бит знака числа с плавающей запятой IEEE-754.

example::softu8_add:         mov     rax, rdi         movups  xmm2, xmmword ptr [rsi]         movups  xmm0, xmmword ptr [rdx]         movaps  xmm3, xmm2         subps   xmm3, xmm0         movaps  xmm4, xmm0         subps   xmm4, xmm2         movaps  xmm1, xmmword ptr [rip + .LCPI0_0]         xorps   xmm4, xmm1         subps   xmm4, xmm3         xorps   xmm3, xmm3         subss   xmm3, xmm4         movaps  xmm6, xmm0         xorps   xmm6, xmm1         subss   xmm6, xmm2         xorps   xmm6, xmm1         subss   xmm6, xmm3         movaps  xmm3, xmm4         shufps  xmm3, xmm4, 85         movaps  xmm5, xmm6         subss   xmm5, xmm3         xorps   xmm5, xmm1         movaps  xmm10, xmm6         xorps   xmm10, xmm1         subss   xmm10, xmm3         movaps  xmm7, xmm0         shufps  xmm7, xmm0, 85         xorps   xmm7, xmm1         movaps  xmm3, xmm2         shufps  xmm3, xmm2, 85         subss   xmm7, xmm3         xorps   xmm7, xmm1         movaps  xmm8, xmm4         unpckhpd        xmm8, xmm4         movaps  xmm3, xmm0         unpckhpd        xmm3, xmm0         xorps   xmm3, xmm1         movaps  xmm9, xmm2         unpckhpd        xmm9, xmm2         subss   xmm3, xmm9         xorps   xmm3, xmm1         xorps   xmm11, xmm11         movaps  xmm9, xmm4         shufps  xmm9, xmm4, 255         subss   xmm7, xmm10         movaps  xmm10, xmm7         xorps   xmm10, xmm1         subss   xmm10, xmm8         subss   xmm3, xmm10         unpcklps        xmm7, xmm3         shufps  xmm6, xmm7, 64         addps   xmm11, xmm4         movlhps xmm5, xmm4         subps   xmm4, xmm6         movss   xmm4, xmm11         subps   xmm7, xmm8         xorps   xmm7, xmm1         shufps  xmm5, xmm7, 66         subps   xmm5, xmm4         xorps   xmm3, xmm1         subss   xmm3, xmm9         shufps  xmm0, xmm0, 255         xorps   xmm0, xmm1         shufps  xmm2, xmm2, 255         subss   xmm0, xmm2         xorps   xmm0, xmm1         movups  xmmword ptr [rdi], xmm5         movups  xmm2, xmmword ptr [rdx + 16]         movaps  xmm5, xmm2         xorps   xmm5, xmm1         movups  xmm7, xmmword ptr [rsi + 16]         subss   xmm5, xmm7         xorps   xmm5, xmm1         movaps  xmm4, xmm2         shufps  xmm4, xmm2, 85         xorps   xmm4, xmm1         movaps  xmm6, xmm2         movaps  xmm8, xmm7         movaps  xmm9, xmm7         subps   xmm9, xmm2         subps   xmm2, xmm7         shufps  xmm7, xmm7, 85         subss   xmm4, xmm7         xorps   xmm4, xmm1         movhlps xmm6, xmm6         xorps   xmm6, xmm1         movhlps xmm8, xmm8         subss   xmm6, xmm8         xorps   xmm6, xmm1         xorps   xmm2, xmm1         subps   xmm2, xmm9         subss   xmm0, xmm3         movaps  xmm3, xmm0         xorps   xmm3, xmm1         subss   xmm3, xmm2         subss   xmm5, xmm3         unpcklps        xmm0, xmm5         xorps   xmm5, xmm1         movaps  xmm3, xmm2         shufps  xmm3, xmm2, 85         subss   xmm5, xmm3         subss   xmm4, xmm5         movaps  xmm3, xmm4         xorps   xmm3, xmm1         movaps  xmm5, xmm2         unpckhpd        xmm5, xmm2         subss   xmm3, xmm5         subss   xmm6, xmm3         unpcklps        xmm4, xmm6         movlhps xmm0, xmm4         movaps  xmm3, xmm2         subps   xmm3, xmm0         subps   xmm0, xmm2         xorps   xmm0, xmm1         subps   xmm0, xmm3         movups  xmmword ptr [rdi + 16], xmm0         ret