2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Возведение в 2^n-1 степень.
Сообщение24.06.2011, 11:55 
Заполнить единицами все биты справа от 1 до N-1 , остальные нулями - вот вам самый быстрый алгоритм.

 
 
 
 Re: Возведение в 2^n-1 степень.
Сообщение24.06.2011, 12:35 
Андрей АK в сообщении #461805 писал(а):
Заполнить единицами все биты справа от 1 до N-1 , остальные нулями - вот вам самый быстрый алгоритм.
Покажите, пожалуйста, как с помощью этого алгоритма посчитать $3^3$.

 
 
 
 Re: Возведение в 2^n-1 степень.
Сообщение24.06.2011, 12:45 
Андрей АK в сообщении #461805 писал(а):
Заполнить единицами все биты справа от 1 до N-1 , остальные нулями - вот вам самый быстрый алгоритм.


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

 
 
 
 Re: Возведение в 2^n-1 степень.
Сообщение24.06.2011, 13:55 
Maslov в сообщении #461810 писал(а):
Андрей АK в сообщении #461805 писал(а):
Заполнить единицами все биты справа от 1 до N-1 , остальные нулями - вот вам самый быстрый алгоритм.
Покажите, пожалуйста, как с помощью этого алгоритма посчитать $3^3$.

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

 
 
 
 Re: Возведение в 2^n-1 степень.
Сообщение24.06.2011, 13:56 
Наверное имелось в виду то, что $2^n-1=1111111...1111_2$ ($n$ единиц) в двоичной системе.

 
 
 
 Re: Возведение в 2^n-1 степень.
Сообщение24.06.2011, 13:58 
Polytech в сообщении #461815 писал(а):
Андрей АK в сообщении #461805 писал(а):
Заполнить единицами все биты справа от 1 до N-1 , остальные нулями - вот вам самый быстрый алгоритм.


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

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

 
 
 
 Re: Возведение в 2^n-1 степень.
Сообщение24.06.2011, 18:09 
Андрей АK в сообщении #461835 писал(а):
Этот алгоритм только для степеней двойки.
Насколько я понял автора темы, ему нужен алгоритм для возведения произвольного числа в степень вида $(2^n-1)$, а вовсе не для вычисления степеней двойки.

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

 
 
 
 Re: Возведение в 2^n-1 степень.
Сообщение24.06.2011, 18:22 
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.

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

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

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

 
 
 
 Re: Возведение в 2^n-1 степень.
Сообщение25.06.2011, 11:01 
Цитата:
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.

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

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

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

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group