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

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

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

29.09.2023 13:39

PatientZero 7 2600 Источник

Если конкретнее, то функционально полно вычитание с плавающей точкой по 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

Комментарии (7)

INSTE
29.09.2023 14:08
#26012318
+8
Не "вентиль IMPLY", а "импликация". Есть же устоявшийся термин, который широко используется в литературе.
1. PatientZero Автор
  29.09.2023 14:08
  #26013618
  Спасибо

nitrosbase
29.09.2023 14:08
#26012994
+7
Оказывается, наша таблица истинности функционально полна, то есть при помощи одного этого вентиля можно создавать произвольные схемы.

Это неверно. Множество булевых функций, состоящее из одной только (обратной) импликации, не является функционально полным. Критерий Поста не позволяет. В множестве нет функции, не принадлежащей предполному замкнутому классу функций, сохраняющих единицу.

Не принадлежит этому классу одна из двух функций, которые автор на самом деле дополнительно использует:

Сначала определим константы...

Вместе с константой 0 импликация образует функционально полное множество булевых функций, да.

16tomatotonns
29.09.2023 14:08
#26013188
Пока выглядит как максимально объёмная обфускация кода на произвольном языке с поддержкой плавающей запятой. Полагаю, можно использовать в местах где скорость не важна, но важен результат сокрытия информации.
[][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+[]+!+[]+!+[]]+(!![]+[])[+!+[]]][([][(![]+[])[+[]]+([![]]+[][[]])[+!+[]+[+[]]]+(![]+[])[!+[]+!+[]]+(!![]+[])[+[]]+(!![]+[])[!+

redfox0

29.09.2023 14:08

#26015016

Чуть более многословно:

#[derive(Clone, Copy)]
pub struct Bit(f32);

impl std::ops::Not for Bit {
    type Output = Self;

    fn not(self) -> Self::Output {
        Self(Self::ZERO.0 - self.0)
    }
}

impl std::ops::BitOr for Bit {
    type Output = Self;

    fn bitor(self, rhs: Self) -> Self::Output {
        Self(self.0 - (!rhs).0)
    }
}

impl std::ops::BitAnd for Bit {
    type Output = Self;

    fn bitand(self, rhs: Self) -> Self::Output {
        !(!self | !rhs)
    }
}

impl std::ops::BitXor for Bit {
    type Output = Self;

    fn bitxor(self, rhs: Self) -> Self::Output {
        (!self & rhs) | (self & !rhs)
    }
}

impl Bit {
    pub const ZERO: Self = Self(-0.0);
    pub const ONE: Self = Self(0.0);

    pub fn adder(a: Self, b: Self, c: Self) -> (Self, Self) {
        let s = a ^ b ^ c;
        let c = ((a ^ b) & c) | (a & b);
        (s, c)
    }
}


pub struct SoftU8 {
    inner: [Bit; 8],
}

impl std::ops::Add for SoftU8 {
    type Output = Self;

    fn add(self, rhs: Self) -> Self::Output {
        let (s0, c) = Bit::adder(self.inner[0], rhs.inner[0], Bit::ZERO);
        let (s1, c) = Bit::adder(self.inner[1], rhs.inner[1], c);
        let (s2, c) = Bit::adder(self.inner[2], rhs.inner[2], c);
        let (s3, c) = Bit::adder(self.inner[3], rhs.inner[3], c);
        let (s4, c) = Bit::adder(self.inner[4], rhs.inner[4], c);
        let (s5, c) = Bit::adder(self.inner[5], rhs.inner[5], c);
        let (s6, c) = Bit::adder(self.inner[6], rhs.inner[6], c);
        let (s7, _) = Bit::adder(self.inner[7], rhs.inner[7], c);
        Self {
            inner: [s0, s1, s2, s3, s4, s5, s6, s7],
        }
    }
}

impl Into<SoftU8> for u8 {
    fn into(self) -> SoftU8 {
        SoftU8 {
            inner: std::array::from_fn(|i| if (self >> i) & 1 == 1 { Bit::ONE } else { Bit::ZERO }),
        }
    }
}

impl Into<u8> for SoftU8 {
    fn into(self) -> u8 {
        (0..8).filter(|i| self.inner[*i].0.signum() > 0.0).map(|i| 1 << i).sum()
    }
}

fn main() {
    let a: SoftU8 = 23.into();
    let b: SoftU8 = 19.into();
    let c = a + b;
    let c: u8 = c.into();
    println!("{}", c);
}

funny_falcon
29.09.2023 14:08
#26018810
Как минимум and можно выразить эффективнее:
```
f_and = lambda a, b: f_not(f_not(a)-b)
```
1. funny_falcon
  29.09.2023 14:08
  #26018822
  Соответственно:
  
  f_xor = lambda a,b: f_or(f_not(a-b), f_not(b-a))

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

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

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

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

Комментарии (7)

INSTE

PatientZero Автор

nitrosbase

16tomatotonns

redfox0

funny_falcon

funny_falcon