Fast exponentiation algorithms?

Question

Algorithms

I have such a small question =) And what is this 1 at the beginning of the whole multiplication? That is, when 1 * 21. I understand the algorithm itself, but I don’t understand it.

Answer 1

I write it like this:
13 = 8+4+1
21^13 = 21^8 * 21^4 * 21^1
Now we calculate the x's like this:
x1=21
x2=x*x1
x4=x2*x2
x8=x4*x4
And we calculate the desired
21^13 = x8 * x4 * x1
(x2 does not participate in the product - it is needed to calculate x4).
PS: The product of the original number by an integer is considered similar.

Answer 2

1 for seed is the initial value.

def power(x, y):
    res = 1
    for d in f'{y:b}':
        res *= res
        if d == '1':
            res *= x
    return res

print(power(21, 13))