当前位置: 首页 > news >正文

【算法设计-分治】快速幂与龟速乘

文章目录

    • 1. 快速幂
    • 2. 龟速乘
    • 3. 快速幂取模
    • 4. 龟速乘取模
    • 5. 快速幂取模优化

1. 快速幂

算法原理:

  • 计算 311
    • 311 = (35)2 x 3
    • 35 = (32)2 x 3
    • 32 = 3 x 3
    • 仅需计算 3 次,而非 11 次
  • 计算 310
    • 310 = (35)2
    • 35 = (32)2 x 3
    • 32 = 3 x 3
    • 仅需计算 3 次,而非 10 次

算法思路:

  • 若指数是偶数,则将底数平方,指数除以 2。
  • 若指数是奇数,则将底数平方,指数除以 2,再乘上底数。

算法代码:

typedef unsigned long long uLL;// 快速幂 a^b
uLL power (uLL a, uLL b){uLL r = 1;while (b != 0){if (b & 1) 	// (b % 2 == 1)r = r * a;b = b >> 1; // (b = b / 2)a = a * a;}return r;
}

举例:

  • 初始值:a = 3,b = 11
  • 第 1 轮:(11 % 2 == 1)r=1x3=3,b=5,a=32=9
  • 第 2 轮:(5 % 2 == 1)r=3x32=33=27,b=2,a=(32)2=34=81
  • 第 3 轮:(2 % 2 == 0)r 不变,b=1,a=(34)2=38
  • 第 4 轮:(1 % 2 == 1)r=33x38=311,b=0,a=(38)2=316
  • 得到 r = 33x38 = 311

2. 龟速乘

算法原理:将其中一个乘数分解成 2 的幂次相加。

12 x a = 23 x a + 21 x a

算法代码:

typedef unsigned long long uLL;// 龟速乘 a*b
uLL mul (uLL a, uLL b){uLL r = 0;while (b != 0){if (b & 1) 	// (b % 2 == 1)r = r + a;b = b >> 1; // (b = b / 2)a = a + a;}return r;
}

3. 快速幂取模

初等数论中有如下公式:

(a × b) % m = ((a % m) × (b % m)) % m

推广:

(a × b × c…) % m = ((a % m) × (b % m) × (c % m) × … ) % m

(ab) % m = (a × a × a…) % m = ((a % m) × (a % m) × (a % m) × … ) % m

算法代码:

typedef unsigned long long uLL;// 快速幂取模 (a^b) % p
uLL powerMod (uLL a, uLL b, uLL p){uLL r = 1;while (b != 0){if (b & 1) 	// (b % 2 == 1)r = (r * a) % p;b = b >> 1; // (b = b / 2)a = (a * a) % p;}return r;
}

4. 龟速乘取模

算法原理:(a × b) % m = ((a % m) × (b % m)) % m

算法代码:

// 龟速乘取模 (a*b) % p
uLL mulMod (uLL a, uLL b, uLL p){uLL r = 0;while (b != 0){if (b & 1) 	// (b % 2 == 1)r = (r + a) % p;b = b >> 1; // (b = b / 2)a = (a + a) % p;}return r;
}

5. 快速幂取模优化

算法原理:注意到快速幂取模算法中的相乘操作可能会超出数据范围,因此可以将相乘操作转化为龟速乘取模。

原理依然是此公式:(a × b) % m = ((a % m) × (b % m)) % m,其中((a % m) × (b % m))即为龟速乘取模。

算法思路:快速幂 + 龟速乘结合。

// 快速幂取模防止爆炸 (a^b) % p
uLL powerModBig (uLL a, uLL b, uLL p){uLL r = 1;while (b != 0){if (b & 1) 	// (b % 2 == 1)r = mulMod(a, b, p) % p;b = b >> 1; // (b = b / 2)a = mulMod(a, a, p) % p;}return r;
}
http://www.lryc.cn/news/23051.html

相关文章:

  • 基于新一代kaldi项目的语音识别应用实例
  • 【GO】31.grpc 客户端负载均衡源码分析
  • PTA L1-058 6翻了(详解)
  • 【Origin科研绘图】如何快速绘制一个折线图 ||【前端特效】爱心篇 之 幸好有你 || 泰坦尼克号——乘客生存与否 预测 || PyCharm使用介绍
  • 一文解读电压放大器(电压放大器原理)
  • 线上监控诊断神器arthas
  • @Import注解的原理
  • 平台总线开发(id和设备树匹配)
  • TS泛型,原来就这?
  • 关于算法学习和刷题的建议
  • 2023年“网络安全”赛项浙江省金华市选拔赛 任务书
  • http协议简介
  • CSDN 第三十一期竞赛题解
  • EM_ASM系列宏定义(emscripten)
  • Batchnorm和Layernorm的区别
  • 高级前端面试题汇总
  • HTML#5表单标签
  • ONNX可视化与编辑工具
  • Verilog 学习第五节(串口接收部分)
  • AIX系统常见漏洞修复(exec、rlogin、rsh、ftp、telnet远端服务运行中)
  • IEEE SLT 2022论文丨如何利用x-vectors提升语音鉴伪系统性能?
  • 设计模式(十三)----结构型模式之桥接模式
  • 倾向得分匹配案例分析
  • 基于SpringCloud的可靠消息最终一致性04:项目基础代码
  • 操作系统权限提升(十八)之Linux提权-内核提权
  • 华为OD机试真题Java实现【快递运输】真题+解题思路+代码(20222023
  • java面试题-JVM问题排查
  • 市场上有很多低代码开发平台,不懂编程的人可以用哪些?
  • Tina_Linux打包流程说明指南_new
  • JVM面试题