Обсуждение:Алгоритмы быстрого возведения в степень — Википедия

Эта статья входит в число добротных статей русской Википедии. См. страницу номинации (статус присвоен 3 декабря 2015 года).

Проект «Математика» (уровень ДС) Эта статья тематически связана с вики-проектом «Математика», цель которого — создание и улучшение статей по темам, связанным с математикой. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями.  ДС Уровень статьи по шкале оценок проекта «Математика»: добротная статья

Алгоритм неправильный. — Эта реплика добавлена с IP 109.86.224.126 (о)

Обоснуйте это. -- X7q 17:41, 14 декабря 2010 (UTC)[ответить]

Пропущено возведение в квадрат во второй стрроке аналога схемы горнера, должно быть ${\displaystyle s_{i}=(s_{i+1})^{2}\cdot x^{m_{i}}}$ -- 89.189.191.13 12:07, 25 февраля 2012 (UTC)[ответить]

Исправил. Maxal 07:14, 28 февраля 2012 (UTC)[ответить]

95.30.123.61 19:22, 29 августа 2011 (UTC)[ответить]

18 правок на 16 строчек паскалевского кода. Неужели вы заблудились в трёх соснах? Неужели так сложно было проверить программу, прежде чем править статью? Звёзды на небе погаснут быстрей, чем эта "функция" посчитает возведение любого числа в первую степень.

Дабы не быть голословным попытаюсь прокомментировать прочитанное:

function power(t, k: integer): integer; {возведение числа t в степень k}

// Отрицательные степени мы тоже умеем считать. Конечно.

if k mod 2 = 1 then {или напишите "if Odd(k) then" для большей скорости выполнения}

// Честно, я первый раз в жизни вижу, чтобы в комментариях писали "Быстрый" код, а в самом коде "медленный". Ноу-хау?

if k > 0 then break;

// Считаем до бесконечности...

t := t * t; {или напишите "t:= sqr(t);" для большей скорости выполнения}

// Для большей скорости не надо ничего никуда писать. В этой реализации выполняется на две инструкции меньше чем с использованием sqr.

Вот немного исправленный код из викиучебника:

var		k:word;	// k - счетчик количества умножений 		 function power(Val, Pwr: qword): qword; // возведение числа val в степень pwr begin   if Val = 0 then     result := 0   else     if Pwr = 0 then       result := 1     else       if Pwr = 1 then         result := Val       else         begin           result := 1;           while Pwr > 0 do           begin             if Pwr mod 2 = 1 then               begin                 p := p * Val; // сделали умножение, поэтому                 inc(k); // увеличиваем k на 1               end;               Pwr := Pwr div 2;             Val := Val * Val; inc(k); // аналогично опять увеличиваем k           end;         end; end;  begin 	k:=0; 	writeln(power(2, 15)); // это просто так для проверки 	writeln(k - 1); // последнее возведение val в квадрат было лишним, вычтем его 		// выводит 7, а не 6? end. 

Программа вывела 7, а не 6. Где ошибка в моих рассуждениях? 37.140.0.93 15:58, 31 мая 2013 (UTC)[ответить]

Надо бы в статье алгоритм описать не только в символьной записи, но и словами. Для облегчения восприятия. И пример возведения в 15 степень расписать, по алгоритму и более оптимальный. --Nashev 17:51, 3 сентября 2013 (UTC)[ответить]

У Панкратовой, этот алгоритм называется "Дихотомический (или бинарный) алгоритм возведения в степень". По-моему это название гораздо лучше. Предлагаю, переименовать эту статью в "Бинарный алгоритм возведения в степень" а для остальных названий поставить перенаправление. Alexei Kopylov 10:04, 3 декабря 2015 (UTC)[ответить]

: оставлю здесь (поиск в Яндексе): * быстрое возведение в степень - 2 млн * двоичное возведение в степень - 600 т * бинарное возведение в степень - 400 т * дихотомическое возведение в степень - 90 т 95.220.151.234 11:22, 22 декабря 2015 (UTC)[ответить] 

Во-первых, если уж так считать, то надо использовать поиск в кавычках. Во-вторых, важно, понять, является быстрое возведение в степень - термином именно для этого алгоритма, или это просто свойство этого алгоритма. Так, например, если источник говорит, что для быстрого возведения в степень можно использовать бинарный алгоритм, то ясно, что хоть "быстрое возведение в степень" и употребляется, но не как название алгоритма. Я не видел ни одного источника, который явно указывал на то, что "быстрое возведение в степень" - это именно название алгоритма, а не его свойство. Alexei Kopylov 22:53, 25 декабря 2015 (UTC)[ответить]