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

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

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

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

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

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

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


list lisp polynomial-math
person sam    schedule 30.11.2014    source источник
comment
Это, вероятно, слишком широко, так как то, что лучше всего, будет зависеть от того, что именно вы хотите с ними делать (я знаю, что вы упоминали сложение, вычитание и умножение), ожидаете ли вы иметь разреженные или плотные полиномы (большинство или несколько коэффициентов ненулевой) и т. д. Ответ также вряд ли будет особенно специфичным для Lisp. Многие языки имеют односвязные списки, векторы и хэш-таблицы/словари, и я ожидаю, что большинство ответов, которые вы здесь увидите, будут основаны на них.   -  person Joshua Taylor    schedule 01.12.2014

Ответы (3)


arrow_upward
1
arrow_downward

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

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

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

person robbyphillips    schedule 01.12.2014
comment
Это был самый ясный и интуитивно понятный способ представить это для меня, спасибо. - person sam; 02.12.2014

arrow_upward
1
arrow_downward

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

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

person coredump    schedule 30.11.2014
comment
В этом случае, как бы вы представили что-то вроде «5xy». - person sam; 30.11.2014
comment
Для этого представления 5xy является произведением двух многочленов 5x = #(0 5) и y = #(0 1). Да, не очень оптимально. - person coredump; 30.11.2014
comment
Я не уверен, что понимаю, что вы имеете в виду, в вашем представлении, как бы я, например, сохранил полином (2x^3 + 4xy - 2y -2)? - person sam; 30.11.2014
comment
@ Сэм, ты прав, для таких полиномов это не сработает. Я использовал это для полиномов с одной переменной, для более общего решения вам нужно другое представление. - person coredump; 30.11.2014
comment
Почему многомерный подход, похоже, отлично подходит для этого, не так ли? (2x^3 + 4xy - 2y - 2) равно #((-2 0 0 2) (-2 4 0 0)). 5_xy_ равно #((0 0) (0 5)). - person Svante; 01.12.2014

arrow_upward
0
arrow_downward

Существует несколько способов представления многочленов. Как обычно, выбор представления является компромиссом.

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

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

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

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

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

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

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

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

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

person soegaard    schedule 01.12.2014