|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Ponomarev 2:5020/400 11 Jul 2001 11:56:41
To : All
Subject : Re: Скобки расставить. Оптимальное вычисление выражения с несколькими п
--------------------------------------------------------------------------------
Hi!
Vasily Shmelev wrote:
> Hе знаю, поможет ли тебе это, но есть такая схема Горнера,
> когда полином
> Pn = a0 + x*a1 + x^2*a2 + ... + x^n*aN
> = a0 + x*(a1 + x*(a2 + x*(...)));
Про схему Горнера я знаю, но она не работает в случае нескольких
переменных. :(
> Или можно попробовать решать задачу итерационными методами,
> правда, я пока не знаю как.
Что ты подразумеваешь под "итерационными методами"?
Меня интересуют даже смутные идеи на этот счет, потому что
я совершенно не знаю куда рыть. :(
Hа всякий случай повторяю свое письмо, что бы было четко
понятно, чего мне нужно. Меня интересует сам алгоритм упрощения
выражения, а не, допустим, способ его быстрого вычисления.
=8<========================8<========================8<=
Всем известно, что для вычисления полинома с одной переменной
можно применить схему Горнера. А какую схему можно использовать
в случае нескольких переменных?
Итак. Есть выражение представленное ввиде суммы произведений
нескольких переменных. Каким образом можно преобразовать его так,
что бы минимизировать количество умножений (очень "дорогой" операции
в моем случае). Причем, коэффициэнты у всех произведений равны единице
(уж не знаю, облегчит ли это задачу :)
Hапример:
1 + x1*x2*x3 + x1*x2*x4 (6 умножений)
легко преобразуется в
1 + x1*x2 * (x3 + x4) (3 умножения)
В моем случае количество переменных может достигать 70-ти,
а количество комбинаций их различных произведений нескольких тясяч.
Hаверняка, в компиляторах применяется некие приемы оптимизации
вычисления выражений. Какие? Что лучше применить мне в моем случае?
=8<========================8<========================8<=
--
Ponch
mailto:O.Ponomarev@vaz.ru phone: (848-2) 73-83-49
--- ifmail v.2.15dev5
* Origin: AvtoVAZ (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
