Интернет магазин китайских планшетных компьютеров



Компьютеры - Алгоритм быстрого возведения в степень

22 января 2011


Оглавление:
1. Алгоритм быстрого возведения в степень
2. Оценка сложности



алгоритм, предназначенный для возведения числа x в натуральную степень n за меньшее число умножений, чем это требуется в определении.

Алгоритм не всегда оптимален. Например, при n=15 требуется 6 умножений, хотя на самом деле возведение в 15-ую степень можно выполнить за 5 умножений.

Теоретические основы алгоритма

Пусть n=_2 — двоичное представление степени n. Тогда n=m_{k} \cdot 2^{k}+m_{k-1} \cdot 2^{k-1}+...+m_{1} \cdot 2+m_{0}, где m_{k}=1, m_{i} \in \{ 0,1 \} и x^{n}=x^{ \cdot 2+m_{k-2}) \cdot 2+...) \cdot 2+m_{1}) \cdot 2 + m_{0}}=^{2} \cdot x^{m_{k-1}})^{2}...)^{2} \cdot x^{m_{1}})^2 \cdot x^{m_{0}}.

Таким образом, алгоритм быстрого возведения в степень сводится к мультипликативному аналогу схемы Горнера.

\begin{Bmatrix} s_{k}=x \\ s_{i}=s_{i+1} \cdot x^{m_{i}} \\ 0 \le i \le k-1 \end{Bmatrix}

Программная реализация

Используется представление числа x:

x^m=x^{m_0} \cdot \left^{m_1} \cdot \left^{m_2} \cdot \left^{m_3}  \cdot\dots\cdot \left^{m_k} .

Язык Си

int power // возведение t в степень k
{
  int res = 1;
  while  
      {
        if  
           res *= t;
        t *= t;
        k >>= 1;
      }
  return res;
}

Delphi

function Power: NativeInt; inline;
begin
  Result := 1;
  while true do
  begin
    if Odd then
      Result := Result * t;
    k := k shr 1;
    if k = 0 then
      break;
    t := t * t;
  end;
end;

Паскаль

function power: integer; {возведение числа t в степень k}
var
  res:integer;
begin
  res := 1;
  while true do
  begin
    if k mod 2 = 1 then    {или напишите "if Odd then" для большей скорости выполнения} 
      res := res * t;
 
    k := k div 2;          {или напишите "k := k shr 1;" для большей скорости выполнения}
    if  k = 0 then
        break;
    t := t * t;            {или напишите "t:= sqr;" для большей скорости выполнения}
  end;
  power := res;
end;

Python

def FastPow :  # Быстрое возведение числа t в степень k
    res = 1
    while k:
        if :
            res *= t
        k = k >> 1
        if k == 0:
            break
        t *= t
 
    return res


Просмотров: 3562


<<< Алгоритм Адлемана
Алгоритм Евклида >>>