快捷導(dǎo)航

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

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

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

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

缺點(diǎn)1：在我們?cè)谥笥?jì)算指數(shù)的過(guò)程中，計(jì)算的數(shù)字不都拿得增大，非常的占用我們的計(jì)算資源（主要是時(shí)間，還有空間）

缺點(diǎn)2：我們計(jì)算的中間過(guò)程數(shù)字大的恐怖，我們現(xiàn)有的計(jì)算機(jī)是沒(méi)有辦法記錄這么長(zhǎng)的數(shù)據(jù)的，所以說(shuō)我們必須要想一個(gè)更加高效的方法來(lái)解決這個(gè)問(wèn)題

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

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

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

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

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

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

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

這個(gè)公式很簡(jiǎn)單，原理就是不斷的用a的平方來(lái)代替b，將b替換為原來(lái)的一半。因?yàn)槲覀兺ㄟ^(guò)第一個(gè)公式知道了一個(gè)數(shù)的模的相同次方的模相同（這句話說(shuō)的有點(diǎn)繞，就是公式一的意思）。那么我們用a*a%c的結(jié)果來(lái)代替a效果是一樣的。

所以根據(jù)上述的公式，我們得到復(fù)雜度O（logN）這樣的計(jì)算快速冪的方法：

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);
 }
}

這個(gè)算法大概如此，第一步先a%=c是為了將a縮小一些，防止在for中第一次進(jìn)行a*a的時(shí)候數(shù)字溢出。在for循環(huán)中，如果是b為奇數(shù)則令res=res*a，直接先將a乘到結(jié)果中去，最后做處理，又是為了防止數(shù)字溢出直接將res*a的結(jié)果mod c操作。這個(gè)for循環(huán)中，早晚有一天b會(huì)等于1，進(jìn)入if分支，最后將res的值計(jì)算完畢mod c退出for循環(huán)，的到最后的結(jié)果。

總結(jié)

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

您可能感興趣的文章: