Ускоренная функция возведения в степень

Question

Недавно пришла идея написания функции возведения в степень (power), и понял, что кроме обычного возведения:

int power(const int x, int y) {
    int result = 1;
    for (; y > 0; y--) {result *= x;}
    return result;
}

можно использовать гораздо лучше функцию:

int power_big(int x, int p) {
    if (p == 1) return x;
    if (p == 0) return 1;
    if (p % 2 == 0) {
        int n = power_big(x, p/2);
        return n * n;
    }
    return power_big(x, p - 1) * x;
}

Эта статья не про вопрос, а про возможность того, что можно сделать так, а не обычным циклом что при больших степенях будет долго обрабатываться. Как пример: функция power(2, 10) выдаст результат через 10 циклов, а функция power_big(2, 10) за 5.

Есть ли ещё методы, которые помогут оптимизировать скорость работы программы и повысить её производительность вразы?

Answer 1

NB Тема большая, но как-то сориентироваться в ней можно.

Да, такие методы есть. Ими занимается теория алгоритмов.

Для конкретно задачи возведения в степень можно показать что ваше решение (которое называется быстрое возведение в степень) близко к самому быстрому возможному. Близко в том смысле, что если вообразить себе самый быстрый возможный алгоритм возведения в степень, то он будет быстрее вашего только в фиксированное количество раз. То есть, принципиально его ускорить нельзя.

Что такое "принципиально" вы можете почувствовать на примере двух вариантов кода из вопроса. Чем больше p, тем быстрее оказывается второй алгоритм в сравнении с первым. Это принципиальное ускорение. Ваш второй алгоритм уже самый быстрый в этом "принципиальном" смысле.

Но его можно ускорить ещё немного. Для некоторых значений p второй алгоритм делает слишком много умножений. Например для p = 81 ваш алгоритм сделает восемь умножений, а лучшая схема уложится в шесть. Поиск самой лучшей схемы - сложная проблема. На практике на неё не тратят время, так как принципиально ваше решение уже не улучшить.

Можно избавится от рекурсии, это даст небольшое "непринципиальное" ускорение, так как лучше использует ресурсы вычислителя.

Оба вида ускорений, и "принципиальные" и не "принципиальные", равно важны для успешного решения задач. Например, ваш GPU - пример "непринципиального" ускорения, то только благодаря ему вы играете в игры.

Анализ алгоритмов занимается как доказательством правильности аллгоритмов, так и даёт инструменты для оценки насколько можно ускорить тот или иной алгоритм.

Answer 2

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

Кру́глыми чи́слами относительно некоторой позиционной системы счисления называют степени её основания. В этой системе счисления такие числа записываются как единица с последующими нулями. Количество нулей справа от единицы равно показателю степени основания.

т.е. для возведения, скажем 9ти в какую-то степень достаточно всего лишь... взять число 9 в 9ти-ричной СИ(10) и после просто конкатенировать к нему нужное кол-во кругли... тьфу! ноликов(равное нужной степени), воть :3

понимаете ж к чему я?

@counter-style bin{
system: numeric;
symbols: '0' '1';
suffix: ". ";
}
#x{list-style: bin;}

@counter-style tre{
system: numeric;
symbols: '0' '1' '2';
suffix: ". ";
}
#y{list-style: tre;}
ol{padding-left: 30%;}

<ol id='x'>
  <li value='2'>я
  <li value='4'>web
  <li value='8'>дизайнер
  <li value='16'>я
  <li value='32'>так
  <li value='64'>вижу
  <li value='81'>81
</ol>
<ol id='y'>
  <li value='3'>
  <li value='9'>
  <li value='27'>
  <li value='81'>
  <li value='243'>
  <li value='64'>64
</ol>
<ol id='z'>
  <li value='3'>
  <li value='9'>
  <li value='27'>
  <li value='81'>
  <li value='243'>
</ol>

никто не запрещает использовать СИ отличные от общепринятых =)

еще пример:

чтобы получить, скажем dec 2^4, берем систему счисления с основанием 2 и рисуем в ней единицу с 4я нулями(bin 10 000).

дальше останется только сконвертировать полученный набор символов в ту СИ которая больше нравится :3 // ну и из строки в int конечно же

надо возвести 16 в 7ую? - 10 000 000 в hex
7^5 - 100 000 кто нить пробовал считать зарплату в днях недели? :D
60^2 - минуты \ секунды.

ну а дальше, если ваш ЯП поддерживает числа с нужными числами в качестве оснований, максимум что потребуется - привести к соответствующему типу(числу).

let a = 0b1;
a += '000';
console.log(parseInt(a, 10) + 92);

let b = parseInt(1, 16);
console.log('b0: ' + parseInt(b, 16));

b += '0';
console.log('b1: ' + parseInt(b, 16));

b += '0';
console.log('b2: ' + parseInt(b, 16));

b += '0';
console.log('b3: ' + parseInt(b, 16));

b += '000';
console.log('b4: ' + parseInt(b, 16)); // по идее тут M 16^6

p.s. если что, в бэнчмарках сие не щупал, даж самому интересно стало :3

кто пощупает, отпишите результат сравнения.

и да, я не настоящий математик, если есть ошибки - сильно не истерите =)

БЛОГ НА HUSL

Ускоренная функция возведения в степень

Ответы (2 шт):