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

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

Автор: Kernigan 25.8.2006, 17:22

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

Автор: nostromo 25.8.2006, 17:35

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

Автор: Mayk 25.8.2006, 17:49

Пораскладывать на составляющие?  Пример для x^27: Цитата x3 = x*x*x x9 = x3*x3*x3 x27 = x9*x9*x9 //6 умножений Цитата x2 = x*x x4 = x2*x2 x8 = x4 * x4 x16 = x8 * x8 x27 = x16 * x8 * x2 * x //7 умножений Правда АФАИК нет хорошего алгоритма, который позволяет определять точную  оптимальную последовательностей перемножений. Но можно пораскладывать на нескольких приближенных алгоритмов и перемножать по лучшему результату. Добавлено @ 17:55  PS. Для возведения в x^-27 достаточно расчитать x^27, а потом 1/(x^27).

Автор: nostromo 25.8.2006, 17:57

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

Автор: maxim1000 25.8.2006, 18:49

Цитата(Mayk @  25.8.2006,  16:49 ) Правда АФАИК нет хорошего алгоритма, который позволяет определять точную  оптимальную последовательностей перемножений ну раз нет, то можно придумать  вводим набор переменных x1...xN нам нужно вычислить xN у нас есть x1 каждое перемножение двух известных степеней даёт нам третью (неизвестную на данный момент) потом начинаем перебирать все возможные последовательности перемножений, из них находим кратчайшую может, даже динамическое программирование удастся прикрутить правда есть один недостаток: определение оптимального способа будет занимать больше времени, чем само возведение  так что, думаю, в качестве общего случая более выгодно возведение по степеням двойки - там получается 2*log2 n умножений кроме того, сама степень может буть представлена длинным числом, а чаще всего бывает, что в двоичную систему длинное число переводить очень быстро (или вообще не надо)

Автор: esperant0 25.8.2006, 19:10

=t

Автор: Mayk 25.8.2006, 19:25

Цитата(maxim1000 @  25.8.2006,  22:49 ) правда есть один недостаток: определение оптимального способа будет занимать больше времени, чем само возведение Поэтому я и написал "хорошего". Брутфорс никто не отменял    Но пожалуй да. В принципе для малых показателей N ( N < 1000  ) можно написать N оптимальных ф-ций возведений в степень , а для остальных использовать приближённое разложение (приближённые разложения). (оптимальные писать не руками, естественно   ) Интересная кстати задачка. Может сделаем несколько общих решений для произвольных [но пусть 63 битных] N  и устроим небольшой турнир?

Автор: esperant0 25.8.2006, 22:25

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

Автор: mes 26.8.2006, 11:41

Цитата(Kernigan @  25.8.2006,  17:22 ) Подскажите пожалуйста, как возвести в целую степень число, представленное строкой, более 100 символов. Легче всего возводить число в двоичной системе. То есть вначале надо перевести 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;

Автор: Silent 3.10.2006, 10:02

Быстрое возведение в степень делается так: 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.

Автор: Akina 3.10.2006, 15:29

Цитата(Mayk @  25.8.2006,  18:49 ) нет хорошего алгоритма, который позволяет определять точную  оптимальную последовательностей перемножений Именно такой алгоритм - побитовое представление степени и получение соответствующих возведений в степени, равные степени двойки, с последующим их перемножением, и есть оптимум. Быстрее не получится. Это можно строго доказать, причем доказательство несложное и базируется на том, что нельзя за 1 атомарную операцию перемножить более 2 чисел.

Автор: maxim1000 3.10.2006, 15:56

Цитата(Akina @  3.10.2006,  14:29 ) Именно такой алгоритм - побитовое представление степени и получение соответствующих возведений в степени, равные степени двойки, с последующим их перемножением, и есть оптимум. Быстрее не получится. Это можно строго доказать, причем доказательство несложное и базируется на том, что нельзя за 1 атомарную операцию перемножить более 2 чисел.  а пример Mayk'а? если там всё правильно (ошибок я не увидел), то используя "троичный" способ умножений получается на 1 меньше...

Автор: esperant0 3.10.2006, 18:50

Цитата(Akina @ 3.10.2006,  15:29) Цитата(Mayk @  25.8.2006,  18:49 ) нет хорошего алгоритма, который позволяет определять точную  оптимальную последовательностей перемножений Именно такой алгоритм - побитовое представление степени и получение соответствующих возведений в степени, равные степени двойки, с последующим их перемножением, и есть оптимум. Быстрее не получится. Это можно строго доказать, причем доказательство несложное и базируется на том, что нельзя за 1 атомарную операцию перемножить более 2 чисел. Ваш алгоритм не ТОЧНЫЙ. читайте выше.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)