количество сложений и умножений при вычислении формул

[Circiter]

2ewert

Цитата:

Не существуют и в принципе не могут существовать. Но существует типа $O(N\log N)$, что ненамного хуже.

Но в той книге именно такая сложность упоминается (порядка $N$ операций). Я вот специально нашел её перевод и опять увидел там ту же оценку... Хотя вдумчиво читал эту книжку я достаточно давно, все успел забыть (тем более для меня она сложноватой оказалась, всякие там вычеты, кольца, и прочие ужастики из теории чисел, бррр), может что-то и перепутал...

[ewert]

Circiter в сообщении #242669 писал(а):

Но в той книге именно такая сложность упоминается (порядка $N$ операций).

Этого не может быть, потому что этого не может быть никогда. А почему -- потому ли, что перевод неадекватен -- или потому, что неадекватна сама книжка -- разбираться недосуг.

[st256]

Circiter в сообщении #242665 писал(а):

Простите, но может кто-нибудь объяснить простому IT'шнику как вообще можно посчитать выражение, содержащее сложений и умножений, за число операций меньшее чем ?

Я ошибся. Имелось в виду меньше чем $N-1$ сложений на один отсчет. И одно умножение.

Circiter в сообщении #242665 писал(а):

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

Тогда Вы находитесь не на том сайте

Circiter в сообщении #242665 писал(а):

И ещё, в первоначальной версии заголовка темы упоминалась теория графов, но связь с ней почему-то (почти) не обсуждается...

Ну потому, что к сожалению в ней никто не разбирается здесь

ewert в сообщении #242666 писал(а):

Не существуют и в принципе не могут существовать.

А ссылочку? Или повторяется история с дельта-функцией? Помните, я просил дать хоть какое-то определение. Вы сможете привести его хотя бы на этот раз? Знаете, уважаемый, это просто некрасиво. Пришел, чото прокричал увереным голосом и фсё.... Сдулся...

[Xaositect]

ewert в сообщении #242666 писал(а):

Не существуют и в принципе не могут существовать.

Не доказано.
Доказана нижняя оценка $N\log N$ только для какого-то ограниченного класса алгоритмов.

[ewert]

Xaositect в сообщении #242769 писал(а):

Не доказано.

Может, и не доказано. Но обратное (даже если и формально не опровергнуто) -- неправдоподобно.

[Xaositect]

Circiter в сообщении #242665 писал(а):

Простите, но может кто-нибудь объяснить простому IT'шнику как вообще можно посчитать выражение, содержащее $N-1$ сложений и $N$ умножений, за число операций меньшее чем $2N-1$?

Ну вот выражение $axy + bx + c$ содержит 3 умножения и 2 сложения, а считать можно так: $(ay+b)x + c$
Наверное, плохой пример, но больше ничего простого в голову не лезет.

Circiter в сообщении #242665 писал(а):

Конечно, если числа в выражении подчиняются некоторым априорно известным функциональным зависимостям, то, очевидно, оптимизация возможна. Действительно, пусть все $a_i$ равны, тогда вынося за "скобки" достаточно будет произвести лишь операций (кстати, уже в этом случае получается, что изначальное предположение-теоремка неверна...)

Это предположение верно в случае, если $a_i$, $x_i$ - независимые, заранее неизвестные. Ну, например, если они все на вход поступают.

Circiter в сообщении #242665 писал(а):

И ещё, в первоначальной версии заголовка темы упоминалась теория графов, но связь с ней почему-то (почти) не обсуждается... Как переформулировать задачу в терминах этой теории?

Каждому алгоритму можно поставить в соответствие орграф. У этог графа будет столько истоков, сколько есть входных переменных, каждая вершина, кроме стока, помечена операцией, и в нее входят ребра из вершин, соответствующих операндам.

[ewert]

st256 в сообщении #242741 писал(а):

Помните, я просил дать хоть какое-то определение. Вы сможете привести его хотя бы на этот раз?

О хоссподи. Да гляньте в любую книжку. Дельта-функцией формально называется функционал, который каждой пробной функции ставит в соответствие её значение в нуле.

[st256]

Xaositect в сообщении #242769 писал(а):

Доказана нижняя оценка только для какого-то ограниченного класса алгоритмов.

Не-а. Нету такой оценки. Есть оценка для БПФ по основанию два, но она выглядит так:
$\frac N 2 log_2 N$ комплексных умножений.

-- Сб сен 12, 2009 23:34:58 --

ewert в сообщении #242774 писал(а):

Дельта-функцией формально называется функционал, который каждой пробной функции ставит в соответствие её значение в нуле

