arithmetic 设计

设计目标

线性代数算法除了环运算符之外还需要少量标量运算：选主元用的绝对值、范数用的平方根、排序用的比较，以及比较浮点结果的方法。arithmetic 包为线性代数代码命名了这些运算，但不声称标量类型满足它们实际上并不满足的定律。凡上游已有的词汇它都复用，只在没有时才新增 trait。

数学背景

运算与结构

像 Field 这样的结构 trait 承诺的是等式：结合律、分配律、逆元。像 Sqrt 这样的运算 trait 只承诺存在一个函数 $\sqrt{\cdot} : T \to T$ 。这一区分很重要，因为内置浮点类型实现了这些运算，却只近似地满足那些等式：对 Double，

\mathrm{fl}\big(\mathrm{fl}(2^{53} + 1) - 2^{53}\big) = 0 \ne 1 = \mathrm{fl}\big(2^{53} - 2^{53}\big) + 1 ,

因此一般而言 $(a + b) - c \ne (a - c) + b$ 。本包的每个 trait 都是运算 trait。

部分运算及其全函数化

除法和平方根是实数上的部分函数： $x / y$ 定义在 $\{(x, y) : y \ne 0\}$ 上， $\sqrt{x}$ 定义在 $\{x \ge 0\}$ 上。IEEE 754 通过返回特殊值（ $\pm\infty$ 、NaN）使它们成为全函数，这些值随后会静默传播。受检运算则把部分函数 $f : D \rightharpoonup C$ 全函数化为

\hat f : X \to C + E, \qquad \hat f(x) = \begin{cases} \mathrm{Ok}\,(f(x)) & x \in D, \\ \mathrm{Err}\,(e(x)) & x \notin D, \end{cases}

其中 $E$ 是错误值集合， $e(x)$ 说明 $x$ 为何落在定义域之外。CheckedDiv 对浮点操作数采用如下定义域划分：

区域	IEEE 结果	受检结果
$y \ne 0$ ，且不同时为无穷	$\mathrm{fl}(x / y)$	同一值的 `Ok`
$x = y = 0$	NaN	`DomainError`
$x, y$ 均为无穷	NaN	`DomainError`
$x \ne 0$ , $y = 0$	$\pm\infty$	`DivisionByZero`

含 NaN 时的排序

Double 上的 Compare 不是全序：NaN 既不小于、不等于、也不大于任何值，因此对含 NaN 的数据排序或选主元，结果会依赖于顺序。CheckedCompare 把比较限制在有序子集上，在其之外报告 UnorderedComparison，从而使结果在其定义域上是全序。

近似相等

ApproxEq 使用绝对规则 $a \approx b \iff |a - b| \le \varepsilon$ 。该关系是自反和对称的，但不是传递的。由 $|a - b| \le \varepsilon$ 和 $|b - c| \le \varepsilon$ ，三角不等式只能给出

|a - c| \le |a - b| + |b - c| \le 2\varepsilon ,

而且该界是可以取到的：取 $a = 0$ 、 $b = \varepsilon$ 、 $c = 2\varepsilon$ ，有 $a \approx b$ 、 $b \approx c$ 而 $a \not\approx c$ 。因此 approx_eq 不是等价关系，本包也不把它当作等价关系。

绝对容差也不具有尺度不变性。浮点数的间距随数值大小增长： $x$ 附近相邻 Double 值之间的间距约为 $2^{-52}|x|$ 。在 $10^{20}$ 附近，该间距约为 $1.6 \times 10^{4}$ ，因此两个不同的值永远不可能相差 $10^{-12}$ 以内；而在 $10^{-20}$ 附近，任意两个值都满足。相对规则 $|a - b| \le \varepsilon \max(|a|, |b|)$ 解决了尺度问题，但在零附近失效，因此严谨的代码会把两者结合；本包把这一选择留给调用者。

设计决策

复用上游名称

Luna-Flow/arithmetic 中的标量 trait Zero、One、Inverse、Conjugate 以及分析类 trait 通过 pub using 重新导出，而不是重新定义。本地副本会造成第二个互不兼容的 Sqrt，实现了上游 trait 的标量类型将无法满足本地的 trait。使用 pub using 后，@la_arithmetic.Sqrt 就是 @lf_arith.Sqrt。

小型本地 trait

Abs、ApproxEq、CheckedDiv、CheckedSqrt 和 CheckedCompare 之所以存在，是因为线性代数代码需要这些名称，而上游包当时没有以这种形式提供。每个 trait 只有一个方法，因此标量类型可以只选择它所支持的运算。对 Float 和 Double，受检 trait 委托给上游的受检 trait，因此两层在每个输入上都一致。

二进制浮点数接受但忽略上下文

checked_div 和 checked_sqrt 接受一个 ArithmeticContext，使同一签名既适用于固定精度标量类型，也适用于任意精度标量类型。对 Float 和 Double，精度由硬件格式固定，舍入方式为就近舍入到偶数，因此上下文不起作用。

固定的绝对容差

ApproxEq 对 Double 使用 $10^{-12}$ ，对 Float 使用 $10^{-6}$ 。以各格式的单位舍入误差 $u$ （ $2^{-53}$ 和 $2^{-24}$ ）计，它们分别约为 $9000u$ 和 $17u$ ，因此适用于量级为一的值，例如归一化向量的元素。对于其他量级，请在自己的代码中用显式容差进行比较。

正确性与不变量

对 Float 和 Double，checked_div(x, y, ctx) 返回 Ok(v)，当且仅当 IEEE 除法返回的值不是由无效运算或除零异常产生的，此时 v 与 IEEE 商逐位相等。
checked_sqrt(x, ctx) 对 $x \ge 0$ 和 NaN 返回 Ok(√x)，对 $x < 0$ 返回 Err。注意 $-0.0 \ge 0$ 成立，因此 checked_sqrt(-0.0) 为 Ok(-0.0)。
checked_compare 在其定义域上是反对称的：checked_compare(a, b) == Ok(k) 蕴含 checked_compare(b, a) == Ok(-k)。
approx_eq 对非 NaN 值是自反和对称的，对 NaN 则为 false。

被否决的方案

组合所有运算的本地 Real 或 Number trait。 它会掩盖算法实际使用了哪些运算，并迫使特殊的标量类型实现全部运算。
让 approx_eq 成为 Eq 的一部分。 Eq 必须是等价关系；近似相等不满足传递性。
在 ApproxEq 中使用相对容差。 它在零附近需要一种依赖于应用场景的策略；因此该 trait 保持简单，并在文档中说明。

边界

arithmetic 不定义向量、矩阵或后端类型，也不依赖本仓库的其他包。它不定义代数结构 trait（来自 luna-generic），不为矩阵算法选择容差（那是 mutable 的 Tolerance trait），也不实现任意精度算术。