Create polynomials

Q&A's, tips, howto's
Locked
cameyo
Posts: 183
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy
Contact:

Create polynomials

Post by 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 all

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

(poly 0)
;-> 5
And then to get the searched values:

Code: Select all

(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 all

  y(x) = 4*x^3 + 5*x^2 + 7*x + 10 
is represented by the function:

Code: Select all

  (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 all

(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 all

(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 all

(poly 0)
;-> 10
And to get the values:

Code: Select all

(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?

ralph.ronnquist
Posts: 228
Joined: Mon Jun 02, 2014 1:40 am
Location: Melbourne, Australia

Re: Create polynomials

Post by ralph.ronnquist »

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 all

(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
Posts: 183
Joined: Sun Mar 27, 2011 3:07 pm
Location: Italy
Contact:

Re: Create polynomials

Post by 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
Posts: 607
Joined: Fri Apr 08, 2005 7:13 pm
Location: Front Royal, Virginia

Re: Create polynomials

Post by rickyboy »

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

Code: Select all

(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 all

> (make-poly-horner (list 3 2 1))
(lambda (x) (add 1 (mul x (add 2 (mul x 3)))))
(λx. x x) (λx. x x)

Locked