Быстрое вознесение в степень

[Alex696]

Хотел бы задать вопрос насчет "быстрого" вознесения в степень числа, например $x^{n}$. Суть операции ясна - достичь результата за меньшее количество произведений, а вот принцип реализации, был бы благодарен, если разъяснили (именно не реализация на каком-то языке, а на данном примере).

[Xaositect]

Бинарный алгоритм работает так:
Если $n$ нечетное, то сначала получаем $x^{n-1}$, а затем умножаем его на $x$: $x^n = x^{n-1}\cdot x$,
Если $n$ четное, то сначала получаем $x^{\frac{n}{2}}$, а потом возводим в квадрат(умножаем на себя): $x^n = x^{\frac{n}{2}}\cdot x^{\frac{n}{2}}$.
Таким образом, за максимум 2 шага мы уменьшаем требуемую степень в 2 раза, то есть всего для возведения в $n$-ю степень нам потребуется меньше $2\log n$ умножений.

[venco]

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

[Xaositect]

На практике использовать схему, которую я выше написал, нехорошо, потому что рекурсия и вообще.
используется такой алгоритм:

float Power(float x, int n)
{
  r = 1;
  while( n > 0 )
  {
    if( n % 2 )
    {
      r *= x;
    }
    else
    {
      x *= x;
    }
    n >>= 1;
  }
  return r;
}

Он основан на соотношении $x^n = x^{\sum n_i 2^i} = \prod\limits_{n_i = 1} x^{2^i}$, где $n = \overline{(n_{k-1}..n_0)}_2$ - запись числа $n$ в двоичной системе, то есть, если подумать, идея та же.

[Alex696]

2Xaositect: Большое спасибо, все четко и ясно!

[Pixar]

Если хочешь достичь в этом деле максимальных высот, почитай про числа Стирлинга

[Alex696]

Возник вопрос касательно быстрого умножения Просмотрел несколько методов таких как Трахтенберга, Штрассена. Но какой из них использовать в информатических задачах, вроде реализации быстрого умножения двух заданых чисел $x * n$, понятия не имею. Оба, как указано, для больших натуральных чисел. Буду благодарен за любую помощь касательно вопроса.

[Xaositect]

Alex696 в сообщении #256077 писал(а):

Буду благодарен за любую помощь касательно вопроса.

Я думаю, Карацубы должно хватить, на крайняк 3-Тоом с точками интерполяции $-1,0,1,\infty$ и еще какой-нибудь.

Вот, скажем, в библиотеке GMP используется обычное умножение для чисел длиной до ~10 лимбов (лимб - это нативное машинное число, т.е. 4 байта на 32-битной машине), Карацуба - до ~100, Тоом - до ~1000, а дальше Шёнхаге-Штрассен. Причем у них Ш-Ш оптимизированный, вы такого сходу не напишете

[Circiter]

2Xaositect
Кажется, приведенный вами алгоритм быстрого возведения в степень (последний) не работает. На самом деле, возводить $x$ в квадрат нужно на каждой итерации, т.е. примерно так:

Type PowerBySquaring(Type Base, unsigned long Exponent)
{
    type Result=Identity;

    while(Exponent)
    {
        if(Exponent % 2)
        {
            Result *= Base;
            Exponent -= 1;
        }

        Base *= Base;
        Exponent /= 2;
    }
}

Используется разложение

$$x^n=\left[ n=\sum_{i=0} 2^i n_i \right]=\prod_{i=0} x^{2^i n_i},$$

где $n_i$ - цифры двоичного представления числа $n$. Таким образом для вычисления $x^n$ необходимо найти последовательность $\{x^{2^i}\}_{i=0}$ и бинарное представление показателя степени.

Первая задача решается "в лоб" последовательным возведением в квадрат (Base *= Base), а вторая переводом числа $n$ в двоичную систему счисления, т.е. последовательным делением на два (Expoxnent /= 2 или Exponent >>= 1) с учетом получающихся остатков (наличие единицы в младшем разряде индицируется выполнением условий Exponent % 2 или Exponent & 1).

Строка Exponent -= 1 опциональна и нужна лишь для гарантии правильности округления (до наибольшего целого, меньшего чем частное; aka floor) результата деления на два (для C это гарантируется стандартом).

Этот алгоритм имеет сложность $\mathcal{O}(\log n)$ и работает над любой (абелевой) полугруппой относительно умножения (моноидом?), что является его главным преимуществом (хоть коров в степень возводи), но умеет возводить числа только в натуральную степень.

Фактическая производительность алгоритма может быть улучшена многочисленными способами (можно разбивать бинарное представление на группы разрядов скользящим окном, разрешить отрицательные биты или использовать addition chain), но на асимптотику это не повлияет (улучшаться будет только константный множитель).

2Alex696

Цитата:

Хотел бы задать вопрос насчет "быстрого" вознесения в степень числа, например $x^n$.

Если $x,n\in\mathbb{R}$ или $x,n\in\mathbb{C}$, то можно заюзать логарифм с экспонентой: $x^n=\exp\ \ln x^n=\exp(n\ln x)$. Это работает достаточно быстро и позволяет возводить числа в произвольные степени, даже в дробные (e.g. при вычислении корней).

Цитата:

Возник вопрос касательно быстрого умножения

Недавно попалась на глаза работка Martin Furer, Faster Integer Multiplication. Довольно интересно.

[Xaositect]

Circiter в сообщении #256163 писал(а):

Кажется, приведенный вами алгоритм быстрого возведения в степень (последний) не работает. На самом деле, возводить в квадрат нужно на каждой итерации, т.е. примерно так:

Да, извиняюсь.Впрочем, идея понятна.

Circiter в сообщении #256163 писал(а):

Недавно попалась на глаза работка Martin Furer, Faster Integer Multiplication. Довольно интересно.

Индийцев еще почитайте: http://arxiv.org/abs/0801.1416