kostyamega8
@kostyamega8
Новичок

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

5d2ad2e743bab514374442.png У меня маленький такой вопросик =) А что это за 1 вначале всего умножения ? То есть когда 1 * 21. Сам алгоритм я понимаю но не понимаю.
  • Вопрос задан
  • 300 просмотров
Решения вопроса 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: Произведение исходного числа на целое считается аналогично.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
longclaps
@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))
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы