关于大非负整数计算的一些想法

前言

就是说，关于吾等人在看《算法分析与设计》时坐大牢，随便找点其他的乐子当作兴趣玩玩了。不得说，现在个人的感受是，早知道当年还不如选算法，搞安全搞得头疼，说到底就是搞各种测试啥的，搞算法搞得头秃（起码头不疼 (●ˇ∀ˇ●)。

~~主要还是卷不动了~~

不妨就当作一些奇怪的想法，当作随笔写写看了。

绪论（瞎扯）

一些简单数值运算实例，比方说加法、乘法、幂次乘法啥的，其实归根到底还是对加法的灵活运用，个人的感觉（大概？）。这就像是说像一个很简单代码：

1
2
3

int a = 1;
bigInt N;
a = a + N;

以上这样看起来似乎非常非常的简单，但实际上如果再往深一层考虑的话是可以扯出很多东西来的。就这个 int a = 1 而言，显然是限定了这个变量 a 是一个 int 型，也就是熟知的数据类型。

在 数据结构 中对高级语言的数据类型的解释是 一组性质相同的值的集合和定义在该值集上的一组方法的总称 。从中可知，这个值集是有范围的，而且根据操作系统而定。一般来说，如果是大于等于 32 位系统， int 类型的大小为 4 个字节；对于小于 32 位系统， int 类型的大小为 2 个字节（这也是为啥有些C教材里面的关于 int 类型的答案是 2 字节长度）。

当然，就目前来说吾等人的想法并不想深究这个玩意，只是表示假设想写的所有内容都是以 64 位为例（相当于指针大小为 8 位大小，可以用 unsigned long long int 来强转指针的歪门邪道 ~~随便说说~~）。另外下述的所有 long 实际上和 long int 以及 int 一致的，都是 4 个字节，而 long long int 是 8 个字节。回归来说，上面的 int a 的最大大小为 4 个字节，而又由于这是一个有符号数，则第 1 位用来表示符号，这也就是其值集为整数 -2^31 ~ 2^31-1 的原因，这也就是什么补码反码的内容了，比方说 负数值(原码) = 补码 - 1 AND 取反 ，当然，无论如何，符号位永远不变！

那么瞎扯完毕，对于 int a 运算的值的有效计算位数为 4 * 8 - 1(符号位) = 31 位，凡是无论多大的整数 N（位数很高的整数）都会自然而然的强行在化为 int a 类型的值集范围（假设看作强转成与 int 位数相同的类型）内进行运算，并且当 N 的位数 bit(N) 有 bit(N) >= 8 时（不包括 N 的符号位）那么 a 的符号位也会被计算到，这实际上可以人为地将 N 的低 8 位看成 unsigned int 类型，所以说当所要计算的数足够大时，会改变原有数值如 a 的符号（溢出），这是不可接受的。

正因为高级程序设计语言所提供的 数据类型 在很多时候无法满足一些 “大宇宙” 问题（如某某曾对有关如何对全宇宙的所有事物进行排序时采用归并排序的荒谬思路），说简单点比如关于素数 P 的判定充要条件

当 P 足够大时，阶乘的计算量可想而知（超过常规 数据类型 所能表示的大小）；亦或是需要求一些比较大，但不完全大的数值，比如某些毫无意义的值 520 ^ 520 啥的，自定义一个 大整数 是很有必要的！

理论

简单加法

先从最最简单的加法运算来进行分析罢。

对于一个数，如先做以下赋值：

这对所有人（九漏🐟除外）来说如果计算以下式子：

简直就是随意随意呀。这里之所以能这么快得出答案是因为脑子已经习惯了 10 进制的计算（有志者或大佬除外），并且在计算机中对已给定的 数据类型 也有相关明确的计算规则，不需要人为的进行计算规则的实现。

但是！上面已经说了，高级程序设计语言给定的 数据类型 还不够！现在所给的 数据类型 （也就是Integer ）并不是高级程序设计语言已经给定好的 数据类型 ，而是一个能表示很大很大（~~位数小于内存大小的位数~~）的数值的 数据类型 ，也就是说这是一个自定义的、只能用以存储人为给定数值的 数据类型 ，那就必须得人为地为其实现计算规则。

为此，由于最小存储单位为位，这里以 位运算 的角度来分析一下上述式子进行计算的过程，首先是 A = 10 ，从 二进制 角度来看，其值显然为 A = 1010 ；而 B = 1 。对 A 和 B 做求和运算，即 A + B 实际上也就是：

对于 Σ = A + B = 1011 的结果简单说来就是，低位对齐，各位作和 ，由于并没有满足进位，再来看存在进位的例子 A + C ，也就是

此时，还是先 低位对齐 ，然后进行 各位作和 运算，设进位标识符为 F：

通过对上述部分的分析，不难看出和 Σ 第 n 位数的值符合以下的规则：

总结来说可以看作当且仅当 (A[n] + C[n] + F) % 2 = 1 时候 Σ[n] = 1 ，而 (A[n] + C[n] + F) % 2 = 0 时候 Σ[n] = 0 。

因此可以简化为

至于关于 F 的值，若设 pi[n] 为变量 i 第 n 位计算前的初值，且 pF 为 F 当前的值，也不难看出，当有 2 个数值参与运算时（两个数的位数同长）符合以下规则：

显然，若 pF = 0 ，只有当 pA[n] 和 pC[n] 都满足 pA[n] = pC[n] = 1 时，F = 1，而对 pF = 1 只要 pA[n] = 1 或 pB[n] = 1 即可使得 F = 1 。

简而言之，可以写成

如果其中一个数值（如设为 A）已算完，但此时 F = 1 ，需要对另一个数（如设为 C）进行补位，则满足以下规则：

以及

由于作简单的加算至多加到原数的 2 倍，因而以二进制来说，最终结果的位长度至多增加 1 位，也就是说，若设两个数 P 和 Q ，则 P + Q 的和的二进制位最大长度为

由此可知，如果由上述的规则将 Integer 类型进行加法运算，可以先将其转换为二进制，然后再进行 低位对齐，各位作和 ，同时根据进位标识符 F 进行补位，易知，在最差的情况下 时间复杂度 为

