首页 > 其他分享 >【知识点】快速幂与矩阵快速幂

【知识点】快速幂与矩阵快速幂

时间:2024-04-26 11:46:28浏览次数:23  
标签:知识点 exponent 矩阵 底数 long 算法 base 快速

什么是快速幂,为什么要使用快速幂?

Macw: 快速幂有好多好处。
Penelope: 例如?
Macw: 它比较快。

见名知意,快速幂算法可以在非常短的时间内求出一个数的 \(n\) 次幂。虽然快速幂在初学阶段的应用不算太多,但是快速幂背后的思想是非常值得我们去理解的。

举例而言,如果我们要求出 \(3^4\) 的值是多少?我们当然可以暴力求解 \(3 \times 3 \times 3 \times 3 = 81\)。如果要求出 \(3^{n}\) 是多少呢?暴力也还不为过...

暴算法力求解一个数的次幂的时间复杂度是 \(O(n)\)。如果我们要求解的次幂非常高的时候,那么速度就会变得非常慢。众所周知,普通64位测评机每秒也就能处理 \(10^8\) 左右的数据。因此我们需要找到一个更优的算法来解决这个问题。

快速幂算法的核心思想就是幂运算的乘法法则。

我们以求 \(3^{16}\) 为例,根据“同底次幂相乘,底数不变,指数相加的法则”,我们可以把问题看作成求解 \(3^{8} \times 3^{8}\) 的值。不难看出,这样的话我们只需要知道 \(3^8\) 的值,我们就可以快速求出 \(3^{16}\) 的值了,不再需要在 \(3^8\) 的基础上再乘 \(8\) 遍来得到最终结果。相同地,我们也可以以同样的方法快速求出 \(3^8\) 的值,这样子程序运行的速度将会大大减少:

再以计算 \(3^{16}\) 次方为例:

  1. 我们先计算 \(3^2\) 的值。
  2. 然后就可以立刻计算出 \(3^4\) 的值。
  3. 然后就又可以计算出 \(3^8\) 的值。
  4. 最后就能快速地计算出 \(3^{16}\) 的值了。

比较新的快速幂的算法和普通的暴力算法,可以看到原本需要运行 \(16\) 次的乘法运算现在只需要运算 \(4\) 次就可以计算出答案了。当数据量越大的时候,两个算法的速度差距就会越明显。(稍微学过初高等数学的人可以推断出快速幂算法的时间复杂度约为 \(O(log_2(n))\),对数时间复杂度远优于线性时间复杂度)。

快速幂算法的进一步拓展

然而,大家也都发现了,普通的快速幂算法只能解决要求解次幂为 \(2\) 的指数的情况(将代码稍做修改其实也可以解决所有以偶数作为次幂的情况)(例如:\(1, 2, 4, 8, \dots, 2^n\))。难道对于那些非 \(2\) 的指数倍的次幂就没有办法了吗?当然不是。

我们都知道,任意一个数字都可以被查分成多个 \(2\) 的次幂的和。

例如数字 \(34\),可以写成二进制形式 \(100100_{(Base\space2)}\)。那么 \(32\) 这个数字就可以被分解成 \(2^5 + 2^2\)。再根据幂运算的乘法法则,若要计算出任意数字 \(x^{34}\),只需要计算出 \(x^{2^5}\) 和 \(x^{2^2}\),即 \(x^{32}\) 和 \(x^{4}\) 就可以再按照之前的快速幂方法快速求解答案。

因此,对于求任意一个指数非 \(2\) 的次幂的值,我们可以将这个指数分解成多个 \(2\) 的次幂相加的和并依次求解出最后的答案即可。其中,这多个 \(2\) 的次幂的数字我们也可以通过普通的快速幂算法快速求得答案。

到目前为止,快速幂算法就迎刃而解了。

快速幂算法的代码以及实现

这个是 C++ 代码的快速幂模版:

这段代码通过递归求解问题,将一个大的次幂转变成两个小的次幂的积进行运算。

// 计算以 base 为底数的 exponent 次方的值
long long quick_power_recursive(int base, int exponent) {
    if (exponent == 0) 
        // 如果指数为0,返回1
        return 1;
    else if (exponent % 2 == 0) { 
        // 如果指数为偶数,递归计算底数的一半指数幂
        long long temp = quick_power_recursive(base, exponent / 2); 
        // 返回底数的一半指数幂的平方
        return temp * temp; 
    } else { 
        // 如果指数为奇数,递归计算底数的一半指数幂
        long long temp = quick_power_recursive(base, (exponent - 1) / 2); 
        // 返回底数乘以底数的一半指数幂的平方
        return base * temp * temp; 
    }
}

这个是经过位运算优化过后的快速幂模板:

// 计算以 base 为底数的 exponent 次方的值
long long quick_power(int base, int exponent) {
    // 初始化结果为 1
    long long result = 1; 
    // 当指数不为0时进行循环
    while (exponent) { 
        // 如果指数为奇数,将当前底数乘到结果中
        if (exponent & 1) 
            result *= base;  
        // 底数平方
        base *= base; 
        // 将指数右移一位,相当于除以 2
        exponent >>= 1; 
    }
    return result;  // 返回结果
}

矩阵快速幂 - 结束语

学过线性代数的同学们看过来!

快速幂算法不光可以求解普通的快速幂问题,我们还可以用同样的方法对一个任意大小的矩阵求快速幂。快速幂在矩阵乘法中的作用非常的大,普通的两个矩阵相乘的时间复杂度约为 \(O(n^3)\),其中 \(n \times n\) 为矩阵的大小。

\[Matrix = \begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,1} & a_{3,2} & a_{3,3} \end{bmatrix}^n \]

相比较普通快速幂,矩阵快速幂只需要重新定义乘法的运算规则即可。这里提供一个用结构体来重定义运算符的方法:

struct matrix{
    int a[5][5];
    matrix() { memset(a, 0, sizeof a); }
    matrix operator * (const matrix &b) const {
        matrix res;
        for (int i=1; i<=2; i++){
            for (int j=1; j<=2; j++){
                for (int k=1; k<=2; k++){
                    res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % MOD;
                }
            }
        }
        return res;
    }
} ans, base;

矩阵快速幂的一个常见应用场景就是动态规划,也就是我们常说的矩阵加速动态规划算法。有关这方面的知识我会在后期单独出一篇文章来详细讲解。

标签:知识点,exponent,矩阵,底数,long,算法,base,快速
From: https://www.cnblogs.com/Macw07/p/18159695

相关文章

  • ollama——快速上手Llama3部署使用
    ollama——快速上手Llama31.ollama安装#Linuxcurl-fsSLhttps://ollama.com/install.sh|sh#vi/etc/systemd/system/ollama.service[Unit]Description=OllamaServiceAfter=network-online.target[Service]ExecStart=/usr/local/bin/ollamaserveUser=ollamaGrou......
  • 如何3分钟,快速开发一个新功能
    背景关于为什么做这个代码生成器,其实主要有两点:参与的项目中有很多分析报表需要展示给业务部门,公司使用的商用产品,或多或少有些问题,这部分可能是历史选型导致的,这里撇开不不谈;项目里面也有很多CRUD的功能,而这些功能的实现代码基本上差不多,这些功能都去手写,也比较浪费时间而且......
  • 阿里云边缘容器云帮助AI推理应用快速落地
    近日,阿里云技术专家徐若晨在全球分布式云大会上,分享了《边缘容器云助力AI推理高效落地》的主题演讲,分享了阿里云边缘容器云如何助力开发者实现更快速的AI推理应用的迭代和部署。此外,他还分享了边缘AI推理应用在实际业务中的应用案例。 终端算力上移云端算力......
  • 矩阵树定理 BEST 定理
    矩阵树定理\(\text{BEST}\)定理证明很复杂,连\(\text{cmd}\)这种无敌神犇都不会,而且对定理本身的可扩展性几乎为\(0\),即每次套用的定理都跟模板一模一样。矩阵树无论任何情况,一定要不能有自环无论任何情况,一定要不能有自环无论任何情况,一定要不能有自环对于无向无权图,......
  • MinIO 常用 API 快速入门
    快速入门minio中文网minio官网minio有开源版和收费版,使用开源版时,若修改了minio的源代码,需要将修改后的源代码完全公开。启动miniominio文档提供了多个运行环境的安装流程,此处以windows为例,其它运行环境文档上都有介绍。相关文档下载minio.exe:https://dl.minio......
  • Redis 面试知识点
    1、Redis缓存数据库一致性采用最终一致性,而不是采用强一致性,强一致性会导致系统吞吐量变差;采用双删除的策略,第二次删除,采用延迟删除;推荐采用,先操作数据库,直接删除缓存的方式;删除失败的情况,采用异步方式,重试操作;读取binlog异步删除,使用开源框架canal,监听canal......
  • 矩阵树定理 BEST 定理
    矩阵树定理\(\text{BEST}\)定理证明很复杂,连\(\text{cmd}\)这种无敌神犇都不会,而且对定理本身的可扩展性几乎为\(0\),即每次套用的定理都跟模板一模一样。矩阵树无论任何情况,一定要不能有自环无论任何情况,一定要不能有自环无论任何情况,一定要不能有自环对于无向无权图,......
  • 洛谷题单指南-动态规划2-P1874 快速求和
    原题链接:https://www.luogu.com.cn/problem/P1874题意解读:一个数字字符串s,分解成几个整数,和为n,计算最少加号个数,也就是计算最少分解的整数个数-1。解题思路:此题虽然分类在动态规划,但数据量不大,DFS更加直观和易于理解,所以采用DFS暴搜+剪枝来解决。搜索思路是对数字字符串依次枚......
  • 快速入门
    快速入门‍为什么不用Pyqt6,非要用PySide6开发程序呢?因为PySide6是Qt官方维护的py库,Pyqt6如果用于商业需要购买许可证,而PySide6的LGPL许可证,允许商业、非商业、开源或非开源。当然,PyQt6和PySide6大部分函数是一致的,网上的PyQt教程也比较丰富,可以先练习PyQt,发布源码时转为PySide6......
  • 快速部署 微软开源的 Garnet 键值数据库
    快速部署微软开源的Garnet键值数据库Garnet是MicrosoftResearch推出的一种新型远程缓存存储,其设计速度极快、可扩展且延迟低。Garnet在单个节点内是线程可扩展的。它还支持分片集群执行、复制、检查点、故障转移和事务。它可以在主内存以及分层存储(例如SSD和Azure存......