Лучший способ хранить многозначные полиномы в Лиспе

Question

Мне нужно хранить полиномы в моей программе lisp для сложения, вычитания и умножения. Но не могу найти простой способ его хранения.

Я рассмотрел следующий путь

(2x^3 + 2x + 4y^3 - 2z) в списке списков, где каждый список представляет собой список количества каждой силы

= ( (0 2 0 2) (0 0 0 4) (0 2))

Но неопределенная длина каждого списка и потенциальная длина может стать проблемой.

Есть ли общепринятый способ хранить их в lisp, который позволяет максимально легко складывать, вычитать и умножать их вместе?

Answer 1

Предполагая, что вы заранее знаете количество возможных переменных, вы можете выразить каждый термин следующим образом: (constant x-exponent y-exponent z-exponent ...), затем 5xy^2 было бы (5 1 2 0)и полное выражение будет просто список этих терминов.

Если вы хотите иметь возможность обрабатывать любое количество произвольных переменных, вам необходимо составить ассоциативный список в соответствии с ((constant 5) (a 0) (b 3) (z 23) (apple 13)),

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

Answer 2

Может быть, эта идея поможет вам частично. Вы можете представить полином как вектор, когда индекс будет степенью, а элемент - коэффициентом, а первый элемент - вашей переменной. Я имею в виду 5* х ^3 + 10* х ^2 + 40х + 50 будет выглядеть #(50 40 10 5), Работать с таким представлением легко, но, похоже, он не очень оптимален для больших степеней, таких как x^100.

Многопараметрический полином может быть представлен в виде N-мерного массива, где N - количество переменных.

Answer 3

Есть несколько способов представления полиномов. Как обычно, выбор представительства - это компромисс.

Одним из способов является список ассоциаций от порядка к коэффициенту, который обычно сортируется в соответствии с порядком.

12x ^ 2 + 11x + 10 ((2. 12) (11. 1) (10. 0))

Если вам нужно вычислить с разреженными полиномами, то это представление является эффективным с точки зрения пространства. х ^200 просто ((200 . 1)).

Если ваши вычисления состоят в основном из не разреженных полиномов, векторное представление более эффективно с точки зрения пространства:

12x ^ 2 11x + 10 (вектор 10 11 12)

Длина вектора минус один дает порядок многочлена.

Если вам нужны многочлены от нескольких переменных, существуют варианты представлений. В частности, вы можете посмотреть представление в Maxima:

http://maxima.sourceforge.net/docs/manual/maxima_14.html

Если у вас есть "Парадигмы программирования искусственного интеллекта: тематические исследования в Common LISP" Питера Норвига, есть хорошая глава о полиномах.