Алгоритмы быстрого возведения в степень?

Question

[UID_B Nintendo]

У меня маленький такой вопросик =) А что это за 1 вначале всего умножения ? То есть когда 1 * 21. Сам алгоритм я понимаю но не понимаю.

Answer 1

[Karpion]

Я распишу это так:
13 = 8+4+1
21^13 = 21^8 * 21^4 * 21^1

Теперь вычисляем иксы так:
x1=21
x2=x*x1
x4=x2*x2
x8=x4*x4

И вычисляем искомое
21^13 = x8 * x4 * x1
(x2 в произведении не участвует - он нужен для вычисления x4).

PS: Произведение исходного числа на целое считается аналогично.

Answer 2

[longclaps]

1 для затравки - это начальное значение.

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))

Comments

[UID_B Nintendo]

То есть это что то вроде постоянной константы ? Типо если я захочу замутить другое число я делаю все тоже самое только с другим значением но при этом в начале этого умножения я умножаю на 1 ?

[longclaps]

UID_B Nintendo, я вообще не понимаю, о чем ты толкуешь. А так-то 1 - это константа )

[res2001]

UID_B Nintendo, 2^64 не нужно мутить, так же как и любую другую степень двойки - это просто сдвиг 1 влево на 64 позиции, лишь бы разрядности целого хватило.

[UID_B Nintendo]

longclaps, ну вот это то что я хотел от тебя услышать что 1 это константа.

[longclaps]

UID_B Nintendo, просто интересуюсь - мой ответ неполный, неправильный, непонятный или всё вместе?

[UID_B Nintendo]

longclaps, все ок