1 个不稳定版本
0.0.0 | 2022年5月17日 |
---|
#21 in #digit
87KB
2K SLoC
BigFixed数字
BigFixed是一种数据格式,专为进行任意精度二进制表示的数值运算而设计。当精度是任意的时候,固定点数和浮点数之间的区别最终是没有意义的,但我们选择称它们为定点数,有特定的原因,这些原因并不特别重要。
浮点数很棒——每个人都想使用它们而不必担心细节,大多数情况下这也是可以的——但实现通常是架构相关的(即使只有一点),因此是非确定的。BigFixed的主要目标是构建一个平台无关的浮点数等效物,但可以对创建浮点数系统的各种精度选择进行控制。
[当前开发阶段是构建实现这一目标所需的背景机制。目前向用户公开了一些技术参数。最终计划是在大部分功能确定后,构建一个配置方案来处理技术细节,并向最终用户公开一小套参数。他们将选择一些与所需的数值精度相关的值,该配置将处理所有细节,以便像熟悉的浮点数一样Just Work™]
BigFixed是一个基于位的位置运算系统,其中Digit
是原生无符号整数类型之一u*
(除了最大的u128
)。[在开发过程中Digit是u16,但在最终产品中,Digit的选择将是u32、u64或通过某种配置方案进行配置。]每个BigFixed数字都有一个无限的二进制表示,其中除了有限多个位外,其他位都是平凡的。Digit将这个序列分割成块
... 00000000 00101101 01001101.10100111 01000000 00000000 ...
// if Digit is u8
许多操作有极端情况,其中可能发生溢出/其他错误(主要是索引限制引起的)。这些通常是可避免的,但大多数操作仍然返回一个Result
类型以防万一。
遵循Rust的本地整数惯例,除法之外的所有操作都使用补码(即补码运算)。除法使用符号幅度。
索引
位置索引使用 crate::Index
类型进行。Index 本身是一个枚举,分为 Bit(isize)
和 Position(isize)
。位置指的是构成大固定数(BigFixed)的数字,位指的是位。如果大固定数 x
的二进制表示如上所示(使用数字 u8),那么具有 Index::Position(-1)
的数字是 10100111
,而位 Index::Bit(10)
是这个位
... 00000000 00101[1]01 01001101.10100111 01000000 00000000 ...
索引可以相互添加、乘法、比较,以及枚举版本之间的类型转换。从位到位置的转换本质上是对整数进行除法,因此是一个有损操作。
整数类型 isize
虽然很大,但有限。因此,实际上有许多 Index::Position
值超出了相应 Index::Bit
变体的范围。IndexError
是设计用来表示这些现象的错误。大多数索引操作都有极端情况,其中可能出现 IndexError
,因此大多数操作返回 Result
类型而不是直接结果。
大固定结构(BigFixed Struct)
大固定(BigFixed)的组成部分
- head: Digit
- body: Vec<Digit>
- position: Index
头部和身体一起代表了一系列数字(小端),头部重复到正无穷的位置。根据补码算术,头部只能是 0 或 ALLONES(最大的数字,其二进制扩展为 111...111)。位置是最不显著的身体的权重,即小数点的位置。二进制扩展到此点以下均视为 0。
大固定有适当的格式,如果破坏了该格式,会导致算法效率低下或不兼容。位置必须是 Index::Position
类型(不是位),身体不得包含琐碎数据;如果数据可以被吸收到头部或尾部,则该数据是琐碎的。任何大固定都可以通过调用 self.format()
来正确格式化。
在扩展中,可以通过使用 crate::Index
类型(对于名称冲突表示歉意)的标准操作 Index 和 MutIndex 来访问系数。通过 Index 访问引用会得到适当的引用值(头部、身体内部或尾部),而不会更改 BigFixed 或进行实际分配。大固定数还可以通过 isize
进行索引--其值首先被强制转换为 Index::Position
。
首先获取可变引用会根据需要扩展身体到该位置,可能进行重新分配,以保证任何修改都发生在身体内部。获取可变引用可能会破坏大固定格式,因此请确保之后重新格式化。如果要对连续的系数块进行修改,则可以通过首先调用 self.ensure_valid_range(...)
将整个块空间一次性带入可变作用域,从而将重新分配保持在最低限度。
数字零是特殊的:头部是0,体是空的。在这种情况下,位置(最小非平凡系数的权重)没有意义,因此按照惯例,零的位置始终设置为0。我们可以选择将其位置设置为某种形式的无限大或最大值,但我们没有这样做。位置为0与是小整数相对应 - 介于 -ALLONES 和 ALLONES 之间的所有其他整数也有位置为0。
转换
Rust的所有原生整数类型都可以使用 std::convert
语法与 BigFixed 进行转换。从整数转换为 BigFixed 总是无损的。
从 BigFixed 获取整数不是无损的。对于无符号整数类型,如 u32::from(&x)
(其中 x 是 BigFixed),是对应位范围的直接位转换。另一方面,取无符号整数是一种饱和操作。如果 x
的值太大(正或负),则结果是最合适的最 i*
值。【分数值的舍入方案目前尚未明确定义,但最终将与 Rust 的原生 float_type::round 方法一致。】
BigFixed 还具有通用的浮点转换。国际标准浮点格式 IEEE 754 包含三个用于位浮点数据格式的参数:指数宽度、指数偏移和尾数宽度。任何遵循此标准的浮点数都可以通过基于 self.float_from_bits
和 self.float_to_bits
方法的简单转换与 BigFixed 进行转换。这涵盖了 Rust 原生的 f32 和 f64 类型以及其他 crate 的浮点类型。
操作
大多数 std::ops
中的操作都针对 BigFixed 实现。除法之外的所有操作都是无损操作;除法是特殊的,并且只有精确的实现。
在标准(非除法)操作中,所有操作都是基于 OpAssign
。也就是说,首先使用 &x + &y
构建一个新的 BigFixed c = x.clone()
,然后调用 c += &y
,返回 c
。尽可能使用 OpAssign
版本以最小化分配。在 OpAssign
实现中,就地调整大小(如果需要),而不是重新构造体部分的 Vec。
【目前可以使用 BigFixed::combined_div(&mut num, &denom, places)
进行除法。使用长除法同时计算商和余数(因此命名为 combined
),直到指定的小数位数。选择这种特定结构是为了最小化计算中的重新分配 - 它打算成为将来更易于使用的除法和余数操作 API 访问点的后端机制。在算法执行过程中修改了分子,最后它包含余数的值;商被构建并返回。]
截断
尽管在BigFixed数字上进行的纯操作是无损的,但在实践中,我们通常并不希望结果具有完整的精度。我们的数字可以迅速变得难以想象的精确(数千或数百万位数字),这会减慢我们的代码,以保持我们最终并不关心的精度级别。这个问题存在于所有标准操作中,但乘法是主要的罪魁祸首。
我们处理这个问题的方法是使用截断。截断和Cutoff结构体足够重要,值得单独的文档说明[正在进行中],但主要思想是指定我们需要的结果精度,并且只计算到那个精度级别。
所有标准操作都有截断变体,它们确实如此。调用它们就像输入一个对(&b, c)
,我们原本会为无损版本提供&b
,即
// a and b are BigFixeds and c is a Cutoff
let full_product = &a * &b;
let cutoff_product = &a * (&b, c);
[截断机制已经就绪,但其最终用户API尚未最终确定。计划有一个配置对象,其中包含两个全局Cutoffs——一个用于内部计算,一个用于最终结果。前者包含比后者更高的精度。参见 https://stackoverflow.com/questions/612507/what-are-the-applications-benefits-of-an-80-bit-extended-precision-data-type —— 使用80位数字进行64位数字的计算]
示例
尽管此代码没有实现,但为了举例,假设数字是十进制模运算。那么ALLONES是数字9,并且由此产生的位置算术是熟悉的印度-阿拉伯十进制系统。在这个例子中,整数1,以十进制展开为...0001.000...
,被表示为
BigFixed {
head: 0,
body: vec![1],
position: 0
}
-150.00这个负数,其展开来自补码计算
...0000150.00000... = 150
...9999849.99999... = -150 direct opposite
...9999850.00000... = -150 equivalent value
因此,如果我们想让x
表示-150的BigFixed,我们取
let x = BigFixed {
head: 9,
body: vec![5, 8], // little endian
position: 1
}
取x[0]
给出(对数字的引用)0(同样,x[-1], x[-2],...
),而x[1] == 5
,x[2] == 8
,以及x[3] == x[4] == ... == 9
。
我们可以通过将 x
中的 x[0] = 1 设置为 -149,或者通过将 x[1] = 5 和 x[0] = 9 设置为 -151 来实现。这两种方法都会将体的大小调整为 3(并且可能重新分配内存)。当然,我们也可以选择 x (+/-)= BigFixed::from(1)
,让 BigFixed 处理细节。这种方法在调整 x
的体的大小时,会额外构建一个 BigFixed (1),这虽然成本微小,但值得关注。