Program for Exponential Squaring (Fast Modulo Multiplication)

Python Program for Exponential Squaring (Fast Modulo Multiplication)

Beginners and experienced programmers can rely on these Best Java Programs Examples and code various basic and complex logics in the Java programming language with ease.

Given two numbers base value and the exponential value, the task is to find the power of base and exponent modular 10^9+7

Examples:

Example1:

Input:

Given base value =  5
Given exponent value = 3

Output:

The value of the power of base and exponent modular 10^9+7 =  125

Example2:

Input:

Given base value =  3
Given exponent value = 10000

Output:

The value of the power of base and exponent modular 10^9+7 =  895629451

Program for Exponential Squaring (Fast Modulo Multiplication) in Python

Below are the ways to find the power of base and exponent modular 10^9+7 for the given base and exponential values:

Method #1: Using While Loop (Static Input)

Approach:

  • Give the base value as static input and store it in a variable.
  • Give the exponential value as static input and store it in another variable.
  • Pass the given base and exponential values as the arguments to the exponentl_squaring() function and store it in a variable.
  • Take a variable to say numb and initialize its value with 1000000007(10^9+7).
  • Create a function to say exponentl_squaring() which takes the given two base and exponential values as the arguments and returns the value of the power of base and exponent modular 10^9+7.
  • Inside the function, take a variable say p, and initialize its value to 1.
  • Loop until the given exponential value is greater than 0 using the while loop.
  • Check if the given exponential value is odd using the if conditional statement.
  • If it is true, multiply p with the given base value and store it in another variable.
  • Calculate the value of the above result modulus numb(10^9+7) and store it in the same variable p.
  • Multiply the given base value with itself and apply the modulus operator with 10^9+7(numb).
  • Store it in the same variable given base value.
  • Divide the given exponential value by 2 and convert it to an integer using the int() function.
  • Store it in the same variable given exponential value.
  • Return the value of p modulus 10^9+7.
  • Print the value of the power of base and exponent modular 10^9+7.
  • The Exit of the Program.

Below is the implementation:

# Take a variable to say numb and initialize its value with 1000000007(10^9+7).
numb = 1000000007

# Create a function to say exponentl_squaring() which takes the given two base and
# exponential values as the arguments and returns the value of the power of base and
# exponent modular 10^9+7.


def exponentl_squaring(gvn_baseval, gvn_exponentlval):
  # Inside the function, take a variable say p, and initialize its value to 1.
    p = 1
    # Loop until the given exponential value is greater than 0 using the while loop.
    while(gvn_exponentlval > 0):
           # Check if the given exponential value is odd using the if conditional statement.
        if (gvn_exponentlval % 2 != 0):
            # If it is true, multiply p with the given base value and store it in another
            # variable.
            k = p * gvn_baseval
            # Calculate the value of the above result modulus numb(10^9+7) and store it in the
            # same variable p.
            p = k % numb
      # Multiply the given base value with itself and apply the modulus operator with
      # 10^9+7(numb).
      # Store it in the same variable given base value.
        gvn_baseval = (gvn_baseval * gvn_baseval) % numb
        # Divide the given exponential value by 2 and convert it to an integer using the
        # int() function.
        # Store it in the same variable given exponential value.
        gvn_exponentlval = int(gvn_exponentlval / 2)
   # Return the value of p modulus 10^9+7.
    return p % numb


# Give the base value as static input and store it in a variable.
gvn_baseval = 5
# Give the exponential value as static input and store it in another variable.
gvn_exponentlval = 3
# Pass the given base and exponential values as the arguments to the exponentl_squaring()
# function and store it in a variable.
rslt = exponentl_squaring(gvn_baseval, gvn_exponentlval)
# Print the value of the power of base and exponent modular 10^9+7.
print("The value of the power of base and exponent modular 10^9+7 = ", rslt)

Output:

The value of the power of base and exponent modular 10^9+7 =  125

Method #2: Using While loop (User Input)

Approach:

  • Give the base value as user input using the int(input()) function and store it in a variable.
  • Give the exponential value as user input using the int(input()) function and store it in another variable.
  • Pass the given base and exponential values as the arguments to the exponentl_squaring() function and store it in a variable.
  • Take a variable to say numb and initialize its value with 1000000007(10^9+7).
  • Create a function to say exponentl_squaring() which takes the given two base and exponential values as the arguments and returns the value of the power of base and exponent modular 10^9+7.
  • Inside the function, take a variable say p, and initialize its value to 1.
  • Loop until the given exponential value is greater than 0 using the while loop.
  • Check if the given exponential value is odd using the if conditional statement.
  • If it is true, multiply p with the given base value and store it in another variable.
  • Calculate the value of the above result modulus numb(10^9+7) and store it in the same variable p.
  • Multiply the given base value with itself and apply the modulus operator with 10^9+7(numb).
  • Store it in the same variable given the base value.
  • Divide the given exponential value by 2 and convert it to an integer using the int() function.
  • Store it in the same variable given exponential value.
  • Return the value of p modulus 10^9+7.
  • Print the value of the power of base and exponent modular 10^9+7.
  • The Exit of the Program.

Below is the implementation:

# Take a variable to say numb and initialize its value with 1000000007(10^9+7).
numb = 1000000007

# Create a function to say exponentl_squaring() which takes the given two base and
# exponential values as the arguments and returns the value of the power of base and
# exponent modular 10^9+7.


def exponentl_squaring(gvn_baseval, gvn_exponentlval):
  # Inside the function, take a variable say p, and initialize its value to 1.
    p = 1
    # Loop until the given exponential value is greater than 0 using the while loop.
    while(gvn_exponentlval > 0):
           # Check if the given exponential value is odd using the if conditional statement.
        if (gvn_exponentlval % 2 != 0):
            # If it is true, multiply p with the given base value and store it in another
            # variable.
            k = p * gvn_baseval
            # Calculate the value of the above result modulus numb(10^9+7) and store it in the
            # same variable p.
            p = k % numb
      # Multiply the given base value with itself and apply the modulus operator with
      # 10^9+7(numb).
      # Store it in the same variable given base value.
        gvn_baseval = (gvn_baseval * gvn_baseval) % numb
        # Divide the given exponential value by 2 and convert it to an integer using the
        # int() function.
        # Store it in the same variable given exponential value.
        gvn_exponentlval = int(gvn_exponentlval / 2)
   # Return the value of p modulus 10^9+7.
    return p % numb

# Give the base value as user input using the int(input()) function and store it in a variable.
gvn_baseval = int(input("Enter some random number = "))
# Give the exponential value as user input using the int(input()) function and 
# store it in another variable.
gvn_exponentlval = int(input("Enter some random number = "))
# Pass the given base and exponential values as the arguments to the exponentl_squaring()
# function and store it in a variable.
rslt = exponentl_squaring(gvn_baseval, gvn_exponentlval)
# Print the value of the power of base and exponent modular 10^9+7.
print("The value of the power of base and exponent modular 10^9+7 = ", rslt)

Output:

Enter some random number = 3
Enter some random number = 10000
The value of the power of base and exponent modular 10^9+7 = 895629451