这是什么概念呢，如果 P 和 Q 当作十进制数来看，时间复杂度 相当于

这么一看，效率还是比较可观的。

简单乘法

说到乘法，以小学的思维来看若取 R = P * Q ，则可以把看作 R 看作是 Q 个 P （或 P 个 Q ）相加的结果。这么看，怎么说呢，能用，但不完全够用（~~用吾等人师傅的话来说就是，所以其他人和其他人的使用者也就只能处在同一水平的圈子里了~~）。

假设以上面所述的方法来计算乘法，而再使用上一小节所述的加法实现法来对乘法进行实现，在不考虑效率，而只求结果的情况下，确实可行，但弊端也很明显——计算过程过于简单（搭积木水平）了。在最坏的情况下，无论所算的数的值是如何，若设

在最坏情况下，时间复杂度 可以达到

其中 β 为修正值，因为每次做加法运算都有可能出现进位的情况，而 M 和 N 的值只与最大数值本身有关，这是很不好的结果。

那么，若以初中的思维来看一下有关数 R = P * Q 的计算过程，众所周知，乘法是符合 结合律 和 分配律 的，不妨先以 结合律 的思想来做一个简单讨论。

此时若设对任意正整数 K > 0 ，有 R = P * (K * Q/K) ，也可看作

设

还可看作

或

此时也就可以人为地对通过对 K 值的构造来找到特定的、能使得对 P 和 Q 有利（或只对 P 或 Q 有利，或相比直接计算更效率）的情况。

但是，由于 P 和 Q 都同为大整数，而上述式子所述的 K 值显然得满足为 Q 的非平凡因子，否则得到的结果会出现浮点数或无意义；同时，即便是找到了对应的 K 值，在计算 K/Q 时仍需要解决另一大与乘法类似的问题——除法（若将除法看作是乘倒数），这有点就像是进入了一个递归；并且若以上述方式作为分解，并不一定能够降低过程中进行加法运算的数量，甚至可能会比直接计算更多。

当然，可能对 结合律 应该也是有解的，就是说吾等人才疏学浅，就先不拓展了。

若再以 分配律 进行讨论，不妨将 R = P * Q 中的 Q 表示为 Q = K1 + K2 + K3 ... + Kn ，则原式有

再次进行分解还可以看作是

如果就此来看，似乎是比 结合律 更复杂了，且加法运算并没有得到改善。但是其中的 K1 K2 K3 ... Kn 如果从搞安全的角度看来，可以说成是 ”部分完全可控“（存在一种构造序列使得在部分个体满足一定条件时，其他部分完全可控）的，既然是 ”部分完全可控“ 的，不妨以二进制的思想再来进行考虑。

显而易见，任何该 Integer 类型值集内数值（若计算结果为非负整数）都是可以使用二进制来表示，若对 Q 进行二进制分解，可得

其中使得 m = n ，再将 Ci (i = 1,2,3, ... m ) 和 Ki (i = 1,2,3, ... n) 进行切合，带入上式，可得

再进行简化成

此时不妨将 R 看作一个 复合函数 ，如设

其中 P 为非负整数，Ci 为 i = 1,2,3, ... m 的给定序列。

现在先对 m 值进行分析，由于这个 Ci 序列由 Q 分解得到，若以集合 S 来表示 Ci ，则

即，求集合 S 的值只需要对 Q 进行移位运算（如向右移动 j 位），若其第 1 位值为 1 则称 (2^Cj) 为构成 Q 的一部分。显然移位运算和与运算属于 位运算 ，是很效率的。其次，由于 Q 在一般情况下二进制表示是存在 0 的，也就是说，对 m 的取值，有

其中 |S| 为集合 S 的元素数量，这样就使得在计算总和时进行加法运算的数量有可能得以减少。再次，对于 Ci 序列，不难看出总有 Ca < Cb 当且仅当 a < b ，这就意味着若从 Q 的最高位开始求集合 S ，所得到的结果是有序的（降序），而对于以二进制表示的计算形如 (2^Ci)*P 实际上可以看作是 P 的二进制表示向左移动 Ci 位；若结合有序集合 S ，那么设

则后一个结果 Ca 就能由前一个结果 Cb 通过向右移动 b - a 位得到。即对集合 S 内的所有

只需在通过 P 由高到低移位得到第一个（设为 Cb）结果后，其直接后继的值（设为 Ca）可通过其直接前驱 Cb 移动 b - a 位得到，在最坏情况下，构造该集合 S 的 时间复杂度 为

同时，在 复合函数 R(Ci,P) 中，若将其看成一个多项式，则每一个 Ci 都对应一个子式

则在求该函数的值时在最后会对这些子项进行一个求和，求和的数量为 m 。

再对每一个子式进行分析，显而易见，对任一

进行求和时，若代入上一小结所述的方法，则该对子项加法运算时，在最坏的情况下，计算这对子项和的 时间复杂度 为

其实就是会多计算 Ca 或 Cb的值，因为在集合 S 中无相同的值，即 Ca != Cb ，因此在进行加法运算时，按照 低位对齐，各位作和 的规则，最坏的情况是指计算过程进 1 位的情况，此时所进行计算的位长度就为 Max{Ca,Cb} + bit(P) + 1 。

那么由此可以得出，若在最坏的情况下，整个乘法运算所需要的 时间复杂度 约为

或

即主要还是和 Q 有关，且主要影响的是在集合 S 的构成部分。如果使用该方法，实际运用时可以考虑分解较小的乘数。

幂次乘法

相较于简单加法和简单乘法，对幂次乘法来说，更像是在简单乘法的基础上再做乘法。不妨还是先以小学的角度来看有关幂次乘法的计算，如给定一个 R = P^Q 自然而然地想到，相当于 Q 个 P （或 P 个 Q）进行相乘得到的结果。而乘法运算在如此角度来看，原型为多个数值的累加，以此再进行分解，将第 i 趟 P 自乘得到的结果记为 L{i} ，则可以得到递推式

即

若以这种思想进行计算，每一趟乘法都需要做 P 次的加法运算，设 U{i}{j} 为在做第 j 次加法运算时第 j-1 次得到的和，在最坏的情况下，第 i 趟乘法所作的加法运算的 时间复杂度 为

由于对第 i 趟乘法中 L{i} 的每一次加法运算不可能每一次都会进位，所以 ɑ 仅作为一个修正值看待。

不难得出总的 时间复杂度 为

或

不妨先对 bit(L{i}) 进行分析，由于对任意

显然总有

而对任意 bit(L{i}) 存在

若以最坏情况来看，即对每一个 bit(L{i+1}) = bit(L{i}) + bit(P) ，这就类似于等差数列求和了，时间复杂度 还可表示为

其中，再将对第 i 趟乘法求和过程进行适当简化，不妨设 M[i] 为第 i 趟求和过程中对位的操作数，可由

得

易知

那么

整理可得

而

可见，如果直接按加法进行运算，在最坏的情况下，其 时间复杂度 是很大的，且受位影响不如值本身大，这对以二进制表示法来进行计算是很糟糕的。

若以上一小节所述的乘法来进行运算，则可以设第 i 趟 P 自乘得到的结果记为 F{i} ，得到递推式

做一下简单的代入，很容易得到 时间复杂度

或

显然，后者为较佳的选择，不妨再对后者进行讨论。

由上面已知，对于 bit(F{i+1}) 最坏情况下为 bit(F{i+1}) = bit(F{i}) + bit(P) ，那么在以后者为前提，最坏情况下，还可以写成

化简可得

由此可见，起决定性作用的关键还是在 Q 上，因此若想加快幂次乘法的效率，就得从 Q 的优化入手。

应用

求幂算法

由上一章已经得出，若想对幂次乘法的计算做优化，就必须优化 Q ，而 Q 实际上在上一章的定义中为递推式的长度，也可以称为连乘的次数。

不妨先设 E 为求 R = P^Q 时所作的乘法数量，则此时根据前面所述的内容，可知 E = Q，用伪代码可以做以下表示

Integer pow(Integer P, Integer Q){
    if(P == 0) return 0;
	Integer R = 1;
    for([1..Q]){
		R = R * P;		
	}
    return R;
}

显然这是比较通俗易懂的思想，但并没有能对 E 做到优化，可以以此为基础继续向下讨论。

首先，不难注意到 Q 作为幂次也是属于非负整数值集，且对于幂次的运算由于底数 P 相同，也就可以看作是对总幂次 Q 的加法链分解。当然最小加法链属于 NP完全问题 ，可求但代价有些大，不如用其他类似的、效果近似的方式使得让 E 尽可能的小于 Q ，这样就将幂次多连乘的问题分解成了求 Q 的次优加法链的问题。

现在来讨论第一种方案，对 Q 的值做一下分解

其中对任意

若设 R{i} 为第 i 趟乘法得到的值，则确保了

即对当前所求的结果，总能从对前一个结果做平方得到。同时，为确保连续性，K1 的值必须为 1 ，用以表示 P 的初值。在最理想的情况下，也就是恰好存在这样一个关于 K 的序列，则做的乘数 E 恰好就为 bit(Q) 。

但并非所有数都能分解成这样的理想 K 序列，最简单的例子，如

不难看出，在对 12 分解过程中，存在后一个 Kj ≠ 2*Ki 的情况，为此，就不能够简单的将这一步骤的结果以上一步结果的平方来表示了。

如果对 K 序列的理想值进行分析，显然可以看作是一个包含 1 的非负偶数集，即当存在 Kj ≠ 2*Ki 情况时，Kj 必然是非负偶数集的补集， Kj 为一个正奇数。应对这类情况的正确做法是，若当前期望得到的 Kj 值为奇数时，而此时上一步得到的 2*Ki 与期望值得到的 Kj 不符时，需要 2*Ki 补 “1” ，也就是将上一步结果与 P 做乘法运算，以弥补差值。

这样也就可以得到关于新的 K 的递归式

还可以得到关于 R{i} 的递推式

根据上述递推式，可写出以下递归函数

Integer pow(Integer P, Integer Q){
    
    if(Q == 0) return 1;
    if(Q == 1) return P;
    
    Integer R = pow(P,Q >> 1);
    
    R = R * R;
    if(Q % 2 == 1){
        R = R * P;
    }
    
    return R;
}

其中递归段 Q >> 1 相当于 Q / 2 (向下取整)，根据当前分解得到的的 K 值是否为奇数决定在最后是否再将上一步骤的结果乘上 P (补 “1”) 。

显然，该算法需要的 空间复杂度 为递归最大层数

若将做乘法运算的次数 E 看作 时间复杂度 的计算单位，则 时间复杂度 为

其中， C 为 K 序列中奇数的数量。

若再对该算法进行讨论，易知，这是一个非尾递归函数，而一般来说，这类递归函数是可以用通过栈来模拟等价成非递归的递推形式。但如果使用栈来进行模拟意义不大，显然栈的深度和该算法递归时的 空间复杂度 一致，这样其 空间复杂度 并没有得到改善。

那么不妨对栈内所需存储的数据内容进行分析，由于每次调用内层递归时，Q 的值都会时原来的二分之一，即可看作向右移动 1 位，而判断是否为奇数看的是当前层 Q 二进制表示的第 1 位是否为 1 。也就是说，若忽略对当 Q 为奇数时的处理，则该算法可以作为尾递归来看待，此时，栈的作用就很明显了，是用以记录当前层 Q 的值是否为奇数的判断，以便在结束内层递归进行子问题组合时决定当前层是否乘上 P (补 “1”)。

实际上，若设 i 为算法的第 i 层递归调用（若将首次调用看作是第 1 层），则将当前层 Q的值即可看作是 Ki ，且满足

此时也就可以通过将 Q 通过向右移位 i 层来获取当前层的 Ki 值，可写出以下递推函数

Integer pow2(Integer P, Integer Q){

	if(Q == 0) return 1;
	
	Integer len = 0;
	Integer R = P;
	
	for(Integer i = Q; i > 0; len ++,i = i >> 1);
	for(len = len - 2; len >= 0; len --){
		R = R * ((Q >> len)&1 ? R * P : R);
	}
    
	return R;
}

