2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: сложность вычисления биномиального коэффициента
Сообщение26.02.2010, 19:29 
А мне вот интересно, можно ли делать как-то так:
Возвести в степень число $1000...0001$, а затем собирать биномиальные коэффициенты в различных разрядах?

Например, при $n=10$:
$1001^{10}= 1,010,045,120,210,252,210,120,045,010,001$ (запятые ввел для удобства).

 
 
 
 Re: сложность вычисления биномиального коэффициента
Сообщение26.02.2010, 21:02 
Аватара пользователя
Батороев в сообщении #292687 писал(а):
А мне вот интересно, можно ли делать как-то так:
Возвести в степень число $1000...0001$, а затем собирать биномиальные коэффициенты в различных разрядах?

Сделать-то можно (причем лучше работать с двоичной системой счисления), вот только будет ли от этого прок. Прикинуть сложность можно так:
Для простоты оценим биномиальные коэффициенты $\binom{n}{k}$ величиной $2^n$. Тогда число которое нам нужно возводить в степень $n$ нужно брать равным $2^n+1$. Сложность его возведения в степень $n$ можно оценить сложностью $O(\log n)$ умножений $n^2$-битных чисел, что суммарно дает сложность $O(n^2\log^2 n)$, что хуже чем у метода, основанного на рекуррентной формуле.

 
 
 
 Re: сложность вычисления биномиального коэффициента
Сообщение26.02.2010, 21:14 
Аватара пользователя
Всё-таки я так и не понял из этого обсуждения, какой наиболее быстрый алгоритм вычисления $\binom{n}{k}$ при неограниченной памяти.

-- Сб фев 27, 2010 00:17:31 --

Умножение $n \cdot k$, по видимому, следует трактовать как $\log_2 k$ сложений чисел длины $\log_2 k + \log_2 n$. Сложение же чисел $n + k$ требует $O(\max\{ \log_2 n, \log_2 k \})$ времени.

 
 
 
 Re: сложность вычисления биномиального коэффициента
Сообщение26.02.2010, 22:12 
Аватара пользователя
Профессор Снэйп в сообщении #292744 писал(а):
Всё-таки я так и не понял из этого обсуждения, какой наиболее быстрый алгоритм вычисления $\binom{n}{k}$ при неограниченной памяти.

Зависит от соотношения $n$ и $k$.
Профессор Снэйп в сообщении #292744 писал(а):
Умножение $n \cdot k$, по видимому, следует трактовать как $\log_2 k$ сложений чисел длины $\log_2 k + \log_2 n$.

Мы считали $n$ и $k$ "одноячеечными" числами (например, $<2^{31}$ на 32-битной архитектуре), для практических применений вряд ли нужны большие. А для таких чисел, умножение и сложение можно считать атомарными операциями, требующими константное время.

 
 
 
 Re: сложность вычисления биномиального коэффициента
Сообщение26.02.2010, 23:39 
Аватара пользователя
Кстати, а сколько тактов работы процессора занимают сложение и умножение? Или я отстал от жизни и сейчас всё это уже не в тактах меряется?

 
 
 
 Re: сложность вычисления биномиального коэффициента
Сообщение26.02.2010, 23:47 
Единицы тактов. Однозначно сказать нельзя, т.к. исполнение инструкций может перекрываться.
Из арифметических операций только деление осталось медленным.

 
 
 [ Сообщений: 21 ]  На страницу Пред.  1, 2


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