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

Алгоритм неправильный

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

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

Пропущено возведение в квадрат во второй стрроке аналога схемы горнера, должно быть $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.

Количество умножений при возведении в 15 степень

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

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)