整数快速幂, 矩阵加速, 矩阵快速幂超详细讲解

2023-11-13 19:37:34

本文出自我的掘金博客, 欢迎访问传送门

小布曰: 这次分享的算法有些偏数论, 不过你也不要被数论吓到哈, 在离散数学中, 初等数论的内容是相对而言简单的内容, 好的, 废话不多说了, 下面来步入正题

一, 整数快速幂

1. 简介

该算法就是让计算机更快的求出 aba^bab 的值的一个算法, 如果采用暴力算法, 那么计算机需要计算 bbb 次, 如果 bbb 很大的话, 那么时间复杂度是很大的, 但如果采用 快速幂算法, 时间复杂度就是 O(logb)O(logb)O(logb) 级别的, 怎么样, 是不是很心动呢?

2. 原理

这种算法之所以这么快, 是因为它符合计算机的思维, 它利用了二进制.

举个例子: 十进制的数11 可以换算成二进制的数 (1011)2(1011)_2(1011)2​, 从左到右, 这些1分别代表十进制中的 $ 8 $, $ 2 $, 111, 所以 a11a^{11}a11 === $ a^{8+2+1} $ === a8∗a2∗a1a^8*a^2*a^1a8∗a2∗a1.

好的, 有了上面的例子帮助理解, 下面我们直接叙述快速幂算法的原理:

  1. 如果将 aaa 自乘一次, 那么会得到 a2a^2a2, 再自乘一次, 会得到 a4a^4a4, …\dots…, 自乘 nnn 次, 我们会得到 a2na^{2n}a2n.
  2. ax+ya^{x+y}ax+y === ax∗aya^x*a^yax∗ay
  3. 一个十进制数 bbb 有一个唯一的二进制数与之对应

这三条原理的正确性应该不需要证明吧!

3. 算法流程

对于一个幂 aba^bab.

  1. 将 bbb 写成二进制数的形式
  2. 定义一个基底 basebasebase === aaa, 定义一个储存结果的变量 ansansans === 111.
  3. 从右至左遍历 bbb 的二进制位, 如果该位是 111, 则 ansansans = ansansans ∗*∗ basebasebase, 若该位为 000, 则不对 ansansans 进行处理. 无论该位为什么, 始终有 basebasebase = base2base^2base2.
  4. 遍历结束, 输出 ansansans

举一个实际的例子吧, 以 2132^{13}213 举例吧

  1. bbb = (1101)2(1101)_2(1101)2​

  2. 定义一个基底 basebasebase === 222, ansansans === 111.

  3. 从右至左遍历 bbb

    3.1 遇到 111, ansansans === 111 ∗*∗ 222 = 222, basebasebase = 222^222 = 444

    3.2 遇到 000, ansansans 不变, basebasebase = 424^242 = 161616

    3.3 遇到 111, ansansans = 222 ∗*∗ 161616 = 323232, basebasebase = 16216^2162 = 256256256

    3.4 遇到 111, ansansans = 323232 * 256256256 = 819281928192, 遍历完毕 □\square□

  4. 输出 ansansans === 819281928192

相信您现在已经掌握了整数快速幂了叭

二, 矩阵加速

1. 简介

这是一个很神奇的算法, 比如说给定你一个递推关系式, 然后要你求第 nnn (nnn是很大的一个数) 项的值, 如果你纯粹递推的话, 肯定很慢, 但是用了矩阵加速之后就变得飞快.

比如说对于斐波那契数列, f[n]=f[n−1]+f[n−2]f[n]=f[n-1]+f[n-2]f[n]=f[n−1]+f[n−2], 要你求第 nnn 项的值

很多人也写过类似的博客, 是那种找规律一样的, 我不喜欢这样做, 下面我来谈一谈我的做法, 如何快速找到转移矩阵

首先进行一个简单的数学推导, 相信大家都看得懂, 以后碰到类似的也可以这样做, 很容易找到转移矩阵哒

(anan−1)\begin{pmatrix} a_n & a_{n-1} \end{pmatrix}(an​​an−1​​) === (an−1+an−2an−1)\begin{pmatrix} a_{n-1} + a_{n-2} & a_{n-1} \end{pmatrix}(an−1​+an−2​​an−1​​) === (an−1an−2)\begin{pmatrix} a_{n-1} & a_{n-2} \end{pmatrix}(an−1​​an−2​​) ∗*∗ (1110)\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}(11​10​) === (a2a1)\begin{pmatrix} a_2 & a_1 \end{pmatrix}(a2​​a1​​) ∗*∗ (1110)n−2\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-2}(11​10​)n−2

LATEXL^AT_EXLATE​X 的矩阵是真的难打(小声bb

式子推出来了, 剩下的矩阵快速幂一阵乱锤就行, 下面介绍矩阵快速幂

三, 矩阵快速幂

1. 简介

不知道各位学习过线性代数 没有, 矩阵是线代里面一个非常重要的知识, 如果有的童鞋没有学习或者过了太久忘了的话, 我可以帮您回顾一下相关的重要知识点

我实在不想打矩阵了, 这里无关紧要的就用文字描述一下吧

1. 加法运算

要求: 同型矩阵, 即两个矩阵的规模一样, 都是 m∗nm*nm∗n.

操作: 将两个矩阵对应位置的数相加即可

2. 减法操作

就是加法的逆运算, 不再赘述

3. 数乘操作

要求: 一个数乘以一个矩阵

操作: 将矩阵的每一个位置的元素都乘以这个数

4. 重头戏 , 敲重点, 矩阵乘法

矩阵乘以一个矩阵
要求: 矩阵A * 矩阵B, 必须要求, 矩阵A的规模为 m∗nm*nm∗n, 则 B的规模为 n∗kn*kn∗k, 即A的列数等于B的行数

操作: 如下图所示(打矩阵太累了

整数快速幂, 矩阵加速, 矩阵快速幂超详细讲解

矩阵乘法满足结合律哟

有了上面的知识储备后, 你会发现, 又回到了最初的快速幂的问题, 只不过现在不是两个整数相乘, 而是两个矩阵相乘, 所以我们只需重载一下 ∗*∗ 运算符, 其他的与整数快速幂没有什么大的区别了

1. 数据结构

struct Mat {
    ll m[MAXN][MAXN];
    //构造函数, 将矩阵所有元素都初始化为0
    Mat() {
        memset(m, 0, sizeof(m));
    }
    
    //调用这个函数即可初始化为单位矩阵
    void build () {
        for (int i = 1; i <= n; i++) {
            m[i][i] = 1;
        }
    } 
};

单位矩阵就是左上角到右下角的对角线上的元素为1, 其他均为0的矩阵

重载运算符 ∗*∗

Mat operator* (const Mat& a, const Mat& b) {
    Mat c;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                c.m[i][j] = c.m[i][j] + a.m[i][k] * b.m[k][j];
            }
        }
    }

    return c;
}

快速幂主体

while (k > 0) {
    if (k & 1) {
        ans = ans * mat;
    }
    mat = mat * mat;
    k >>= 1;
}

注意, 这里不能使用 *= 运算符, 因为没有重载

接下来就大功告成啦

码字不易, 如果这篇文章能帮助到您的话, 就请点个赞再走呗, 您的一个赞将是对我的极大鼓励, _!
整数快速幂, 矩阵加速, 矩阵快速幂超详细讲解整数快速幂, 矩阵加速, 矩阵快速幂超详细讲解 汪阿少二少 发布了8 篇原创文章 · 获赞 0 · 访问量 115 私信 关注
上一篇：学习笔记(01):理解JavaScript中的闭包-什么是闭包


下一篇：实现Dictionary、NumericDictionary