在这个算法中多了一个 len 变量，用以记录 Q 值二进制表示的位的长度，然后通过对Q 和 len 的相关计算来模拟上述递归算法中第 len - 1 层递归的情况，以便决定是否乘上 P (补 “1”)。

总的来说相比递归算法其 空间复杂度 降低到了

但相对的，需要知道 Q 值二进制表示的位的长度，多了一层计算，则一般 时间按复杂度 为

实际上，还可以通过位运算来规避求层数的问题，如以下函数

Integer pow3(Integer P, Integer Q){
	
	if(Q == 0) return 1;
	
	Integer R = P;
    
	for(Integer i = Q >> 1; i > 0; i = i >> 1){
		R = R * ((Q^i)>Q ? R : P * R);
	}
	
	return R;
}

这样可进一步降低 时间复杂度

不过，这对乘法运算的次数 E 并没有影响。

若设 C 为序列 K 中奇数的数量，显然有 C ≤ bit(Q)，不妨取 C = bit(Q)/2 ，则乘法运算的次数 E 可表示为

即在对幂次为 Q 的求幂算法中，只需要做 E 次乘法，这相较于直接做连乘是有很大改进的。

猜想

在上一小节中，是将 Q 分解成了关于 2*Kn 的递归式，这样总可以找到

即在 K 序列中，任何值不相等且是有序的，若设 Ki 是 Kj 的直接前驱，当知道了 Ki 的值，通过很简单的计算就能得到 Kj 的值。

但从另一个角度来看，由于 Q 是属于非负整数值集，如果设 [*] 为向下取整符号，则将其分解成

也就是说若能确定一个 C 的值使得该等式成立，所需要的乘法运算次数就能降低至

那么解决该问题的关键是如何求 C 值，并且 C 值最好能由 Q 或在求 P^(2^[log2(Q)]) 的过程中通过简单的计算得到，但似乎不太可能。

实现

链串法

由于C语言每次申请动态变量只能以"字节"为单位，无法精确到"位"，为节省空间，不妨借鉴 链块串 的结构，根据位长来申请尽量少的字节，并用一个记录当前位数的变量来约束大整数的运算长度。

易知，一个字节等于 8 个位，所以若设 [*] 为向上取整符号，且 size 为字节长度， bits 为位长，那么满足以下关系

接着来讨论如何对某个字节的指定位进行操作，若设需要操作的位为第 n 个字节的第 i 位，且 n{i} 为第 n 字节的第 i 位（后文皆同）。当期望该 i 位的值为 0 时，需要将第 n 个字节和一个值为 2^i 的修正字节 m 的取反做与运算，即构造除第 i 位为 0 其他位全为 1 的字节；而当期望该 i 位的值为 1 时，则需要将第 n 个字节和一个值恰好为 2^i 的修正字节 m 做或运算，保证除了第 i 位为 1 外，其他位都为 0 。

至于修正字节 m 可以由 0x80 向右移动 8-i 或 1 向左移动 i 位得到，以第二种方式为例，可得

然后是关于存储的格式，为方便当作加法运算时能够很快的做到 低位对齐 ，设可以由低位开始，有序存储到 n = 0,1,2, ... size 的字节上。通俗地说，若将这些存储的字节看作数组，则相当于将数值二进制位从低到高，存到字节数组的从左到右(若设最左的下标号为 0 ，往右升序增 1) ，这样在做加法运算时，仅需让两个数的字节数组从下标为 0 的开始遍历计算即可。

但在做乘法运算时是需要进行数值二进制向左移动数位，若以这样的方式进行存储，在进行左移位运算时，就必须将字节数组中的所有值相对的往右移位。由于对字节数组变量扩容时，只能是往下标大的方向，无法在字节数组的左边补 0 ，因此需要将内容整体先向右移动，然后在其前面补上 0 。并且在推出下一个分解乘数时(即需要做右移位运算)，还需将整个内容向左移动，显然是很不效率的。

为解决这种情况，可在做乘法运算时，将存储方式反过来，即将低位放到字节数组下标最高处，这样扩容时可以直接在更高的下标处补 0 ，而在推出下一个分解乘数时，只需改变表示总位的长度。

除此之外，还得考虑一些情况，如两数相加或相乘若其中一数为 0 则无需继续计算，返回另一数或 0 等等。

按照上述讨论，可使用C类语言写出对应代码

// 大整数计算
#define INTEGER_DEFAULT_SIZE 10

class Integer{
	
	private:
		
		typedef unsigned char byte;
		int size;
		int bits;
		byte *pointer;
		
		// 返回最高位所在的字节下标 
		int len(){
			return (this->bits >> 3) + (this->bits%8 > 0);
		}
		
		// 判断字节数组是否为有效 
		bool null(){
			return this->pointer == NULL;
		}
		
		// 判断是否为空值 
		bool empty(){
			return null() || this->size == 0 || this->bits == 0;
		}
		
		// 判断第p位的值是否为 "1" 
		bool bit(int p){
			if(p < 0  || p >= this->size) return false;
			return (this->pointer[p >> 3] >> (7 - p % 8))&1;
		}
		
		// 扩容 
		void expand(){
			int newSize = this->size > 1024 ? this->size + 1024 : this->size * 2;
			int newLen = (newSize >> 3) + 1;
			this->pointer = (byte*)realloc(this->pointer,sizeof(byte)*newSize);
			for(register int i = len(); i < newLen; i++){
				this->pointer[i] = 0;
			}
			this->size = newSize;
		}
		
		// 复制 
		void copy(const Integer &i){
			this->size = i.size;
			this->bits = i.bits;
			if(i.size <= 0 || i.bits <= 0){
				this->pointer = NULL;
				return;
			}
			this->pointer = (byte*)calloc(this->size,sizeof(byte));
			for(register int t = 0; t < len(); t++){
				this->pointer[t] = i.pointer[t];
			}
		}
		 
	public:
		
		Integer(){
			this->size = INTEGER_DEFAULT_SIZE;
			this->bits = 0; 
			this->pointer = (byte*)calloc(this->size,sizeof(byte));
		}
		Integer(bool empty){
			this->size = 0;
			this->bits = 0; 
			this->pointer = NULL;
		}
		Integer(int size){
			this->bits = 0;
			if(size <= 0){
				this->size = 0;
				this->pointer = NULL;
				return;
			}
			this->pointer = (byte*)calloc(size,sizeof(byte));
			this->size = size;
		}
		Integer(const Integer &i){
			copy(i);
		}
		~Integer(){
			if(!null()){
				free(this->pointer);
				this->size = 0;
				this->bits = 0;
				this->pointer = NULL;
			}
		}
		// 设为 "0" 或归 "0" 	
		void zero(bool del){
			if(del){
				this->~Integer();
				this->size = INTEGER_DEFAULT_SIZE;
				this->bits = 1;
				this->pointer = (byte*)calloc(this->size,sizeof(byte));
			}else{
				this->bits = 0;
			}
		}
		// 获取两数位最大长度 
		int maxBits(const Integer i){
			return this->bits > i.bits ? this->bits : i.bits;
		}
		// 长整数类型转换(64bits)
		void dex2i(long long int i){
			int cur = 0;
			byte st = 0x80;
			for(register int tu = 0; i > 0; tu++){
				for(register int tp = 0; tp < 8 && i > 0; tp++){
					this->pointer[tu] = i&1 ? this->pointer[tu] | (st >> tp) : this->pointer[tu] & (~(st >> tp));		
					cur ++;
					i >>= 1;
					while(cur > this->size){
						expand();
					}
				}
			}
			this->bits = cur;
		}
		
		// 转换为二进制串 
		char *bin(){
			
			if(empty()) return NULL;
			
			int tl = len();
			int c = this->bits;
			byte st = 0x80;
			char *s = (char*)calloc(c + 1,sizeof(char));
			s[c] = '\0';
			for(register int tu = 0; tu < tl && c >= 0; tu++){
				for(register int tp = 0, tv = 7; tp < 8 && c >= 0; tp++, tv--){
					s[--c] = ((this->pointer[tu] & (st >> tp))>>tv) + '0';
				}
			}
			return s;
		}
		// 等于 
		Integer &operator=(Integer i){
			this->~Integer();
			copy(i);
			return *this;
		}
		// 加法运算 
		Integer operator+(Integer i){
			
			if(empty() || i.empty()){
				Integer it(empty() ? i : *this);
				return it;
			}
			
			Integer it(maxBits(i) + 1);
			
			bool flag = false;
			bool a,b;
			int itl = it.len();
			int tl = this->len();
			int il = i.len();
			register int tu;
			register int iu,ip,iv;
			register int itp,itv,itu;	
			register int c = 0;	
			
			// 采用关于修正字节的右移方式进行位运算 
			byte st = 0x80;
			
			// 初始化第一个加数		
			for(tu = 0; tu < tl; tu++){
				it.pointer[tu] = this->pointer[tu];
			}
			
			// 加上第二个加数 
			for(iu = 0; iu < il; iu++){
				for(ip = 0, iv = 7; ip < 8 && c < i.bits; ip ++, iv--){
					a = (it.pointer[iu] >> iv) & 1;
					b = (i.pointer[iu] >> iv) & 1;
					it.pointer[iu] = (flag+a+b)&1 ? it.pointer[iu] | (st >> ip) : it.pointer[iu] & (~(st >> ip));
					flag = (flag && (a || b)) || (a && b);
					c++;
				}
			}
			
			// 若存在局部进位 
			if(flag){
				itp = c % 8;
				itv = 7 - itp;
				itu = c >> 3;
				while(flag){
					while(itp < 8 && flag){
						a = (it.pointer[itu] >> itv) & 1;
						it.pointer[itu] = (flag+a)&1 ? it.pointer[itu] | (st >> itp) : it.pointer[itu] & (~(st >> itp));
						flag = (flag && a) || a;
						itp ++;
						itv --;
					}
					itp = 0;
					itv = 7;
					itu ++;
				}
			}
			
			// 若存在整体进位 
			it.bits = it.bit(it.size - 1) ? it.size : it.size - 1;
			
			return it;
		}
		// 乘法运算 
		Integer operator*(Integer i){
			
			if(empty() || i.empty()){
				Integer it;
				it.zero(true);
				return it;
			}
			
			Integer it(this->bits + i.bits);
			Integer t(this->bits + i.bits);
			
			// 优先分解较小的乘数 
			Integer *less,*more;
			
			if(this->bits < i.bits){
				less = this;
				more = &i;
			}else{
				less = &i;
				more = this;
			}
			
			bool a,b;
			bool flag;
			int tl = more->len();
			register int im = less->bits - 1;
			register int itp,itv,itu;
			register int tp,tv,tu;
			register int ip,iv,iu;
			register int tc;
			
			// 采用关于修正字节的左移方式进行位运算 
			byte st = 1;
			
				// 高下标存储低位 
				itp = (more->bits + 8 - 1) % 8;
				itu = more->len()-1;
				itv = 7 - itp;

				tp = 0;
				tv = 7;
				tu = 0;
				tc = 0;
				
				while(tu < tl){
					
					while(tp < 8 && tc < more->bits){
						
							if(itp < 0){
								itu--;
								itp = 7,itv = 0;
							}
								
							it.pointer[itu] = ((more->pointer[tu] >> tv) & 1) ? it.pointer[itu] | (st<<itv) : it.pointer[itu] & (~(st<<itv));
							tc++;
							itv++,tv --;
							itp--,tp ++;		
						}
					tp = 0;
					tv = 7;
					tu++;
				}
				it.bits = tc + im;
				
				// 分解 
				while(im >= 0){
					
					if(less->bit(im)){
						
						flag = false;
						
						iu = it.len() - 1;
						ip = (it.bits + 8 - 1) % 8;
						iv = 7 - ip;
						
						tu = 0;
						tp = 0;
						tv = 7;
						
						// 对分配律各项做和 
						while(iu >= 0){
							while(ip >= 0){
								if(tp >> 3){
									tu ++;
									tp = 0;
									tv = 7;
								}
								a = (it.pointer[iu] >> iv) & 1;
								b = (t.pointer[tu] >> tv) & 1;;
								t.pointer[tu] = (flag+a+b)&1 ? t.pointer[tu] | (st<<tv) : t.pointer[tu] & (~(st<<tv));
								flag = (flag && (a || b)) || (a && b);
								ip--,iv++;
								tp++,tv--;
							}
							ip = 7;
							iv = 0;
							iu --;
						}
						
						// 若存在局部进位 
						while(flag){
							while(tp < 8 && flag){
								a = (t.pointer[tu] >> tv) & 1;
								t.pointer[tu] = (flag+a)&1 ? t.pointer[tu] | (st<<tv) : t.pointer[tu] & (~(st<<tv));
								flag = (flag && a) || a;
								tp ++;
								tv --;
							}
							tp = 0;
							tv = 7;
							tu ++;
						}
						
					}
					im--;
					it.bits--;
				}
				
				// 若存在整体进位 
				t.bits = t.bit(t.size - 1) ? t.size : t.size - 1;
				
			return t;
		}
};

理论上使用该链串法可以极大节省存储空间，即对于一个非负整数 P 而言，若设 [*] 为向上取整符号，S(*) 为对应类型的长度，则用该方法需要的字节数组空间为

所占的位空间大小还是比较接近 log2(P)。

字节法

在上一小节的链串法中通过修正字节 m 和对应字节的 n 运算来对第 i 个位进行运算，虽然仅仅是位运算级别的移位运算，但当数足够大时造成的效率损失仍然是有的。如在做 P + Q 运算时，若设 C 为两数在进行位运算时修正字节 m 的移位总数量，在最坏的情况下，即存在进位的情况下，且每个字节数组都填满且都进行了对应位运算，容易得出

而在字节法中以空间规避了这种多余的运算，直接在字节数组中用 1 个字节表示大数 1 个位。

用C类语言表示可得代码

// 大整数计算
#define DEFAULT_INTEGER_SIZE 100

class Integer{
	private:
		
		typedef unsigned char byte;
		int size;
		int len;
		byte *pointer;
		
		// 判断是否为空值 
		bool empty(){
			return this->pointer == NULL || this->size == 0 || this->len == 0;
		}
		
		// 判断字节数组是否为有效 
		bool null(){
			return this->pointer == NULL;
		}
		
		// 判断第n位的值是否为 "1" 
		bool bit(int n){
			if(n < 0 || n >= this->size) return false;
			return (bool)this->pointer[n];
		}
		
		// 扩容 
		void expand(){
			int newLen = this->size > 2048 ? this->size += 1024 : this->size * 2;
			this->pointer = (byte*)realloc(this->pointer,sizeof(byte)*newLen);
			for(register int i = this->len;i < newLen; i++){
				this->pointer[i] = 0;
			}
			this->size = newLen;
		}
		
		// 复制 
		void copy(Integer i){
			if(i.empty()){
				this->pointer = NULL;
				this->len = 0;
				this->size = 0;
				return;
			}
			this->size = i.size;
			this->len = i.len;
			this->pointer = (byte*)calloc(this->size,sizeof(byte));
			for(register int t = 0;t<this->len;t++){
				this->pointer[t] = i.pointer[t];
			}
		}
		
	public:
		
		Integer(bool empty){
			this->len = 0;
			this->size = 0;
			this->pointer = NULL;
		}
		Integer(){
			this->len = 0;
			this->size = DEFAULT_INTEGER_SIZE;
			this->pointer = (byte*)calloc(DEFAULT_INTEGER_SIZE,sizeof(byte)); 
		}
		Integer(int n){
			this->len = 0;
			if(n <= 0){
				this->size = 0;
				this->pointer = NULL;
			}
			this->pointer = (byte*)calloc(n,sizeof(byte)); 
			this->size = n;
		}
		~Integer(){
			if(null()){
				free(this->pointer);
				this->pointer = NULL;
				this->size = 0;
				this->len = 0;
			}
		}
		// 长整数类型转换(64bits)
		void dex2i(long long int i){

			register int tu = 0;
			while(i > 0){
				while(tu > this->size)
					expand();
				this->pointer[tu] = i & 1;
				tu++;
				i >>= 1;
			}
			this->len = tu;
		}
		// 转换为二进制串 
		char *bin(){
			
			if(empty()) return NULL;
			
			register int tu = 0;
			register int sp = this->len;
			char *s = (char*)malloc(sizeof(char)*(sp+1));
			
			s[sp--] = '\0';
			while(sp >= 0){
				s[sp] = this->pointer[tu] + '0';
				tu++,sp--;
			}
			
			return s;
		}
		// 设为 "0" 或归 "0" 
		void zero(bool del){
			if(del){
				this->~Integer();
				this->size = DEFAULT_INTEGER_SIZE;
				this->len = 1;
				this->pointer = (byte*)calloc(DEFAULT_INTEGER_SIZE,sizeof(byte)); 
			}else{
				this->len = 0;
			}
		}
		// 获取两数位最大长度 
		int cmpMax(Integer i){
			return this->len > i.len ? this->len : i.len;
		}
		// 等于 
		Integer &operator=(Integer i){
			this->~Integer();
			copy(i);
			return *this;
		}
		// 加法运算
		Integer operator+(Integer i){
			
			if(empty() || i.empty()){
				Integer it(empty() ? i : *this);
				return it;
			}
			
			Integer it(cmpMax(i) + 1);
			
			bool flag = false;
			bool a,b;
			int tl = this->len;
			int il = i.len;
			register int tu,iu;
						
			// 初始化第一个加数	
			for(tu = 0; tu < tl; tu ++){
				it.pointer[tu] = this->pointer[tu];
			}
			
			// 加上第二个加数 
			for(iu = 0; iu < il; iu ++){
				a = it.pointer[iu];
				b = i.pointer[iu];
				it.pointer[iu] = (a+b+flag)&1;
				flag = (flag && (a || b)) || (a && b);
			}

			// 若存在局部进位 
			while(flag){
				a = it.pointer[iu];
				it.pointer[iu] = a^flag;
				flag = (flag && a) || a;
				iu++;
			}
			
			// 若存在整体进位 
			it.len = it.pointer[it.size - 1] ? it.size : it.size - 1;
			
			return it;
		}
		// 乘法运算 
		Integer operator*(Integer i){
			
			if(empty() || i.empty()){
				Integer it;
				it.zero(true);
				return it;
			}
			
			Integer it(this->len + i.len);
			Integer t(this->len + i.len);
			
			// 优先分解较小的乘数 
			Integer *less,*more;
			
			if(this->len < i.len){
				less = this;
				more = &i;
			}else{
				less = &i;
				more = this;
			}
			
			bool a,b;
			bool flag;
			int tl = more->len;
			register int im = less->len - 1;
			register int tu,itu;
			
			// 高下标存储低位 
			tu = 0, itu = tl - 1;
			while(tu < tl){
				it.pointer[itu] = more->pointer[tu];
				tu ++,itu --;
			}
			it.len = im + tl;
			
			// 分解 
			while(im >= 0){
				if(less->pointer[im]){
					
					flag = false;
					
					itu = it.len - 1;
					tu = 0;
					
					// 对分配律各项做和 
					while(itu >= 0){
						a = it.pointer[itu];
						b = t.pointer[tu];
						t.pointer[tu] = (a+b+flag)&1;
						flag = (flag && (a || b)) || (a && b);
						itu--, tu++;
					}
					
					// 若存在局部进位 
					while(flag){
						a = t.pointer[tu];
						t.pointer[tu] = a^flag;
						flag = (flag && a) || a;
						tu++;
					}
					
				}
				im --;
				it.len --;
			}
			
			// 若存在整体进位 
			t.len = t.pointer[t.size - 1] ? t.size : t.size - 1;
			
			return t;
		}
};

相比于链串法，使用字节法明显代码看起来少了很多，但相对的所占用的存储空间也有所增大。对于一个非负整数 P ，若设[*] 为向上取整符号， S(*) 为对应类型的长度，可以表示为

所占的位空间大小约为 8*log2(P)。

测试

大整数加法

为检测这两个算法对大整数加法的计算效率，如可先分别生成长度为 1000 的大整数序列 A 和 B，然后依次进行加法运算，最后比较所使用的总时间。

若设 i 为大整数序列 A 或 B 的第 i 个大整数，则有

测试伪代码如下

void test(){
    
    Integer A,B,C;
    Time begin,end,Total = 0;
    
   	for([1..1000]){
        A,B = Random();
        
        {
        	begin = Now();
       		C = C + A + B;
        	end = Now();
        }
        
        A,B = zero();
        Total = Total + (end - begin);
    }
    
}

链串法

如图所示

一共耗费了 174ms。

字节法

如图所示

一共耗费了 120ms 。

可见若使用字节法约比使用链串法快了约 30% ，这也就是字节对指定位的位运算多消耗的时间。但字节法占用空间约为链串法的 8 倍可以根据实际情况斟酌选择。

大整数乘法

接下来是有关乘法的分析，可以和对大整数加法类似，先生成对应的序列 A 和 B 然后将加法运算换为乘法运算，但考虑到做累积可能会差异越来越大，故只计算序列 A 和 B 的乘积的平均时间。

测试伪代码如下

void test(){
    
    Integer A,B,C;
    Time begin,end,Total = 0;
    
   	for([1..1000]){
        A,B = Random();
        
        {
        	begin = Now();
       		C = A * B;
        	end = Now();
        }
        
        A,B = zero();
        Total = Total + (end - begin);
    }
    
    Total = Total / 1000;
    
}

链串法

如图所示

平均每次计算耗费 151ms 。

字节法

如图所示

平均每次计算耗费 94ms 。

可见字节法相比链串法快了约 37% ，相比加法运算乘法运算的差距更为明显一些。

大整数乘幂

对于大整数幂乘的测试，显然若使用随机数来进行测试，幂乘的结果会极大的拉开差异，因此该测试打算分别计算 100 以内质数以及部分数的 12345 次方，然后根据计算的时间进行比对。

测试伪代码如下

void test(){
    
    Integer C;
    Integer S = {100以内质数} ∪ {10,100,1000,10000}
    Time begin,end;
    
   	for([i ∈ S]){
        
        C = i;
        
        {
        	begin = Now();
       		pow(C,12345);
        	end = Now();
        }
        
        C = zero();
        print(end - begin);
    }
    
}

同样的，再分别计算 100 以内合数的 12345 次方。

测试伪代码如下

void test(){
    
    Integer C;
    Integer S = {100以内合数}
    Time begin,end;
    
   	for([i ∈ S]){
        
        C = i;
        
        {
        	begin = Now();
       		pow(C,12345);
        	end = Now();
        }
        
        C = zero();
        print(end - begin);
    }
    
}

链串法

关于求质数幂次的的结果，如图所示

关于求合数幂次的结果，如图所示

字节法

关于求质数幂次的的结果，如图所示

关于求合数幂次的结果，如图所示

可见当计算的结果很大时，链串法由字节对指定位的多余运算造成的效率影响就很明显了。

由于链串法和字节法都使用上两节所述的求幂算法对求幂时乘法运算的数量进行了优化，且故影响时间的主要因素为基数的大小。同时，不难看出随着基数的增大，除了一些特殊的数，如恰好为 2 的多次方，或存在 2 的多次方的因子时计算的速度相较周围其他数要快一些外，在 100 以内的合数和质数计算时间的增量较为平均。

若能申请到位空间，就可以节省开辟多余空间的时间，还会更快一些。

附录

上述的两个方法都是基于 C++ 的类实现的，若单纯靠结构和对应的函数来实现会不会快一些呢，经过测试并没有很明显的差异，反而在测试结果中，有多数结果所用耗时比用类进行包装效率还慢一些。

以下是用结构和函数实现的字节法

#define BYTE_C 1
#define INT_DEFAULT_SIZE 100
typedef unsigned char BYTE;

struct Int{
	int size;
	int len;
	unsigned char *pointer;
};

// 判断是否位空 
bool i_Empty(Int *t){
	return t == NULL || t->pointer == NULL || t->len == 0 || t->size == 0;
}

// 清除 
void i_Del(Int *t){
	if(t->pointer != NULL){
		free(t->pointer);
		t->pointer = NULL;
		t->len = t->size = 0;
	}
}

// 设为 "0" 或归 "0"
void i_Zero(Int *t, bool del){
	if(del){
		i_Del(t);
		t->pointer = (BYTE*)calloc(1,BYTE_C);
		t->len = t->size = 1;
	}else{
		t->len = 0;
	}
}

// 获取两数位最大长度 
int i_Cmp(Int *a, Int *b){
	return a->len > b->len ? a->len : b->len;
}

// 扩容
void i_Expand(Int *t){
	int newLen = t->size > 2048 ? t->size += 1024 : t->size * 2;
	t->pointer = (BYTE*)realloc(t->pointer,BYTE_C*newLen);
	for(register int i = t->len;i < newLen; i++){
		t->pointer[i] = 0;
	}
	t->size = newLen;
}

// 转换为二进制串
char *i_Bin(Int *t){
			
	if(i_Empty(t)) return NULL;
			
	register int tu = 0;
	register int sp = t->len;
	char *s = (char*)malloc(sizeof(char)*(sp+1));
			
	s[sp--] = '\0';
	while(sp >= 0){
		s[sp] = t->pointer[tu] + '0';
		tu++,sp--;
	}
			
	return s;
}

// 长整数类型转换(64bits)
void i_Dex2i(Int *t, long long int i){

	register int tu = 0;
	while(i > 0){
		while(tu > t->size)
			i_Expand(t);
		t->pointer[tu] = i & 1;
		tu++;
		i >>= 1;
	}
	t->len = tu;
}

Int *i_Init(){
	Int *i = (Int*)malloc(sizeof(Int));
	i->len = 0;
	i->size = INT_DEFAULT_SIZE;
	i->pointer = (BYTE*)calloc(INT_DEFAULT_SIZE,BYTE_C);
	return i;
}

Int *i_Init(int n){
	Int *i = (Int*)malloc(sizeof(Int));
	i->len = 0;
	i->size = n;
	i->pointer = (BYTE*)calloc(n,BYTE_C);
	return i;
}

Int *i_Init(Int *c){
	if(c == NULL) return NULL;
	Int *i = (Int*)malloc(sizeof(Int));
	i->len = c->len;
	i->size = c->size;
	i->pointer = (BYTE*)calloc(i->size,BYTE_C);
	for(register int t = 0; t < i->len ; t++)
		i->pointer[t] = c->pointer[t];
	return i;
}

// 加法运算 
Int *i_Add(Int *t, Int *i){
	
	if(i_Empty(t) || i_Empty(i)){	
		Int *it = i_Init(i_Empty(t) ? i : t );
		return it;
	}
			
	Int *it = i_Init(i_Cmp(t,i) + 1);
	
	bool flag = false;
	bool a,b;
	
	int tl = t->len;
	int il = i->len;
	
	register int tu,iu;
	
	for(tu = 0; tu < tl; tu++){
		it->pointer[tu] = t->pointer[tu];
	}
	
	for(iu = 0; iu < il; iu++){
		a = it->pointer[iu];
		b = i->pointer[iu];
		it->pointer[iu] = (a+b+flag) & 1;
		flag = (flag && (a || b)) || (a && b);
	}
	
	while(flag){
		a = it->pointer[iu];
		it->pointer[iu] = a^flag;
		flag = (flag && a) || a;
	}
	
	it->len = it->pointer[it->size - 1] ? it->size : it->size - 1;
	return it;
}

// 乘法运算 
Int *i_Multi(Int *p, Int *q){
	
	if(i_Empty(p) || i_Empty(q)){
		Int *it = i_Init();
		i_Zero(it,true);
		return it;
	}
	
	Int *it = i_Init(p->len + q->len);
	Int *t = i_Init(p->len + q->len);
	
	Int *ts, *i;
	if(p->len < q->len){
		ts = q;
		i = p;
	}else{
		ts = p;
		i = q;
	}
	
	bool a,b;
	bool flag;

	int tl = ts->len;
	register int im = i->len - 1;
	register int tu,itu;
			
	tu = 0, itu = tl - 1;
	while(tu < tl){
		it->pointer[itu] = ts->pointer[tu];
		tu ++,itu --;
	}
	it->len = im + tl;

	while(im >= 0){
		if(i->pointer[im]){
			flag = false;
					
			itu = it->len - 1;
			tu = 0;
			while(itu >= 0){
				a = it->pointer[itu];
				b = t->pointer[tu];
				t->pointer[tu] = (a+b+flag)&1;
				flag = (flag && (a || b)) || (a && b);
				itu--, tu++;
			}
					
			while(flag){
				a = t->pointer[tu];
				t->pointer[tu] = a^flag;
				flag = (flag && a) || a;
				tu++;
			}
					
		}
		im --;
		it->len --;
	}
	
	t->len = t->pointer[t->size - 1] ? t->size : t->size - 1;
	free(it);
	return t;
		
}

后话

就是说，上述的所有内容，纯属个人无聊的臆想，没有用足够大的测试集测试过，仅能保证在测试章节中所有数据的正确。无法保证理论、其他未测试结果的正确性！然后，该滚去捣鼓合约了！

如果您喜欢此博客或发现它对您有用，则欢迎对此发表评论。也欢迎您共享此博客，以便更多人可以参与。如果博客中使用的图像侵犯了您的版权，请与作者联系以将其删除。谢谢！

学习笔记 - 关于非负大整数计算的一些想法

关于大非负整数计算的一些想法

前言

绪论（瞎扯）

理论

简单加法

简单乘法

幂次乘法

应用

求幂算法

猜想

实现

链串法

字节法

测试

大整数加法

链串法

字节法

大整数乘法

链串法

字节法

大整数乘幂

链串法

字节法

附录

后话

标签

朋友们