大数运算库的设计与实现

在计算机科学中,处理大数问题是一个常见且具有挑战性的任务。传统的数据类型,如整型(int)或长整型(long long),在数值大小上存在限制。例如,unsigned long long 类型在大多数平台上最大只能表示到 2^64 - 1。然而,在某些应用场景,如密码学,可能需要处理比这大得多的数值。本文介绍的库就是为了解决这一问题,它允许进行任意大小数值的运算,只要系统的内存足够大。

多核库的使用

为了充分利用现代多核处理器的能力,该库使用了作者自己开发的线程池库 tpoollib。这个库利用了 Windows Vista 及以上版本中的线程池 API,可以有效地在多核处理器上并行执行任务。

N 类的内部实现

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 类的实例发生变化后,都会调用一个特殊的函数来辅助调试。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) { // ... }
沪ICP备2024098111号-1
上海秋旦网络科技中心:上海市奉贤区金大公路8218号1幢 联系电话:17898875485