L'introduction d'un algorithme de module de puissance rapide est proposée par les limites d'un algorithme naïf qui prend le module des décimales de grand nombre. Dans la méthode naïve, nous calculons un nombre tel que 5 ^ 1003% 31, qui consomme beaucoup nos ressources informatiques. La chose la plus gênante de tout le processus de calcul est notre processus 5 ^ 1003.
Inconvénient 1: Dans le processus de calcul de l'index ultérieur, les nombres calculés ne sont pas tous augmentés, ce qui reprend une grande partie de nos ressources informatiques (principalement le temps et l'espace)
Désavantage 2: Les nombres de notre calcul sont si importants que nos ordinateurs existants ne peuvent pas enregistrer des données aussi longues, nous devons donc penser à un moyen plus efficace de résoudre ce problème.
Lorsque nous calculons AB% C, le moyen le plus pratique est d'appeler la méthode POW dans la fonction mathématique. Cependant, parfois le nombre de A à la puissance de B est trop grand, et même le double de double précision débordera. Pour le moment, afin d'obtenir le résultat de AB% C, nous choisirons d'utiliser l'algorithme de module de puissance rapide pour obtenir le résultat que nous voulons simplement et rapidement.
Afin d'empêcher les nombres de déborder et de réduire la complexité, nous devons utiliser la formule suivante:
abmod c = (a mod c) bmod c
La signification de cette formule est: le produit prend le reste égal au produit prend le reste. Il est facile de voir que cette formule est transitive, afin que nous puissions faire un de plus en plus petit en prenant constamment le reste pour empêcher le débordement.
Théoriquement, avec cette formule, nous pouvons écrire du code. En modulo en permanence A, nous nous assurons que le résultat ne débordera pas. Cela peut en effet calculer le module d'une puissance à une puissance plus grande, mais la complexité de cette méthode est toujours O (n) et n'est pas rapide.
Afin de calculer plus rapidement le module d'une puissance, nous devons également compter sur la formule suivante:
AB mod c = (a2) b / 2 mod c, b est un nombre pair
AB mod c = ((a2) b / 2 ・ a) mod c, b est un nombre impair
Cette formule est très simple. Le principe est de remplacer constamment B par le carré de A et de remplacer B par la moitié d'origine. Parce que nous savons à travers la première formule que le module d'un nombre a le même pouvoir (cette phrase est un peu déroutante, ce qui signifie la formule un). Alors l'effet de l'utilisation du résultat d'un *% c au lieu de a est le même.
Ainsi, selon la formule ci-dessus, nous obtenons une méthode pour calculer la puissance rapide avec la complexité O (Log):
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; un% = c; pour (; b! = 0; b / = 2) {if (b% 2 == 1) res = (res * a)% c; a = (a * a)% c; } System.out.println (res); }}Cet algorithme est à peu près comme ça. La première étape consiste à réduire un% = C pour empêcher le nombre de déborder lorsque A * A est effectué pour la première fois. Dans la boucle FOR, si B est un nombre impair, laissez Res = Res * A, puis multipliez d'abord A dans le résultat, puis traitez-le. Afin d'empêcher le nombre de débordement, le résultat du résultat de Res * a est directement opéré. Dans cette boucle, tôt ou tard, B égalisera 1, entrera dans la branche IF, et enfin calculez la valeur de Res et Mod C quitte la boucle FOR, puis le résultat final.
Résumer
Ce qui précède est toute l'explication détaillée de cet article sur la mise en œuvre de l'algorithme de module de puissance rapide de la langue java. J'espère que ce sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!