大数处理-1

发表于 2020-12-29 更新于 2021-01-10 分类于 1- 编程相关，数据结构与算法阅读次数： 11 Valine：

对于 Java 这种对于数据类型占用空间有明确规定的语言（相较来说 Python 不规定数据类型占用的存储空间，会根据赋值数据自动分配），需要特别注意大数越界问题。很多时候，因为数据大小超出了声明类型允许的范围而造成的错误，程序不会报告任何异常，因而需要编程者格外小心。

1. 基础知识

对于Java 来说，它的各个数据类型在内存中占用的空间是固定的。总结如下：

数据类型	存储空间大小	描述
byte	1 byte	范围：-128 to 127
short	2 bytes	范围：-32,768 to 32,767
int	4 bytes	范围：-2,147,483,648 to 2,147,483,647
long	8 bytes	范围：-9,223,372,036,854,775,808 to 9,223,372,036,854,775,807
float	4 bytes	存储小数，可存储7位小数，保证6位小数精度
double	8 bytes	存储小数，可存储16位小数，保证15位小数精度
boolean	1 bit*(see ref)	存储 true or false。ref
char	2 bytes	存储单个字符

对于最常用的整型（int）来说，它的最大和最小值都是一个最高位为2的10位数。

为了使得大数不越界，通常的一个做法是对 1,000,000,007 取余数，1,000,000,007 是一个质数，并且在int 范围内。选择该数的原因大致有如下两点（Ref: 为什么要对1000000007取模）：

int32位的最大值为2147483647，所以对于int32位来说1000000007足够大;
int64位的最大值为2^63-1，对于1000000007来说它的平方不会在int64中溢出。

对于大数越界问题，常见的处理思路有两种，包括循环求余法和快速幂求余法。

1.1 循环求余法

对于加法来说，有如下求余运算规则：设正整数 x, y, p，求余符号为 $⊙$ ，则有 $(x + y) ⊙ p = (x ⊙ p + y ⊙ p) ⊙ p$ 。

我们看斐波那契数列的递归求解，根据以上规则，可推出 $f (n) ⊙ p = [f (n - 1) ⊙ p + f (n - 2) ⊙ p] ⊙ p$ ，从而可以在循环过程中每次计算 $s u m = (a + b) ⊙ 1000000007$ ，此操作与最终返回前取余等价。

对于乘法来说，循环求余法基于下述公式（前提条件 $x < p, x ⊙ p = x$ ）：

$x^{a} ⊙ p = [(x^{a - 1} ⊙ p) (x ⊙ p)] ⊙ p = [(x^{a - 1} ⊙ p) x] ⊙ p$

因而，我们可以循环操作求取 $x^{1}, x^{2}, x^{3} \dots x^{a}$ 对于 p 的余数。保证每轮中间的余数都在 int32 的范围之内。余数 remainder 可以使用下述代码来计算： rem = (rem * x) % p;。

Note: 这个算法需要满足 (x * p) 在用于存储它的数据类型的范围之内，也就是说，实际上 rem 需要存储为 long 类型。

该算法的时间复杂度为 O(N)。

1.2 快速求幂法

该方法的的效率更高，时间复杂度为 $O (l o g n)$ 。它基于如下的幂运算公式：

$x^{a} ⊙ p = (x^{2})^{a / 2} ⊙ p = (x^{2} ⊙ p)^{a / 2} ⊙ p$

由于指数可能为奇数或偶数，我们分情况进行讨论，当 a 为偶数时：

$x^{a} ⊙ p = (x^{2} ⊙ p)^{a / / 2} ⊙ p$

当 a 为奇数时（// 表示除法时向下取整）：

$x^{a} ⊙ p = [x (x^{2} ⊙ p)^{a / / 2}] ⊙ p$

因而对于输入指数 a, 底数 x, 模 p, 额外乘子 rem, ((rem * x^a) % p) 等价于求解：

