计算机系统中的代数结构(整型)

在学习CMU的课程15-213时,看到了如下的描述:

Integer operations satisfy "ring" properties

Floating point operations satisfy "ordering" properties

对这两个描述我实际上并没有太理解:因为没有学过代数结构的相关知识。但隐约能感觉出来这里讲的是计算机系统中的代数结构。于是翻出自己尘封的《离散数学》一书,开始补习代数结构。(所以这两篇文章一定不会很深刻...毕竟只用到了离散中的极为粗略的代数结构。两篇文章更大意义上还是写给自己的科普文。)

本文就将从代数结构的角度,来解释计算机系统中的整型与浮点型。

上图给出了本文的主要内容,其次还将介绍同构、阿贝尔群等具体概念。

代数系统

定义

非空集合 \(S\)\(S\) 上的 \(k\) 个运算 \(f_1,f_2,...,f_k\) 组成的 \(<S,f_1,f_2,...,f_k>\) 就称作一个代数系统。

这里需要对 二元运算 进行定义:

\[S \times S \xrightarrow{f} S\]

其中映射 \(f\) 就被称作集合 \(S\) 上的一个二元运算。

比如整数集和其上的加法就构成了一个简单的代数系统: \(<\mathcal{Z},+>\)

如果这个二元运算满足如下条件,则称它具有对应的性质:

  • 封闭性:\(\forall x,y \in S,x \times y = z \Rightarrow z \in S\)
  • 交换律:\(\forall x,y \in S,x \times y = y \times x\)
  • 结合律:\(\forall x,y \in S,x \times (y \times z) = (x \times y) \times z\)

下面还有注入零元、幺元、逆元以及群环等概念的定义,本文将与整型和浮点型的特性一同介绍。

整型上的代数结构

在课程 15-213 的PPT里写道:

无符号整型集合和模加运算构成了一个阿贝尔群。

上图给出了阿贝尔群定义的步骤,下面具体进行具体解释。

阿贝尔群

所以,这里我们首先来了解 的概念。

我们先假设一个代数系统 \(V=<S,\circ>\)。如果 \(\circ\)可结合的,则称 \(V\) 是一个 半群

可结合\(\forall x,y \in S,x \circ (y \circ z) = (x \circ y) \circ z\)

如果这个 半群 含有 幺元,则称它为幺半群(monoid)。

幺元e\(\forall x \in S, x \circ e = e \circ x = x\)

比如线性代数里的单元矩阵、实数域上的1都是幺元。 是的,这里的幺半群就是那个著名的哏中提到的那个幺半群....

Monad 不就是自函子上的幺半群吗,有什么难以理解的?

言归正传,如果这个 幺半群 中的所有元素都有逆元,则称这是一个

\(\forall x \in S,x + x^{-1} = 0\),则称 \(x^{-1}\)\(x\) 的逆。

比如线性代数里矩阵的逆,实数域里的相反数。这都是我们熟悉的逆。 需要注意的是,与 幺元零元 不同,是对于特定元素的逆,而幺元和零元是对于代数系统的特殊元素。

如果这个群的二元运算 \(\circ\) 是可交换的,则称它为一个 阿贝尔群

可交换\(\forall u,v \in S,u \circ v = v \circ u\)

到此为止,我们终于把一个阿贝尔群的定义给搞清楚了。我们对计算机系统中的代数结构已经建立起了一个不错的认知!

无符号整型与模加构成阿贝尔群

我们稍微总结一下上面的定义,发现这些定义既界定了什么叫阿贝尔群,也确定了阿贝尔群的性质。 性质有如下几条:

  • 封闭性:\(0 \leq u +_{u} v \leq 2^w -1\)
  • 交换律:\(u +_{u} v = v +_{u} + u\)
  • 结合律:\(t +_{u} (u +_{u} v) = (t +_{u} u) +_{u} v\)
  • 零元:\(u +_{u} 0 = u\)
  • 逆元:\(u^{-1}=2^w-u\)

我们这里给出了无符号整型与模加(mod)构成的阿贝尔群的基本性质的具体含义。其中,\(w\)指代机器字长(32bit、64bit),\(+_{u}\) 代表无符号模加运算。

可以看出,这里的五大性质还是非常符合我们通常对整型的理解的。除了逆元的含义稍有不同。

无符号整型与补码上的模加与乘是同构环

同构与同态

在图论中,我们说两张图同构是说能找到一个双射使得两张图的点集和边集可以分别一一对应。这里的同构与图的同构类似,标准的定义需要先介绍同态。

定义

\(V_1=<S_1,\circ>,V_2=<S_2,\times>\) ,若存在映射 \(\varphi:S_1 \rightarrow\) 满足 \(\forall x,y \in S\) 都有 \[ \varphi (x \circ y) = \varphi (x) \times \varphi(y) \]

则称 \(\varphi\)\(V_1\)\(V_2\) 的同态映射。

\(\varphi\) 是一个双射(单满射)时,\(\varphi\) 就是一个同构映射。

同构环

在上面,我们介绍了阿贝尔群的概念,这里就将基于阿贝尔群的定义来定义环。需要注意的是,诸多概念的名字主要是为了更好地界定不同代数结构的性质,虽然名目繁多,但其本质上并不复杂。

环的定义

\(V=<R,+,\circ>\),其中\(<R,+>\)为阿贝尔群、\(<R,\circ>\)为半群、\(\circ\)\(+\)满足分配律,则称代数结构\(V\)是一个环。

比如: \[ x + y = (x + y) \mod n \\ x \circ y = (x \circ y) \mod n \]

可以看到,无符号数就是这样的一个模加系统,自然也是环。

并且满足交换律(\(u\circ v=v\circ u\))我们称它为交换环。

无符号与补码的同构映射

在《CSAPP》一书中,给出了两者之间的映射关系。 因为无符号数与补码是同构的,所以自然补码也满足无符号数的各项性质。

整型中的代数结构总结

我们在无符号数(unsigned)和补码上定义运算\(+\)和运算\(\times\)。不妨分别称为 \(V_1=<Z,+,\times>,V_2=<Z,+,\times>\)

对于\(V_1\)的子代数\(<Z,+>\),它满足阿贝尔群的几个性质。\(V_2\)的子代数\(<Z,+>\)也满足。这符号我们在自然世界中对数及其运算的期望。

对于代数结构\(V_1,V_2\),我们发现他们还满足交换环的几个性质。不过需要注意的是在无符号数中一个数的逆元并非为\(u^{-1}=-u\),而是\(u^{-1}=2^w-u\),其中原因,留给读者思考~

其次,在计算机的代数结构中,因为状态空间有限(机器字长决定了能表示的数的个数),我们定义了模运算。

至此,我们就很好地解释了在“引”部分中的第一句话。

Integer operations satisfy "ring" properties

下一篇文章将介绍浮点数中的代数结构。

计算机系统中的代数结构(浮点型) 我所推荐的计算机在线课程与书籍

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×