Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Возвдение в тепень

Автор: T0ohtik 21.5.2008, 20:40

Привет! Надо подобрать и реализовать оптимальный алгоритм возведения в степень. Задача заключается в том, что у нас есть 2 числа в двоичном виде. Эти числа представлены как массив. Какие идеи будут?

Автор: maxim1000 21.5.2008, 21:05

есть такой способ:

Код


power(a,x)
{
    if(x==1)
        return a;
    if(x%2==0)
        return power(a*a,x/2);
    else
        return power(a*a,(x-1)/2)*a
}

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

но, у меня большие подозрения, что на то, чтобы определить, попались ли нам такие числа, что этот метод неоптимальный и какой алгоритм на самом деле оптимальный, потратится больше вычислительной мощности, чем на реализацию этого алгоритма

ну а наличие чисел именно в двоичном представлении - ещё один довод в пользу этого метода:
если повнимательнее его рассмотреть, то можно увидеть, что он просто обрабатывает по порядку биты числа x, т.е. вполне неплохо приспособлен для данной ситуации...

Автор: T0ohtik 21.5.2008, 23:20

как я понял a - это i - тый элемент?

Автор: maxdiver 22.5.2008, 09:16

Нет, a и x - это сами числа (которое возводится в степень и сама степень).
А i-ый бит, подразумевается, берётся здесь: x%2==0.

Автор: maxdiver 31.5.2008, 21:29

По-видимому, бинарное возведение в степень является оптимальным, но при условии, что разрешены операции умножения на 2 и прибавления 1.

Потому что, если, например, разрешено отнимать единичку, то, очевидно, это будет не так (например, 31 быстрее получить из 32).
Вот для этого случая уже намного менее тривиально определить оптимально, какие действия в какой последовательности выполнять. Задача с Петрозаводских сборов-2006 smile

Мы написали динамику за (logN)^2, хотя, видимо, можно кое-какую эвристику пропихнуть (находить группы подряд идущих единичек или разделённых одним ноликом, и получать их возведением двойки в степень и вычитанием, либо, если единичка одна - просто умножением на 2 и прибавлением 1).

А уж если допустимы вообще любые умножения и сложения - тогда вообще страшно представить, какой же там будет алгоритм нахождения smile