(a 为偶数) 底数为 x ** 2, 指数为 a//2, 额外乘子不变，即 (rem * ((x**2)%p)^(a//2)) % p
(a 为奇数) 底数为 x ** 2, 指数为 a//2, 额外乘子为 (rem * x) % p, 即 ((rem * x) % p) * ((x**2)%p)^(a//2) % p。
更新：额外乘子 if(a % 2 == 1) rem = (rem * x) % p;, 指数 a = a//2;, 底数 x = x**2 % p;，更新后再次进入循环。
每一次更新，可以保证 x < p 的前提下，指数 a 变为原先的 1/2。循环结束条件：a == 0。

2. 例子

2.1 斐波那契数列

Leetcode斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

由于使用动态规划求解，每一个过程量在程序执行过程中都需要出现，因此，需要保证所有的这些量都不能超出规定的数值范围，循环求余法因而最为适合。具体的，我们在每一步向前推进的过程中进行大数越界的处理 - %1,000,000,007。由于 1,000,000,007 * 2 仍然在 int 的规定范围之内，所以当每个值都小于 1,000,000,007 时，两个值的和也一定在 int 的范围之内。

故而有如下代码：

class Solution {
    public int fib(int n) {
        // 初始状态
        int pre1 = 0, pre2 = 1, sum;
        for(int i = 0; i < n; ++i){
            // 状态转移条件
            sum = (pre1 + pre2)%1000000007;
            // 状态转移处理
            pre1 = pre2;
            pre2 = sum;
        }
        // 返回
        return pre1;
    }
}

2.2 剪绳子问题

Leetcode-剪绳子问题

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

根据数学理论，优先将绳子分为长度为 3 的段，得到的乘积最大。在这里，我们默认这一陈述的正确性，从而将重点放置到大数越界的处理上。

由于是乘法的越界问题，分析中，我们知道使用快速求幂法可以获得更优的时间复杂度。具体的，我们首先将模3余1，余2，余3 三种情况进行统一，都需要至少计算 3 的 n/3 -1 次方。然后，根据总结中的步骤，进行快速幂求解，其中，底数初始值为 3，指数初始值为 n/3 -1, 额外乘子初始值为 1。

class Solution {
    final int MOD = 1000000007;
    public int cuttingRope(int n) {
        if(n <= 2) return 1; 
        if(n == 3) return 2;
        int exp = n/3 -1;
        // 当 n = 4, n = 5 的时候，因为 n/3 - 1 == 0, 
        // 会造成后面return 处多乘一个3， 所以这里对 x 赋值的时候进行一个判断 
        long rem = 1, x = exp > 0 ? 3:1;
        
        while(exp > 1){
            if(exp % 2 == 1) rem = (rem * x) % MOD;
            x = (x *x) % MOD;
            exp = exp/2;
        }
        if(n % 3 == 0) return (int)(((rem*x) * 3) % MOD);
        if(n % 3 == 1) return (int)(((rem*x) * 4) % MOD);
        return (int)(((rem*x) * 6) % MOD);
    }
}

上述代码中，有一处可以优化中，当 exp == 1时，可以再多进行一次循环，将 x 的值归到 rem 中去。这样做之后，在 return 时，由于不再需要 x，故 x 赋值时的判断也可以省去。当然，这样的做法也有一个代价，就是在 exp == 1 的时候，会多做一次 x * x 的无用乘法。(ref)。

如下：

class Solution {
    final int MOD = 1000000007;
    public int cuttingRope(int n) {
        if(n <= 2) return 1; 
        if(n == 3) return 2;
        int exp = n/3 -1;
        // 当 n = 4, n = 5 的时候，因为 n/3 - 1 == 0, 
        // 会造成后面return 处多乘一个3， 所以这里对 x 赋值的时候进行一个判断 
        long rem = 1, x = 3;
        
        while(exp > 0){
            if(exp % 2 == 1) rem = (rem * x) % MOD;
            x = (x *x) % MOD;
            exp = exp/2;
        }
        if(n % 3 == 0) return (int)((rem * 3) % MOD);
        if(n % 3 == 1) return (int)((rem * 4) % MOD);
        return (int)((rem * 6) % MOD);
    }
}