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

Question

48 просмотров

Сегодня на уроке информатики обсуждали алгоритм быстрого возведения в степень. Антон был очень внимателен и запомнил, что алгоритм нужен для того, чтобы сократить количество операций умножения при вычислении 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. Любой язык

Информатика Gagawegwetgaw_zn (12 баллов) 01 Июнь, 20 | 48 просмотров

Дан 1 ответ

Denissvetazvarish_zn · Answer 1 · 2020-06-01T03:11:25+0000

Алгоритмы быстрого возведения в степень (дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы, предназначенные для возведения числа {\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].