Сссссылочку! И не поминайте имя Господа в суе...

[Xaositect]

ewert в сообщении #242771 писал(а):

Может, и не доказано. Но обратное (даже если и формально не опровергнуто) -- неправдоподобно.

Я тоже сомневаюсь, но все-таки не доказано.
Вот, кстати, интересная статья по этому поводу. http://www.imc.pi.cnr.it/~codenotti/ps_files/compl.ps

[ewert]

st256 в сообщении #242775 писал(а):

Сссссылочку!

Пожалуйста:

Цитата:

это общеизвестно

-----------------------------------------------
Да, и кстати: никаких "суй" в природе не существует. Существует лишь "всуе".

[st256]

Xaositect в сообщении #242776 писал(а):

Вот, кстати, интересная статья по этому поводу. http://www.imc.pi.cnr.it/~codenotti/ps_files/compl.ps

А чем читают такие файлы?

[Xaositect]

st256 в сообщении #242775 писал(а):

Не-а. Нету такой оценки. Есть оценка для БПФ по основанию два, но она выглядит так: $\frac{N}{2}\log_2 N$ комплексных умножений

Есть несколько оценок при различных ограничениях. У Пападимитриу $N\log N$, если не ошибаюсь.

-- Сб сен 12, 2009 22:48:10 --

st256 в сообщении #242778 писал(а):

А чем читают такие файлы?

GSView: http://pages.cs.wisc.edu/~ghost/gsview/get49.htm

[st256]

ewert в сообщении #242777 писал(а):

st256 в сообщении #242775 писал(а):

Сссссылочку!

Пожалуйста:

Цитата:

это общеизвестно

Поймите меня правильно. Я тут не развлекаюсь, я пытаюсь найти нужную мне информацию. А Вы ведете себя как трехлетний ребенок. Я уже просил Вас не лезть в мои топики, так как Ваши посты (с моей точки зрения некомпетентные) меня раздражают. А Вы этого не осознаете и снова и снова пытаетесь привлечь мое внимание. Ну зачем Вы меня провоцируете? Давайте мирно разойдемся. Вы мне не интересны. Надеюсь, как и я Вам.

Удачи. Я Вас поставил в игнор.

[ewert]

st256 в сообщении #242780 писал(а):

Я Вас поставил в игнор.

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

[Circiter]

2st256

Цитата:

Я ошибся. Имелось в виду меньше чем $N-1$ сложений на один отсчет. И одно умножение.

У-у-у-у. Ну со сложениями-то понятно, там их и так $N-1$, но вот как одним умножением можно обойтись -- не представляю (по крайней мере на произвольных данных).

А отсчетом вы называете значение $y$ в ваших обозначениях?

Цитата:

Тогда Вы находитесь не на том сайте

Ну и куда бы вы меня послали?

2Xaositect

Цитата:

Каждому алгоритму можно поставить в соответствие орграф. У этог графа будет столько истоков, сколько есть входных переменных, каждая вершина, кроме стока, помечена операцией, и в нее входят ребра из вершин, соответствующих операндам.

Ok. И как его использовать? E.g., искать кратчайший путь?


2All

Парочка идей (наивных):

1. Двупроходный алгоритм: сначала анализируем данные, выявляя зависимости в этой выборке; а потом используя эти зависисимости упрощаем формулку, что облегчает её вычисление (здесь верхняя оценка все равно будет составлять $2N-1+\alpha$ операций, где $\alpha$ -- сложность первого прохода). Этот алгоритм кажется имеет что-то общее с задачей сжатия данных, i.e. сначала используем избыточность во входных данных для нахождения более компактной записи формулы, а потом, несмотря на чрезмерную сложность первой подзадачи, используем компактно записанную формулу для "оптового" вычисления на разных выборках. Кстати,в этой теме Xaositect уже упоминал о возможности более эффективного вычисления полиномов в большом количестве точек нежели в одной.
2. Можно и по другому поступить, а именно как-нибудь закодировать исходные данные в виде чисел в какой-нибудь хитрожо хитрой "системе счисления", и потом уже в ней считать...
3. Не совсем понимаю, почему в этой теме так много было сказано о свертке и о Фурье-трансформации, но может быть поправленная st256 оценка ($N-1$ сложений и одно умножение) получена именно делением сложности свертки на количество отсчетов? То есть мы берем две последовательности, сворачиваем их, а в результате получаем другую последовательность, один из элементов которой выражается по формуле из первого поста темы и обходится в среднем дешево (типа $N$ операций).

P.S.: Я сильно заблуждаюсь?
P.P.S.: Ну когда же появятся квантовые компьютеры?