快捷導(dǎo)航

Java語言實現(xiàn)快速冪取模算法詳解

更新時間：2017年11月29日 10:23:31 作者：QuinnNorris

這篇文章主要介紹了Java語言實現(xiàn)快速冪取模算法詳解，具有一定參考價值，需要的朋友可以了解下。

快速冪取模算法的引入是從大數(shù)的小數(shù)取模的樸素算法的局限性所提出的，在樸素的方法中我們計算一個數(shù)比如5^1003%31是非常消耗我們的計算資源的，在整個計算過程中最麻煩的就是我們的5^1003這個過程

缺點1：在我們在之后計算指數(shù)的過程中，計算的數(shù)字不都拿得增大，非常的占用我們的計算資源（主要是時間，還有空間）

缺點2：我們計算的中間過程數(shù)字大的恐怖，我們現(xiàn)有的計算機是沒有辦法記錄這么長的數(shù)據(jù)的，所以說我們必須要想一個更加高效的方法來解決這個問題

當(dāng)我們計算A^B%C的時候，最便捷的方法就是調(diào)用Math函數(shù)中的pow方法，但是有時A的B次方數(shù)字過大，即使是雙精度的double也會溢出，這個時候為了得到A^B%C的結(jié)果，我們會選擇使用快速冪取模算法，簡單快速的得到我們想要的結(jié)果。

為了防止數(shù)字溢出并且降低復(fù)雜度，我們需要用到下面的公式:

a^b mod c = (a mod c)^b mod c

這個公式的意思就是：積的取余等于取余的積的取余。很容易看出來這個公式是具有傳遞性的，這樣我們可以通過不斷的取余讓a越來越小，防止出現(xiàn)溢出的情況。

理論上，有了這個公式我們就可以寫代碼了，通過不斷的對a進行取模保證結(jié)果不會溢出，這確實能計算出較大次方的冪的模，但是這種方法的復(fù)雜度仍舊是O(N)，并不快速。

為了更快速的計算出冪的模，我們還要依賴下面這個公式：

a^b mod c = (a²)^b/2 mod c , b為偶數(shù)
a^b mod c = ((a²)^b/2·a) mod c , b為奇數(shù)

這個公式很簡單，原理就是不斷的用a的平方來代替b，將b替換為原來的一半。因為我們通過第一個公式知道了一個數(shù)的模的相同次方的模相同（這句話說的有點繞，就是公式一的意思）。那么我們用a*a%c的結(jié)果來代替a效果是一樣的。

所以根據(jù)上述的公式，我們得到復(fù)雜度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的時候數(shù)字溢出。在for循環(huán)中，如果是b為奇數(shù)則令res=res*a，直接先將a乘到結(jié)果中去，最后做處理，又是為了防止數(shù)字溢出直接將res*a的結(jié)果mod c操作。這個for循環(huán)中，早晚有一天b會等于1，進入if分支，最后將res的值計算完畢mod c退出for循環(huán)，的到最后的結(jié)果。

總結(jié)

以上就是本文關(guān)于Java語言實現(xiàn)快速冪取模算法詳解的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！

您可能感興趣的文章: