前言
本文讨论定点数算术运算的算法与实现。
定点数
设实数 $V_{real}$ 的整数数表示形式 $Q_{n}$。
$$ V = Q_n \cdot 2^{-n} $$
其中，$n$ 表示小数部分的比特数或者说定点数的精度。
加减法运算
设
$$ V_S = V_A + V_B \\ V_A = A_{n} \cdot 2^{-n} \\ V_B = B_{n} \cdot 2^{-n} $$
即，$A_{n}$ 是 $V_{A}$ 的整数形式，$A_n$ 和 $B_n$ 有相同的精度，小数点位置已经对齐。
$$ \begin{aligned} V_S &= V_A + V_B \\ &= A_{n} \cdot 2^{-n} + B_{n} \cdot 2^{-n} \\ &= (A_{n} + B_{n}) \cdot 2^{-n} \end{aligned} $$
也就是说，两个实数之和，可以表示为它们的整数形式之和转回实数形式。
对于减法可以视作 $V_S = V_A + (-V_B)$ ，推导过程相同。
因为我们需要的和是定点数，所以将 $V_S$ 也替换为定点数形式：
$$ \begin{aligned} V_S &= (A_{n} + B_{n}) \cdot 2^{-n} \\ S_n \cdot 2^{-n} &= (A_{n} + B_{n}) \cdot 2^{-n} \\ S_n &= (A_{n} + B_{n}) \cdot 2^{-n} \cdot 2^n \\ S_n &= A_{n} + B_{n} \end{aligned} $$
代码实现如下
type Fix32 int32 // fixed-point number in Q15.16 format
func Add(a, b Fix32) (Fix32, error) {
intermediate := int64(a) + int64(b)
if intermediate > math.MaxInt32 {
return 0, ErrOverflow
} else if intermediate < math.MinInt32 {
return 0, ErrUnderflow
}
return Fix32(intermediate), nil
}
func Sub(a, b Fix32) (Fix32, error) {
intermediate := int64(a) - int64(b)
if intermediate > math.MaxInt32 {
return 0, ErrOverflow
} else if intermediate < math.MinInt32 {
return 0, ErrUnderflow
}
return Fix32(intermediate), nil
}
乘法运算
设 $V_P$ 为两数之积，列出方程：
$$ \begin{aligned} V_P &= V_A \cdot V_B \\ &= A_{n} \cdot 2^{-n} \cdot B_{n} \cdot 2^{-n} \\ &= A_{n} \cdot B_n \cdot 2^{-2n} \\ \end{aligned} $$
可得，将两数的整数形式相乘，再右移 $2n$ 比特即得到 $V_P$ 。我们要求定点数结果，所以把 $V_P$ 替换为定点数形式：
$$ \begin{aligned} V_P &= A_{n} \cdot B_n \cdot 2^{-2n} \\ P_n \cdot 2^{-n} &= A_{n} \cdot B_n \cdot 2^{-2n} \\ P_n &= A_{n} \cdot B_n \cdot 2^{-2n} \cdot 2^n \\ P_n &= A_{n} \cdot B_n \cdot 2^{-n} \\ \end{aligned} $$
代码实现
func Mul(a, b Fix32) (Fix32, error) {
intermediate := int64(a) * int64(b)
intermediate >>= 16 // fix32 is Q15.16 format
if intermediate > math.MaxInt32 {
return 0, ErrOverflow
} else if intermediate < math.MinInt32 {
return 0, ErrUnderflow
}
return Fix32(intermediate), nil
}
除法运算
对于除法，我们可以转化为 $V_P = V_A \cdot \frac{1}{V_B}$ 代入推导：
$$ \begin{aligned} V_P &= V_A \cdot \frac{1}{V_B} \\ P_n \cdot 2^{-n} &= A_n \cdot 2^{-n} \cdot \frac{1}{B_n \cdot 2^{-n}} \\ P_n \cdot 2^{-n} &= \frac{A_n \cdot 2^{-n}}{B_n \cdot 2^{-n}} \\ P_n \cdot 2^{-n} &= \frac{A_n}{B_n} \\ P_n &= \frac{A_n}{B_n} \cdot 2^{n} \\ \end{aligned} $$
这里要考虑的一个细节是，如果我们先计算 $\frac{A_n}{B_n}$ 再求 $\cdot 2^n$ 则会因为 $A_n$ 和 $B_n$ 的整数除法丢失了小数部分而损失精度。
只要调整一下计算顺序：
$$ \begin{aligned} P_n &= \frac{A_n}{B_n} \cdot 2^{n} \\ &= \frac{(A_n \cdot 2^{n})}{B_n} \\ \end{aligned} $$
小数位就能被正确计算出来，与原式也是等价的。
代码实现：
func Div(a, b Fix32) (Fix32, error) {
// divisor can't be zero
if b == 0 {
return 0, ErrNaN
}
intermediate := (int64(a) << 16) / int64(b)
if intermediate > math.MaxInt32 {
return 0, ErrOverflow
} else if intermediate < math.MinInt32 {
return 0, ErrUnderflow
}
return Fix32(intermediate), nil
}