Правило Хорнера для полинома с двумя переменными

Question

Правило Хорнера для полинома с двумя переменными

Правило Хорнера используется для упрощения процесса оценки полинома при определенных значениях переменной. https://rosettacode.org/wiki/Horner%27s_rule_for_polynomial_evaluation

Я легко применил метод, используя SML, к полиному с одной переменной, представленному в виде списка int:

fun horner coeffList x = foldr (fn (a, b) => a + b * x) (0.0) coeffList

Это отлично работает. Затем мы можем позвонить, используя:

- val test = horner [1.0, 2.0, 3.0] 2.0;
> val test = 17.0 : real

куда [1.0, 2.0, 3.0] список, представляющий коэффициенты полинома, 2.0 является значением переменной х, и 17.0 является результатом оценки полинома.

Моя проблема такова: у нас есть полином от двух переменных, представленный (список int). N-й элемент в списке высокого уровня будет представлять все полиномиальные члены, содержащие y ^ n, а m-й элемент в списке низкого уровня будет представлять все полиномиальные члены, содержащие x^m.

Например: [[2],[3,0,0,3],[1,2]] это полином

(2 (x ^ 0) (y ^ 0)) +
(3 (x ^ 0) (y ^ 1) + 0 (x ^ 1) (y ^ 1) + 0 (x ^ 2) (y ^ 1) + 3 (x ^ 3) (y ^ 1)) +
(1 (x ^ 0) (y ^ 2) + 2 (x ^ 1) (y ^ 2))

Функция должна возвращать значение полинома по указанным x и y.

Я пробовал различные методы, используя компилятор mlton.

Сначала я попробовал вложенную функцию foldr:

fun evalXY (z::zs) x y = 
        foldr 
        (fn (s, li:list) => 
            s + ((foldr (fn(a, b) => a + b*x) 0 li)*y)
        )
        0 
        z:zs

Вы можете видеть, что я пытаюсь использовать "s" в качестве аккумулятора, как "a" использовалось в примере с одной переменной. Поскольку каждый элемент, обрабатываемый foldr, должен быть сам "foldr'ed", я снова вызываю foldr в функции, описывающей внешний foldr. Я знаю, что этот внутренний сгиб работает нормально, я доказал это выше. * Моя проблема, кажется, в том, что я не могу получить доступ к элементу списка, к которому подключен внешний фолдер, чтобы передать этот список во внутренний фолдер. > Посмотрите, где я использую li во внутреннем сгибе, это моя проблема. *

Затем я попытался применить свою функцию единственной переменной к карте. Я столкнулся с той же проблемой:
```
fun evalXY (z::zs) x y = 
        map 
        (foldr (fn(a, b) => a + b*x) 0 ???)
        z:zs
```
* С этой попыткой я знаю, что я получаю список целых. Я поместил в список int список, в котором внутренние списки были обработаны и возвращены во внешний список в виде целых чисел от foldr. После этого я бы снова свернул, чтобы применить значение y к полиному. Функция здесь должна выглядеть так::: fn evalXY: (список int) * int * int) -> ... -> int list *

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

5

functional-programming sml smlnj polynomial-math mlton

Источник

user7513825 04 фев '17 в 01:13

2 ответа

Другие вопросы по тегам functional-programming sml smlnj polynomial-math mlton

user1031831 04 фев '17 в 20:21 2017-02-04 20:21 · Answer 1 · 2017-02-04 20:21

Ты очень близко Давайте начнем с формализации проблемы. Учитывая коэффициенты C как вложенный список, как вы указали, вы хотите оценить

$\ sum_i \ sum_j C_ {i, j} \ cdot y ^ i x ^ j$

Обратите внимание, что вы можете вытащить $y^i$ с внутренней суммы, чтобы получить

$\ sum_i y ^ i \ left (\ sum_j C_ {i, j} \ cdot x ^ j \ right)$

Посмотрите внимательно на внутреннюю сумму. Это просто многочлен от переменной х с коэффициентами, заданными $C_i$ , В SML мы можем написать внутреннюю сумму с точки зрения вашего horner функционировать как

fun sumj Ci = horner Ci x

Давайте сделаем шаг дальше и определим

$D_i = \ sum_j C_ {i, j} \ cdot x ^ j$

В SML это val D = map sumj C, Теперь мы можем написать оригинальный многочлен в терминах D:

$\ sum_i \ sum_j C_ {i, j} \ cdot x ^ jy ^ i = \ sum_i y ^ i \ left (\ sum_j C_ {i, j} \ cdot x ^ j \ right) = \ sum_i D_i \ cdot y ^ я$

Должно быть ясно, что это просто еще один пример horner, так как у нас есть многочлен с коэффициентами $D_i$ , В SML значение этого многочлена

horner D y

... и мы закончили!

Вот окончательный код:

fun horner2 C x y =
  let
    fun sumj Ci = horner Ci x
    val D = map sumj C
  in
    horner D y
  end

Разве это не мило? Все, что нам нужно, это многократное применение метода Хорнера, и map,

user4996248 04 фев '17 в 16:22 2017-02-04 16:22 · Answer 2 · 2017-02-04 16:22

Ваш второй подход, кажется, на правильном пути. Если вы уже определили horner, что вам нужно сделать, это подать заявку horner к результату отображения horner applied to inner list x по внешнему списку, что-то вроде:

fun evalXY coeffLists x y = horner (map (fn coeffList => horner coeffList x) coeffLists) y

Вы можете заменить два звонка horner по соответствующим сгибам, но это было бы гораздо менее читабельным.

Обратите внимание, что если вы измените порядок двух параметров в horner тогда вы можете закорочены evalXY:

fun horner x coeffList = foldr (fn (a, b) => a + b * x) (0.0) coeffList
fun evalXY x y coeffLists = horner y (map (horner x) coeffLists)

Дело в том, что способ карри работает, если вы используете этот второй порядок, то horner x уже является функцией coeffList так что вам больше не нужна анонимная функция fn coeffList => horner coeffList x, Мораль этой истории заключается в том, что при определении функции карри, вы должны тщательно продумать порядок параметров, поскольку некоторые частичные приложения будут легче создавать, чем другие.

Кстати, SML суетливый. В вашем обсуждении horner ты сказал что назовешь horner list 2, Это должно быть horner list 2.0, Точно так же во второй попытке, используя 0 скорее, чем 0.0 проблематично.