Если конкретнее, то функционально полно вычитание с плавающей точкой по IEEE-754 . Это значит, что можно создать любую двоичную схему на одном только вычитании с плавающей запятой.
Чтобы понять, как это сделать, нужно начать снизу. Цитата из раздела 6.3 стандарта IEEE 754-2019:
6.3 Бит знака
[…] Когда ни входные данные, ни результат не являются NaN, […]; знак суммы или разности x−y, рассматриваемой как сумма x+(−y), знаком отличается максимум от одного из слагаемых; […]. Эти правила должны применяться, даже когда операнды или результаты равны нулю или бесконечности.
Когда сумма двух операндов с противоположными знаками (или разность двух операндов с одинаковыми знаками) равна нулю, знак этой суммы (или разности) должен быть +0 при всех атрибутах направления округления, за исключением
roundTowardNegative; при этом атрибуте знак нулевой суммы (или разности) должен быть −0.
Давайте разберём это.
Вычитание x−y рассматривается как сумма x+(−y).
Ноль может иметь знак, −0 и 0 — это разные сущности (хотя при сравнении с помощью
==они считаются равными).Если оба слагаемых имеют одинаковый знак, то результат должен иметь этот знак. Однако для x−y это означает, что если x и y имеют разные знаки, результат должен иметь знак x.
Если 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
