Question

Сегодня на уроке информатики обсуждали алгоритм быстрого возведения в степень. Антон был очень внимателен и запомнил, что алгоритм нужен для того, чтобы сократить количество операций умножения при вычислении a^n. Вместо n−1умножения, которые получаются если просто вычислить произведение a⋅a⋅a⋅…⋅a (n сомножителей) можно получить гораздо меньшее число, если действовать так: o если n кратно 2, то найдем сперва a^(n/2), а потом умножим a^(n/2) на себя o если n не кратно 2, то найдем a^(n–1), а потом умножим на a. Например, чтобы вычислить a10 хватит четырех умножений: 3. сначала найдем a^2=a⋅a, 4. потом a^4=a^2⋅a^2, 5. потом a^5=a⋅a^4, 6. и, наконец, a^10=a^5⋅a^5. Антон также запомнил, что самые "плохие" случаи для этого алгоритма — когда n на 1 меньше точной степени двойки. Теперь ему интересно узнать для какого-нибудь большого "плохого" n, а сколько умножений нужно, чтобы возвести a в степень n с помощью этого алгоритма. Помогите Антону, определите, сколько умножений сделает алгоритм для вычисления 2n, где n= 2^12–1. Любой язык

Answer 1

Никакой язык здесь не нужен. Задача математическая.

Сначала, давайте определим функции:

1) Для всех натуральных n,

$\displaystyle f(n)= \left \{ {{f(n/2)+1\,, \text{if } n \equiv 0 \pmod 2}\atop {f(n-1)+1\,,\text{if } n\equiv 1 \pmod 2 \land n\neq1 }} \right., f(1)=0$

Очевидно, что эта функция равна количеству умножений, которые нужно выполнить используя данный алгоритм (для того чтобы вычислить $a^n$).

2) Для все натуральных n,

$L(n) = f(2^n-1)$.

Таким образом, нам требуется вычислить

$f(2n)=f(n)+1=f(2^{12}-1)+1=L(12)+1$

Заметим, что

$L(n+1)=L(n)+2$

$L(1)=0$

Т.к.

$f(2^{n+1}-1)=f(2^{n+1}-2)+1=f(2(2^n-1))+1=f(2^n-1)+2$

$f(2^1-1)=f(1)=0$

Используя математическую индукцию, легко доказать что для всех n>1,

$L(n)=2(n-1)$  

Следовательно,

$f(2n)=L(12)+1=2\cdot 11 +1=23$