加法、减法和除法

到目前为止,我们一直专注于乘法运算。然而,为了能够执行通用计算,真实环境下的程序还需要加法、除法和减法。

加法: 在上一节中,我们已经确定可以在单个操作数的情况下添加变量,然后将其乘以另一个操作数,例如 \(\color{ForestGreen}{(3a + b)} \times \color{blue}{d} = \color{red}{r}\),但是如果我们只需要加法而不需要乘法,例如,如果一个程序需要计算 \(\mathrm{a} + \mathrm{b}\),我们可以将其表示为:

$$\color{ForestGreen}{(a + b)}\quad \times \quad\color{blue}{1}\quad = \quad\color{red}{r}$$

注:由于我们的结构对每个操作数都需要一个常数系数和一个变量(\(\color{blue}{c \cdot v}\)),所以 \(\color{blue}{1}\) 的值被表示为 \(c_{one} \cdot v_{one}\),虽然 \(c_{one} = 1\) 可以被「硬编码」到对应的多项式中,但 \(v_{one}\) 是一个变量,可以被赋任何值,因此我们必须通过 4.10 节中解释的约束来限制 \(v_{one}\) 的值。

减法: 减法几乎与加法相同,唯一的区别是一个负系数,例如,对于 \(\mathrm{a - b}\):

$$\color{ForestGreen}{(a + -1 \cdot b)}\quad \times \quad\color{blue}{1}\quad = \quad\color{red}{r}$$

除法: 如果我们观察除法运算 \(\mathsf{\frac{因子}{除数} = 结果}\),可以发现将除法的 \(\mathsf{结果}\) 乘以 \(\mathsf{除数}\) 就能得到 \(\mathsf{因子}\)。因此我们可以用乘法表达相同的含义:\(\mathsf{除数 \times 结果 = 因子}\)。如果我们要证明除法运算 \(\mathrm{\frac{a}{b} = r}\),可以将其表示为:

$$\color{ForestGreen}{b}\quad \times \quad\color{blue}{r}\quad = \quad\color{red}{a}$$

注:运算的结构也被称为「约束(Constraint)」,由多项式结构表示的运算本身并非是为了计算结果,而是检查证明者是否已经知道变量(包括结果),并且它们对运算来说是有效的,也就是说,无论这些值是什么,证明者都必须提供一致的值。

注:所有这些算术运算都已经存在,因此不再需要修改运算的结构。

译者注:约束和运算有一定的关联性。算术电路的目的是实现计算的验证,而非计算的过程

上文中,我们提出了一种方法:把构造多项式的工作交给设置环节,证明者只需要填上对应的数值就可以了。这个方法不仅解决了同一个操作数的运算符不一致的问题,同时还带来了额外的便利:

  1. 允许执行计算的表达式中包含静态系数。

  2. 虽然 \(l(x) \times r(x) = o(x)\) 的关系中只有乘法,但利用这个方法也能轻松地执行加法运算,同时也解决了减法和除法的问题。