Print Page - Create polynomials

Title: Create polynomials
Post by: cameyo on August 25, 2019, 08:45:03 AM

Suppose we have the polynomial y (x) = 3*x^2 - 7*x + 5 and we want to calculate the values of y for x ranging from 0 to 10 (with step 1).

We can define a function that represents the polynomial:

Code Select Expand
(define (poly x)
  (+ 5 (mul 7 x) (mul 3 (pow x 2))))

(poly 0)
;-> 5

And then to get the searched values:

Code Select Expand
(for (x 0 10) (println x { } (poly x)))
;-> 0 5
;-> 1 15
;-> 2 31
;-> 3 53
;-> 4 81
;-> 5 115
;-> 6 155
;-> 7 201
;-> 8 253
;-> 9 311
;-> 10 375

Since the polynomials have a well-defined structure, we can write a function that takes the coefficients of a polynomial and returns a function that represents the polynomial:

For example, the polynomial:

Code Select Expand
  y(x) = 4*x^3 + 5*x^2 + 7*x + 10

is represented by the function:

Code Select Expand
  (lambda (x) (add 10 (mul x 7) (mul (pow x 2) 5) (mul (pow x 3) 4)))

Our function must therefore construct a new lambda function that represents the polynomial (we work on the lambda function as if it were a list).

Code Select Expand
(define (make-poly coeff)
  (local (fun body)
    (reverse coeff)
    (setq fun '(lambda (x) x)) ;funzione lambda base
    (setq body '()) ;corpo della funzione
    (push 'add body -1)
    (push (first coeff) body -1) ;termine noto
    (push (list 'mul 'x (coeff 1)) body -1) ;termine lineare
    (for (i 2 (- (length coeff) 1))
      (push (list 'mul (list 'pow 'x i) (coeff i)) body -1)
    )
    (setq (last fun) body) ;modifica corpo della funzione
    fun
  )
)

In this way we can define a new "poly" function that represents our polynomial:

Code Select Expand
(setq poly (make-poly '(4 5 7 10)))
;-> (lambda (x) (add 10 (mul x 7) (mul (pow x 2) 5) (mul (pow x 3) 4)))

Evaluating the polynomial for x = 0 we obtain the constant term:

Code Select Expand
(poly 0)
;-> 10

And to get the values:

Code Select Expand
(for (x 0 10) (println x { } (poly x)))
;-> 0 10
;-> 1 26
;-> 2 76
;-> 3 184
;-> 4 374
;-> 5 670
;-> 6 1096
;-> 7 1676
;-> 8 2434
;-> 9 3394
;-> 10 4580

Do you known a better/elegant method to create lambda functions for polynomials?

Title: Re: Create polynomials
Post by: rrq on August 25, 2019, 08:57:12 PM

I'm not sure about "better/more elegant", but it's always fun and interesting to explore alternative newlisp articulations. I rendered this one, as an iterative though rather functional in style, "hiding" the iteration in a map primitive:

Code Select Expand
(define (make-poly coeff)
  (let ((rank (length coeff))
        (polyterm (fn (k) (case (dec rank)
                                (0 k)
                                (1 (list 'mul 'x k))
                                (true (list 'mul (list 'pow 'x rank) k))))))
    (push (cons 'add (reverse (map polyterm coeff))) (copy '(fn (x))) -1)))

Title: Re: Create polynomials
Post by: cameyo on August 26, 2019, 01:23:28 AM

Thanks ralph.ronnquist.

I'm looking for a simple way to build "Lagrange Polynomial Interpolation". It is a bit more complex than polynomials.

Have a nice day.

cameyo

Title: Re: Create polynomials
Post by: rickyboy on August 27, 2019, 05:43:23 PM

Here's a version of the lambda builder that constructs the body according to the method of Horner (//https).

Code Select Expand
(define (make-poly-horner coeffs)
  (push (if (< (length coeffs) 2)
            (first coeffs)
          (apply (fn (acc c)
                   (list 'add c (cons 'mul (list 'x acc))))
                 coeffs
                 2))
        (copy '(fn (x)))
        -1))

To give you an idea of what this looks like:

Code Select Expand
> (make-poly-horner (list 3 2 1))
(lambda (x) (add 1 (mul x (add 2 (mul x 3)))))

newLISP Fan Club

Forum => newLISP in the real world => Topic started by: cameyo on August 25, 2019, 08:45:03 AM