Elevación al cuadrado exponencial (multiplicación de módulo rápido)

Posted on by Rudeus Greyrat

Dados dos números base y exp , necesitamos calcular base exp en Modulo 10^9+7 Ejemplos:

Input : base = 2, exp = 2
Output : 4

Input  : base = 5, exp = 100000
Output : 754573817

En las competiciones, para calcular grandes potencias de un número, se nos da un valor de módulo (un número primo grande) porque, a medida que se  x^y calculan los valores de, puede volverse muy grande, por lo que en su lugar tenemos que calcular ( x^y % del valor del módulo). Podemos usar el módulo a nuestra manera ingenua usando módulo en todos los pasos intermedios y tomando módulo al final, pero en las competencias definitivamente mostrará TLE. Así que lo que podemos hacer. La respuesta es que podemos probar la exponenciación elevando al cuadrado , que es un método rápido para calcular la exponenciación de un número. Aquí discutiremos los dos métodos más comunes/importantes:

  1. Método básico (exponenciación binaria)
  2. 2^k -método ario.

Exponenciación binaria

Como se describe en este artículo, usaremos la siguiente fórmula para calcular de forma recursiva ( x^y % del valor del módulo): {\displaystyle x^{n}={\begin{cases}x\,(x^{2})^{\frac {n-1}{2}},&{\mbox{if }}n{\mbox{ is odd}}\\(x^{2})^{\frac {n}{2}},&{\mbox{if }}n{\mbox{ is even}}.\end{cases}}}

C++

// C++ program to compute exponential
// value under modulo using binary
// exponentiation.
#include<iostream>
using namespace std;
 
#define N 1000000007 // prime modulo value
 
long int exponentiation(long int base,
                        long int exp)
{
    if (exp == 0)
        return 1;
 
    if (exp == 1)
        return base % N;
 
    long int t = exponentiation(base, exp / 2);
    t = (t * t) % N;
 
    // if exponent is even value
    if (exp % 2 == 0)
        return t;
 
    // if exponent is odd value
    else
        return ((base % N) * t) % N;
}
 
// Driver Code
int main()
{
    long int base = 5;
    long int exp = 100000;
 
    long int modulo = exponentiation(base, exp);
    cout << modulo << endl;
    return 0;
}
 
// This Code is contributed by mits

Java

// Java program to compute exponential value under modulo
// using binary exponentiation.
import java.util.*;
import java.lang.*;
import java.io.*;
 
class exp_sq {
    static long N = 1000000007L; // prime modulo value
    public static void main(String[] args)
    {
        long base = 5;
        long exp = 100000;
 
        long modulo = exponentiation(base, exp);
        System.out.println(modulo);
    }
 
    static long exponentiation(long base, long exp)
    {
        if (exp == 0)
            return 1;
 
        if (exp == 1)
            return base % N;
 
        long t = exponentiation(base, exp / 2);
        t = (t * t) % N;
 
        // if exponent is even value
        if (exp % 2 == 0)
            return t;
 
        // if exponent is odd value
        else
            return ((base % N) * t) % N;
    }
}

Python3

# Python3 program to compute
# exponential value under
# modulo using binary
# exponentiation.
 
# prime modulo value
N = 1000000007;
     
# Function code
def exponentiation(bas, exp):
    if (exp == 0):
        return 1;
    if (exp == 1):
        return bas % N;
     
    t = exponentiation(bas, int(exp / 2));
    t = (t * t) % N;
     
    # if exponent is
    # even value
    if (exp % 2 == 0):
        return t;
         
    # if exponent is
    # odd value
    else:
        return ((bas % N) * t) % N;
 
# Driver code
bas = 5;
exp = 100000;
 
modulo = exponentiation(bas, exp);
print(modulo);
 
# This code is contributed
# by mits

C#

// C# program to compute exponential
// value under modulo using binary
// exponentiation.
using System;
 
class GFG {
     
    // prime modulo value
    static long N = 1000000007L;
     
    // Driver code
    public static void Main()
    {
        long bas = 5;
        long exp = 100000;
 
        long modulo = exponentiation(bas, exp);
        Console.Write(modulo);
    }
 
