当前位置: 首页 > 编程笔记 >

Java语言实现快速幂取模算法详解

刘承悦
2023-03-14
本文向大家介绍Java语言实现快速幂取模算法详解,包括了Java语言实现快速幂取模算法详解的使用技巧和注意事项,需要的朋友参考一下

快速幂取模算法的引入是从大数的小数取模的朴素算法的局限性所提出的,在朴素的方法中我们计算一个数比如5^1003%31是非常消耗我们的计算资源的,在整个计算过程中最麻烦的就是我们的5^1003这个过程

缺点1:在我们在之后计算指数的过程中,计算的数字不都拿得增大,非常的占用我们的计算资源(主要是时间,还有空间)

缺点2:我们计算的中间过程数字大的恐怖,我们现有的计算机是没有办法记录这么长的数据的,所以说我们必须要想一个更加高效的方法来解决这个问题

当我们计算AB%C的时候,最便捷的方法就是调用Math函数中的pow方法,但是有时A的B次方数字过大,即使是双精度的double也会溢出,这个时候为了得到AB%C的结果,我们会选择使用快速幂取模算法,简单快速的得到我们想要的结果。

为了防止数字溢出并且降低复杂度,我们需要用到下面的公式:

ab mod c = (a mod c)b mod c

这个公式的意思就是:积的取余等于取余的积的取余。很容易看出来这个公式是具有传递性的,这样我们可以通过不断的取余让a越来越小,防止出现溢出的情况。

理论上,有了这个公式我们就可以写代码了,通过不断的对a进行取模保证结果不会溢出,这确实能计算出较大次方的幂的模,但是这种方法的复杂度仍旧是O(N),并不快速。

为了更快速的计算出幂的模,我们还要依赖下面这个公式:

ab mod c = (a2)b/2 mod c , b为偶数
ab mod c = ((a2)b/2·a) mod c , b为奇数

这个公式很简单,原理就是不断的用a的平方来代替b,将b替换为原来的一半。因为我们通过第一个公式知道了一个数的模的相同次方的模相同(这句话说的有点绕,就是公式一的意思)。那么我们用a*a%c的结果来代替a效果是一样的。

所以根据上述的公式,我们得到复杂度O(logN)这样的计算快速幂的方法:

import java.util.Scanner;

public class Main {

 public static void main(String[] args) {
  Scanner in = new Scanner(System.in);
  int a = in.nextInt(), b = in.nextInt(), c = in.nextInt();
  int res = 1;
  a %= c;
  for (; b != 0; b /= 2) {
   if (b % 2 == 1)
    res = (res * a) % c;
   a = (a * a) % c;
  }
  System.out.println(res);
 }
}

这个算法大概如此,第一步先a%=c是为了将a缩小一些,防止在for中第一次进行a*a的时候数字溢出。在for循环中,如果是b为奇数则令res=res*a,直接先将a乘到结果中去,最后做处理,又是为了防止数字溢出直接将res*a的结果mod c操作。这个for循环中,早晚有一天b会等于1,进入if分支,最后将res的值计算完毕mod c退出for循环,的到最后的结果。

总结

以上就是本文关于Java语言实现快速幂取模算法详解的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

 类似资料:
  • 本文向大家介绍java实现快速排序算法,包括了java实现快速排序算法的使用技巧和注意事项,需要的朋友参考一下 1、算法概念。 快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。 2、算法思想。 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序

  • 本文向大家介绍Javascript实现快速排序(Quicksort)的算法详解,包括了Javascript实现快速排序(Quicksort)的算法详解的使用技巧和注意事项,需要的朋友参考一下 目前,最常见的排序算法大概有七八种,其中"快速排序"(Quicksort)使用得最广泛,速度也较快。它是图灵奖得主C. A. R. Hoare(1934--)于1960时提出来的。 "快速排序"的思想很简单,

  • Java 是一种高级的编程语言,它最初是由 Sun 公司开发并于 1995 年公开发布的。Java 可以在不同的平台上运行,例如:Windows,Mac OS 和不同版本的 Unix。本指南将让你对 Java 有一个彻底的认识与了解。

  • 本文向大家介绍C语言快速实现扫雷小游戏,包括了C语言快速实现扫雷小游戏的使用技巧和注意事项,需要的朋友参考一下 本文实例为大家分享了C语言扫雷小游戏的具体实现代码,供大家参考,具体内容如下 一、分析游戏步骤: 具体步骤如图: 二、代码实现: 游戏步骤想好之后,就是用代码把步骤一步一步的实现。具体代码如下: 1、游戏主要实现: game.c 2、游戏源文件:main.c 代码如下: 3、游戏头文件:

  • [简短的回答:糟糕的基准测试方法。你会认为我现在已经明白了。] 该问题被提出为“快速计算x^y的方法,其中x和y是正整数”。典型的“快速”算法如下所示: 我想知道这比调用math.pow()或者使用简单的方法比如将x乘以y要快多少,如下所示: 使用随机数和试验的参数确实会改变输出特性,但试验之间的比率总是与所示的一致。

  • 本文向大家介绍PHP 快速排序算法详解,包括了PHP 快速排序算法详解的使用技巧和注意事项,需要的朋友参考一下 概念 这里借用百度百科的一张图来,非常形象: 快速排序算法是对冒泡算法的一个优化。他的思想是先对数组进行分割, 把大的元素数值放到一个临时数组里,把小的元素数值放到另一个临时数组里(这个分割的点可以是数组中的任意一个元素值,一般用第一个元素,即$array[0]),然后继续把这两个临时数