Create polynomials

[cameyo]

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?

[rrq]

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)))

[cameyo]

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

[rickyboy]

Here's a version of the lambda builder that constructs the body according to the https://en.wikipedia.org/wiki/Horner%27s_method">method of Horner.

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)))))