    static long exponentiation(long bas, long exp)
    {
        if (exp == 0)
            return 1;
 
        if (exp == 1)
            return bas % N;
 
        long t = exponentiation(bas, exp / 2);
        t = (t * t) % N;
 
        // if exponent is even value
        if (exp % 2 == 0)
            return t;
 
        // if exponent is odd value
        else
            return ((bas % N) * t) % N;
    }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// PHP program to compute exponential
// value under modulo using binary
// exponentiation.
 
// prime modulo value
$N = 1000000007;
     
// Function code
function exponentiation($bas, $exp)
{
    global $N ;
    if ($exp == 0)
        return 1;
 
    if ($exp == 1)
        return $bas % $N;
 
    $t = exponentiation($bas,
                        $exp / 2);
    $t = ($t * $t) % $N;
 
    // if exponent is
    // even value
    if ($exp % 2 == 0)
        return $t;
 
    // if exponent is
    // odd value
    else
        return (($bas % $N) *
                 $t) % $N;
}
 
// Driver code
$bas = 5;
$exp = 100000;
 
$modulo = exponentiation($bas, $exp);
echo ($modulo);
 
// This code is contributed by ajit
?>

Javascript

<script>
// JavaScript program to compute
// exponential value under
// modulo using binary
// exponentiation.
 
// prime modulo value
let N = 1000000007;
 
// Function code
function exponentiation(base, exp){
 
    if (exp == 0){
        return 1;
    }
         
    if (exp == 1){
        return (base % N);
    }
 
    let t = exponentiation(base,exp/2);
    t = ((t * t) % N);
    console.log(t);
     
    // if exponent is
    // even value
    if (exp % 2 == 0){
        return t;
    }
     
    // if exponent is
    // odd value
    else{
        return ((base % N) * t) % N;
    }      
}
 
 
// Driver code
let base = 5;
let exp = 100000;
 
let modulo = exponentiation(base, exp);
document.write(modulo);
document.write(base);
 
// This code is contributed by Gautam goel (gautamgoel962)
</script>

Producción :

754573817

-método ario:

En este algoritmo, expandiremos el exponente en base  2^k (k>=1), que es de alguna manera similar al método anterior, excepto que no estamos usando recursividad, este método usa comparativamente menos memoria y tiempo. 

C++

// C++ program to compute exponential value using (2^k)
// -ary method.
#include<bits/stdc++.h>
using namespace std;
 
#define N 1000000007L; // prime modulo value
 
long exponentiation(long base, long exp)
{
    long t = 1L;
    while (exp > 0)
    {
 
        // for cases where exponent
        // is not an even value
        if (exp % 2 != 0)
            t = (t * base) % N;
 
        base = (base * base) % N;
        exp /= 2;
    }
    return t % N;
}
 
// Driver code
int main()
{
    long base = 5;
    long exp = 100000;
 
    long modulo = exponentiation(base, exp);
    cout << (modulo);
    return 0;
}
 
// This code is contributed by Rajput-Ji

Java

// Java program to compute exponential value using (2^k)
// -ary method.
import java.util.*;
import java.lang.*;
import java.io.*;
 
class exp_sq {
    static long N = 1000000007L; // prime modulo value
    public static void main(String[] args)
    {
        long base = 5;
        long exp = 100000;
 
        long modulo = exponentiation(base, exp);
        System.out.println(modulo);
    }
 
    static long exponentiation(long base, long exp)
    {
        long t = 1L;
        while (exp > 0) {
 
            // for cases where exponent
            // is not an even value
            if (exp % 2 != 0)
                t = (t * base) % N;
 
            base = (base * base) % N;
            exp /= 2;
        }
        return t % N;
    }
}

Python3

# Python3 program to compute
# exponential value
# using (2^k) -ary method.
 
# prime modulo value
N = 1000000007;
 
def exponentiation(bas, exp):
    t = 1;
    while(exp > 0):
 
        # for cases where exponent
        # is not an even value
        if (exp % 2 != 0):
            t = (t * bas) % N;
 
        bas = (bas * bas) % N;
        exp = int(exp / 2);
    return t % N;
 
# Driver Code
bas = 5;
exp = 100000;
 
modulo = exponentiation(bas,exp);
print(modulo);
 
# This code is contributed
# by mits

C#

// C# program to compute
// exponential value
// using (2^k) -ary method.
using System;
 
class GFG
{
// prime modulo value
static long N = 1000000007L;
 
static long exponentiation(long bas,
                           long exp)
{
    long t = 1L;
    while (exp > 0)
    {
 
        // for cases where exponent
        // is not an even value
        if (exp % 2 != 0)
            t = (t * bas) % N;
 
        bas = (bas * bas) % N;
        exp /= 2;
    }
    return t % N;
}
 
// Driver Code   
public static void Main ()
{
    long bas = 5;
    long exp = 100000;
 
    long modulo = exponentiation(bas,
                                 exp);
    Console.WriteLine(modulo);
}
}
 
//This code is contributed by ajit

PHP

<?php
// PHP program to compute
// exponential value
// using (2^k) -ary method.
 
// prime modulo value
$N = 1000000007;
 
function exponentiation($bas,
                        $exp)
{
    global $N;
    $t = 1;
    while ($exp > 0)
    {
 
        // for cases where exponent
        // is not an even value
        if ($exp % 2 != 0)
            $t = ($t * $bas) % $N;
 
        $bas = ($bas * $bas) % $N;
        $exp = (int)$exp / 2;
    }
    return $t % $N;
}
 
// Driver Code
$bas = 5;
$exp = 100000;
 
$modulo = exponentiation($bas,
                         $exp);
echo ($modulo);
 
// This code is contributed
// by ajit
?>

Javascript

// JavaScript program to compute
// exponential value
// using (2^k) -ary method.
 
// prime modulo value
let N = 1000000007n;
 
function exponentiation(bas, exp)
{
    let t = 1n;
    while(exp > 0n)
    {
        // for cases where exponent
        // is not an even value
        if (exp % 2n != 0n)
            t = (t * bas) % N;
         
         
        bas = (bas * bas) % N;
        exp >>= 1n;
    }
    return t % N;
}
 
 
// Driver Code
let bas = 5n;
let exp = 100000n;
 
let modulo = exponentiation(bas,exp);
console.log(Number(modulo));
 
 
// This code is contributed
// by phasing17

Producción :

754573817

Aplicaciones: además del cálculo rápido de  x^y este método, tiene otras ventajas, como que se usa en criptografía, en el cálculo de la exponenciación de arrays , etc.

Publicación traducida automáticamente

Artículo escrito por sanjal_katiyar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *