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

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


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

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

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

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

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

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

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

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

Это сообщение отредактировал(а) maxdiver - 31.5.2008, 21:31