Быстрое возведение в степень — различия между версиями
(Новая страница: «'''Алгоритм быстрого возведения в степень''' — алгоритм, предназначенный для возведения чи…») |
Bochkarev (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
'''Алгоритм быстрого возведения в степень''' — алгоритм, предназначенный для возведения числа ''x'' в натуральную степень ''n'' за меньшее число умножений, чем это требуется в определении. | '''Алгоритм быстрого возведения в степень''' — алгоритм, предназначенный для возведения числа ''x'' в натуральную степень ''n'' за меньшее число умножений, чем это требуется в определении. | ||
| + | |||
| + | Пусть <tex>m=(m_{k}m_{k-1}...m_{1}m_{0})_2</tex> — |двоичное представление степени ''n''. Тогда <tex>n=m_{k} \cdot 2^{k}+m_{k-1} \cdot 2^{k-1}+...+m_{1} \cdot 2+m_{0}</tex>, где <tex>m_{k}=1, m_{i} \in \{ 0,1 \}</tex> и <tex>x^{n}=x^{((...((m_{k} \cdot 2+m_{k-1}) \cdot 2+m_{k-2}) \cdot 2+...) \cdot 2+m_{1}) \cdot 2 + m_{0}}</tex>. <br> | ||
Версия 21:03, 8 октября 2010
Алгоритм быстрого возведения в степень — алгоритм, предназначенный для возведения числа x в натуральную степень n за меньшее число умножений, чем это требуется в определении.
Пусть — |двоичное представление степени n. Тогда , где и .
