Возведение в 2^n-1 степень.

[Polytech]

Подскажите, существует ли алгоритм быстрого возведения в степень $2^n-1$, но не бинарка.

[Андрей АK]

Заполнить единицами все биты справа от 1 до N-1 , остальные нулями - вот вам самый быстрый алгоритм.

[Maslov]

Андрей АK в сообщении #461805 писал(а):

Заполнить единицами все биты справа от 1 до N-1 , остальные нулями - вот вам самый быстрый алгоритм.

Покажите, пожалуйста, как с помощью этого алгоритма посчитать $3^3$.

[Polytech]

Андрей АK в сообщении #461805 писал(а):

Заполнить единицами все биты справа от 1 до N-1 , остальные нулями - вот вам самый быстрый алгоритм.

С ним, например, в 511 степень нужно возводить за 16 операций, а можно за 12(если я правильно понял, что вы имеете ввиду).

[Андрей АK]

Maslov в сообщении #461810 писал(а):

Андрей АK в сообщении #461805 писал(а):

Заполнить единицами все биты справа от 1 до N-1 , остальные нулями - вот вам самый быстрый алгоритм.

Покажите, пожалуйста, как с помощью этого алгоритма посчитать $3^3$.

Этот алгоритм только для степеней двойки.

[Батороев]

Наверное имелось в виду то, что $2^n-1=1111111...1111_2$ ($n$ единиц) в двоичной системе.

[Андрей АK]

Polytech в сообщении #461815 писал(а):

Андрей АK в сообщении #461805 писал(а):

Заполнить единицами все биты справа от 1 до N-1 , остальные нулями - вот вам самый быстрый алгоритм.

С ним, например, в 511 степень нужно возводить за 16 операций, а можно за 12(если я правильно понял, что вы имеете ввиду).

Нет, всего одна операция.
На ассемблере биты заполняются единицами за одну операцию (ну или за N/R где R - разрядность процессора).

[Maslov]

Андрей АK в сообщении #461835 писал(а):

Этот алгоритм только для степеней двойки.

Насколько я понял автора темы, ему нужен алгоритм для возведения произвольного числа в степень вида $(2^n-1)$, а вовсе не для вычисления степеней двойки.

Polytech, а нельзя для вычисления $a^{2n-1}$ просто $n$ раз возвести в квадрат, а потом результат поделить на $a$? Или деление -- это слишком долго?
И что такое "бинарка"?

[Андрей АK]

Maslov в сообщении #461903 писал(а):

Андрей АK в сообщении #461835 писал(а):

Этот алгоритм только для степеней двойки.

Насколько я понял автора темы, ему нужен алгоритм для возведения произвольного числа в степень вида $(2^n-1)$, а вовсе не для вычисления степеней двойки.

Polytech, а нельзя для вычисления $a^{2n-1}$ просто $n$ раз возвести в квадрат, а потом результат поделить на $a$? Или деление -- это слишком долго?
И что такое "бинарка"?

А я тогда не понял.
Бинарка - это видимо алгоритм быстрого возведения в степень, путем разбиения степени по битам и т.о. оптимизации вычислений (если уже вычислено число a^2, то a^4 получается (a^2)^2 а a^3=(a^2)*a) - количество операций (умножений) равно двоичному логарифму от степени, т.е. N.

Короче алгоритма не существует.

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

Т.е. других алгоритмов не существует.

[Polytech]

Цитата:

Polytech, а нельзя для вычисления $a^{2n-1}$ просто $n$ раз возвести в квадрат, а потом результат поделить на $a$? Или деление -- это слишком долго?
И что такое "бинарка"?

Для деления нужно большое количество операций. А бинарка - возведение в степень путем ее разложения в двоичной системе и произведении соответствующих значений

-- 25.06.2011, 14:02 --

Андрей АK в сообщении #461907 писал(а):

Maslov в сообщении #461903 писал(а):

Андрей АK в сообщении #461835 писал(а):

Этот алгоритм только для степеней двойки.

Насколько я понял автора темы, ему нужен алгоритм для возведения произвольного числа в степень вида $(2^n-1)$, а вовсе не для вычисления степеней двойки.

Polytech, а нельзя для вычисления $a^{2n-1}$ просто $n$ раз возвести в квадрат, а потом результат поделить на $a$? Или деление -- это слишком долго?
И что такое "бинарка"?

А я тогда не понял.
Бинарка - это видимо алгоритм быстрого возведения в степень, путем разбиения степени по битам и т.о. оптимизации вычислений (если уже вычислено число a^2, то a^4 получается (a^2)^2 а a^3=(a^2)*a) - количество операций (умножений) равно двоичному логарифму от степени, т.е. N.

Короче алгоритма не существует.

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

Т.е. других алгоритмов не существует.

Вы правы, это будет тот же самый алгоритм.