Подскажите пожалуйста, как возвести в целую степень число, представленное строкой, более 100 символов.

Наверное, сначала перейти от строки к более удобному представлению, а затем перемножить нужное число раз. Более удобным представлением может оказаться, скажем, хранение числа в виде списка цифр в системе счисления с основанием, которое хорошо ложиться в доступный integer. Для 32-битных целых это может быть 2^32 или, если хочется упростить вывод десятичного представления, например, 1000000000)

Пораскладывать на составляющие? 
Пример для x^27:




Правда АФАИК нет хорошего алгоритма, который позволяет определять точную  оптимальную последовательностей перемножений. Но можно пораскладывать на нескольких приближенных алгоритмов и перемножать по лучшему результату.

Добавлено @ 17:55 
PS. Для возведения в x^-27 достаточно расчитать x^27, а потом 1/(x^27).

Отличная идея. Упустил.

Похоже на то. Нужно учитывать разложнеие числа N (показатель степени) на простые множители. Зато, по крайней мере, всегда можно обойтись [log N]+1, а это не много даже для весьма больших значений N.

ну раз нет, то можно придумать 
вводим набор переменных x1...xN
нам нужно вычислить xN
у нас есть x1
каждое перемножение двух известных степеней даёт нам третью (неизвестную на данный момент)
потом начинаем перебирать все возможные последовательности перемножений, из них находим кратчайшую
может, даже динамическое программирование удастся прикрутить
правда есть один недостаток: определение оптимального способа будет занимать больше времени, чем само возведение 
так что, думаю, в качестве общего случая более выгодно возведение по степеням двойки - там получается 2*log2 n умножений
кроме того, сама степень может буть представлена длинным числом, а чаще всего бывает, что в двоичную систему длинное число переводить очень быстро (или вообще не надо)

=t

Это сообщение отредактировал(а) esperant0 - 25.8.2006, 19:23

Поэтому я и написал "хорошего". Брутфорс никто не отменял   
Но пожалуй да. В принципе для малых показателей N ( N < 1000  )
можно написать N оптимальных ф-ций возведений в степень ,
а для остальных использовать приближённое разложение (приближённые разложения).
(оптимальные писать не руками, естественно   )


Интересная кстати задачка. Может сделаем несколько общих решений для произвольных [но пусть 63 битных] N  и устроим небольшой турнир?   



Это сообщение отредактировал(а) Mayk - 25.8.2006, 19:27

Да, тетта(лог N) это точная оценка.

Легче всего возводить число в двоичной системе. То есть вначале надо перевести 100символьное число в двоичное представление.

Потом перейти к разложению степени на множетели, которые сами являются степенями 2. 

Например, степень 45 = (32+8+4+1) =  2^5 + 2^3 + 2^2 + 2^0

Тогда число a^45 =  а^(2^5) +а^(2^3) +а^ (2^2) +а^ (2^0)


Теперь, чтоб возвести двоичное число в такую (например, 2^5)) степень
нужно сдвинуть двоичное число "влево"  на значение степени нашей степени  (то есть на 5 разрядов) 

Тогда: а^45 = (а shl 5) + (а shl 3) + (а shl 2) + (а shl 0) 


Вот и всё. 

а да:  (а shl 0) = a;









Это сообщение отредактировал(а) mes - 26.8.2006, 22:43

Быстрое возведение в степень делается так:

long long s(int base, int n){ //основание, показатель
    long long a=1;
    while (n!=0){
        if (n&1==1) a*=base;
        base*=base;
                                n>>=1;
    }
    return a;
}

Нужно только переделать ее на длинную арифметику.
Или использовать, скажем, Java.

Именно такой алгоритм - побитовое представление степени и получение соответствующих возведений в степени, равные степени двойки, с последующим их перемножением, и есть оптимум. Быстрее не получится. Это можно строго доказать, причем доказательство несложное и базируется на том, что нельзя за 1 атомарную операцию перемножить более 2 чисел.

а пример Mayk'а?
если там всё правильно (ошибок я не увидел), то используя "троичный" способ умножений получается на 1 меньше...

Ваш алгоритм не ТОЧНЫЙ.

читайте выше.