Binary Exponentiation - Algorithm Tutorial | Repovive

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/power-function

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/power-function

Repovive

Binary Exponentiation - Algorithm Tutorial | Repovive | Repovive

x^{n} = (x^{n / 2})^{2}

x^n = (x^{n/2})^2

function power(x, n, mod):
    result = 1
    x = x mod mod

    while n > 0:
        if n is odd:
            result = (result * x) mod mod
        x = (x * x) mod mod
        n = n / 2 (integer division)

    return result

Binary Exponentiation Algorithm Tutorial

Learn

Fast Exponentiation (Binary Exponentiation)

Practice this Algorithm

Related Algorithms