Сейчас на уроке информатики обговаривали метод прыткого возведения в ступень. Антон

Методы прыткого возведения в ступень (дихотомический метод возведения в степень, бинарный метод возведения в ступень) алгоритмы, предназначенные для возведения числа \displaystyle x x в естественную ступень \displaystyle n n за наименьшее число умножений, чем это нужно в определении ступени[1]. Методы основаны на том, что для возведения числа \displaystyle x x в степень \displaystyle n n не обязательно перемножать число \displaystyle x x на само себя \displaystyle n n раз, а можно перемножать теснее вычисленные ступени. В частности, если \displaystyle n=2^k n=2^k степень двойки, то для возведения в ступень \displaystyle n n довольно число возвести в квадрат \displaystyle k k раз, затратив при этом \displaystyle k k умножений вместо \displaystyle 2^k 2^k. Например, чтоб возвести число \displaystyle x x в восьмую ступень, вместо выполнения семи умножений \displaystyle x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x \displaystyle x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x можно возвести число в квадрат ( \displaystyle x^2=x\cdot x \displaystyle x^2=x\cdot x), позже результат возвести еще раз в квадрат и получить четвертую ступень ( \displaystyle x^4=x^2\cdot x^2 \displaystyle x^4=x^2\cdot x^2), и наконец итог еще раз возвести в квадрат и получить ответ ( \displaystyle x^8=x^4\cdot x^4 \displaystyle x^8=x^4\cdot x^4).

Кроме того, некие методы для последующей оптимизации используют тот факт, что операция возведения в квадрат прытче операции умножения за счёт того, что при строительстве в квадрат числа в сомножителе повторяются[2].

Бинарный метод возведения в ступень был впервые предложен в XV веке персидским математиком Аль-Каши[3].

Данные методы не всегда оптимальны. Например, при использовании схемы слева вправо быстрое строительство в ступень n = 15 востребует исполнения трёх операций умножения и трёх операций возведения в квадрат, желая строительство в 15-ю ступень можно выполнить и за 3 умножения и 2 возведения в квадрат[4].