在计算机科学中,处理大数问题是一个常见且具有挑战性的任务。传统的数据类型,如整型(int)或长整型(long long),在数值大小上存在限制。例如,unsigned long long 类型在大多数平台上最大只能表示到 2^64 - 1。然而,在某些应用场景,如密码学,可能需要处理比这大得多的数值。本文介绍的库就是为了解决这一问题,它允许进行任意大小数值的运算,只要系统的内存足够大。
为了充分利用现代多核处理器的能力,该库使用了作者自己开发的线程池库 tpoollib。这个库利用了 Windows Vista 及以上版本中的线程池 API,可以有效地在多核处理器上并行执行任务。
N 类是库的核心,它使用一个动态数组(vector)来存储数字的每一位。这个数组中的元素类型是 int,代表十进制数中的一位。N 类还存储了一个基数值(默认为10),用于标识数字的进制,以及一个布尔标志位来表示数字的正负。N 类可以通过整数或字符串来构造:
N n(5LL);
N n(-12438LL);
N n("384747274747282882818373");
// 如果遇到非数字字符,解析将停止
N n("-274727372737");
N n("111", 2); // n = 7
N 类还提供了一个成员函数 ParseBase,可以将不同进制的字符串解析为 N 类的实例:
N n;
n.ParseBase("FFFF", 16); // n = 65535
在库的调试版本中,每次 N 类的实例发生变化后,都会调用一个特殊的函数来辅助调试。N 类的下标操作符(operator[])可以获取从右边数起的特定位数。例如,如果 n = 12345,那么 n[0] 就是 5。如果指定的位数超出了数字的范围,函数不会崩溃,而是返回 0,这使得它在进行加法或乘法运算时非常有用。
函数 s(unsigned long long base = b) 返回 N 的字符串表示,可以指定进制。函数 tobase(unsigned long long nb) 返回一个新的 N 实例,它存储了与原 N 相同的值,但是以不同的进制表示。
N a("12345");
auto a2 = a.upperpart(2); // a2 = 12
auto a3 = a.lowerpart(3); // a3 = 345
a.Set(16LL);
auto str = a.s();
// str = "16"
str = a.tobase(2).s();
// str = "10000"
str = a.tobase(16).s();
// str = "10"
str = a.tobase(10).s(); // str = "16"
加法运算最终会调用函数 w_add,该函数遍历两个数字的所有位数,并进行加法运算,同时处理进位:
static N w_add(const N& n1, const N& n2) {
// ...
}
减法运算最终会调用函数 w_subx:
static N w_subx(const N& n1, const N& n2) {
// ...
}
w_logical 函数用于执行逻辑运算,如 AND、OR 和 XOR。它总是将数字转换为二进制格式。注意,除非两个操作数都在二进制格式,否则运算符 ^ 默认执行 w_pow。
static N w_logical(const N& n1, const N& n2, int x) {
// ...
}
乘法函数创建了一个 N 类型的向量,包含所有的乘法运算,然后将它们相加:
static N w_mul(const N& n1, const N& n2) {
// ...
}
除法函数(用于除法运算符如 /、%、/=、%= 等)返回一个包含结果和余数的元组:
static tuple w_div(const N& n1, const N& n2, bool NoChangeBase = false) {
// ...
}
幂运算函数相对简单:
static N w_pow(const N& n1, const N& n2) {
// ...
}
多核加法接受一个 N 类型的向量,并成对相加,然后递归调用自身,直到只剩下两个数字需要相加:
static N w_add2(vector& n, tpoollib::tpool<>& pool) {
// ...
}
多核乘法创建了一个乘法的向量,然后使用 w_add2 函数将它们相加:
static N w_mul2(const N& n1, const N& n2, tpoollib::tpool<>& pool) {
// ...
}
多核幂运算只是使用 w_mul2:
static N w_pow2(const N& n1, const N& n2, tpoollib::tpool<>& pool) {
// ...
}