Re: [racket-users] Interpolating Polynomial in Newton Form

[Jens Axel Søgaard]

Use Horner's rule.

/Jens Axel


2015-11-06 22:27 GMT+01:00 Dave Yrueta :

> Hi All —
>
> Given a list of constants (a0, a1… an) and a list of x-values (x0,
> x1,….xn), I want to write a function in Racket that produces the function
> p(x) = a0 + a1(x - x0) + a2(x - x0)(x - x1) + a3(x - x0)(x - x1) (x - x2) +
> ….+ an(x - x0)(x - x1)…(x - xn), or the interpolating polynomial in Newton
> form.   My understanding of functions that produce functions is limited to
> what’s in HtDP, and this example (I think) goes beyond that.  Any tips or
> advice would be much appreciated!
>
> Cheers,
> Dave Yrueta
>
> --
> You received this message because you are subscribed to the Google Groups
> "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to racket-users+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>



-- 
-- 
Jens Axel Søgaard

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Interpolating Polynomial in Newton Form

[Dave Yrueta]

Yes, I can see at least two significant errors in my description.  The first is 
in the sequence definitions.  They should be

 list of constants (a0, a1… an) and a list of x-values (x0, x1,….x(n-1)) 
Similarly, the def of p(x) should read

p(x) = a0 + a1(x - x0) + a2(x - x0)(x - x1) + a3(x - x0)(x - x1) (x - x2) + ….+ 
an(x - x0)(x - x1)…(x - x(n-1)), not

p(x) = a0 + a1(x - x0) + a2(x - x0)(x - x1) + a3(x - x0)(x - x1) (x - x2) + ….+ 
an(x - x0)(x - x1)…(x - xn).  Thank you for correcting me! 

Here are some examples:

Data Defs:
x is a real number
lox is (listof x)

;;NewtonPx : (lox lox -> (x -> x)
;; accepts two list of numbers, returns a function equivalent to the 
interpolating polynomial in Netwton form that accepts a number and returns a 
number
(define (NewtonPx lox loa) ….)

Ex #1
(define lox1 ‘(1 2))
(define loa1 (4 5 6))

(NewtonPx lox1 loa1) -> (lambda (x) (+ 4 (* 5(- x 1)) (* 6 (- x 1) (- x 2 
and ( (NewtonPx lox1 loa1) 2) ->  9

Ex. #2
(define lox2 '(4 2 7))
(define loa2 ‘(9 8 6 3))

(NewtonPx lox1 loa1) -> (lambda (x) (+ 9 (* 8 (- x 4)) (* 6 (- x 4) (- x 2)) (* 
3 (- x 4) (- x 2) (- x 7 and  ( (NewtonPx lox2 loa2) 2) -> -7

I realize now that the function I’m after doesn’t require anything as fancy as 
macros — judicious use of loops should do.  Still, I’m wondering if there is a 
macro-based solution that I can use to study as an entry point to this subject. 
 

Cheers, 
DY

 










> On Nov 6, 2015, at 6:43 PM, Matthias Felleisen  wrote:
> 
> 
>> On Nov 6, 2015, at 9:07 PM, dyrueta  wrote:
>> 
>> Hi All --
>> 
>> I'm hoping the answer to the question below will serve as an intro to 
>> macros, a subject I've been interested in for awhile but haven't had time to 
>> look into much.  Here goes, fingers crossed:
>> 
>> Given a list of constants (a0, a1… an) and a list of x-values (x0, x1,….xn), 
>> I want to design a function in Racket that produces an interpolating 
>> polynomial in Newton form, or p(x) = a0 + a1(x - x0) + a2(x - x0)(x - x1) + 
>> a3(x - x0)(x - x1) (x - x2) + ….+ an(x - x0)(x - x1)…(x - xn).   My 
>> understanding of functions that produce functions is limited to what’s in 
>> HtDP, and this example (I think) goes beyond that (and hopefully into 
>> macros).   
>> 
>> Any tips or advice would be much appreciated!
> 
> 
> Let’s assume I don’t know what you’re talking about. But we do know together 
> that HtDP requests examples for problems that you’re not quite familiar with. 
> So we work through 3 instances of this problem: 
> 
> #lang racket
> 
> (require plot)
> 
> (define ((make-p-0 a0 a1) x0 x1)
>  (define (p x)
>(+ a0
>   (* a1 (- x x0
>  p)
> 
> [plot (function ((make-p-0 1 2) 3 4)) #:x-min -10 #:x-max +10]
> 
> (define ((make-p-1 a0 a1 a2) x0 x1 x2)
>  (define (p x)
>(+ a0
>   (* a1 (- x x0))
>   (* a2 (- x x0) (- x x1
>  p)
> 
> [plot (function ((make-p-1 1 2 3) 3 4 5)) #:x-min -10 #:x-max +10]
> 
> (define ((make-p-2 a0 a1 a2 a3) x0 x1 x2 x3)
>  (define (p x)
>(+ a0
>   (* a1 (- x x0))
>   (* a2 (- x x0) (- x x1))
>   (* a3 (- x x0) (- x x1) (- x x2
>  p)
> 
> [plot (function ((make-p-2 1 2 3 4) 3 4 5 6)) #:x-min -10 #:x-max +10]
> 
> I threw in the plots for fun. Now I think one of two things is wrong: 
> 
> — your description (making the a-sequence as long as the x-sequence) 
> — or my understanding of your description. 
> 
> Correct me.

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Interpolating Polynomial in Newton Form

[Matthias Felleisen]

#lang racket

;; -
;; the macro approach 
(module macro-server racket
  
  (provide
   ;; syntax: (make-p number? (number? ...) (number? ...))
   ;; in (make-p a0 (a ...) (x ...)) must be of equal length
   ;; the result is a newton polynomial
   make-p)
  
  (define-syntax-rule
(make-p a0 (a ...) (x ...))
(lambda (y)
  (+ a0 (newton y 1 (a ...) (x ...)
  
  (define-syntax newton
(syntax-rules ()
  [(_ y factor () ()) 0]
  [(_ y factor (a1 a ...) (x1 x ...))
   (let ((delta (* factor (- y x1
 (+ (* a1 delta) (newton y delta (a ...) (x ...])))

(module macro-client racket
  (require (submod ".." macro-server) plot rackunit)
  
  (define ((make-p-0 a0))
(define (p x)
  (+ a0))
p)
  
  (check-equal? [plot (function (make-p 1 () ())) #:x-min -10 #:x-max +10]
[plot (function ((make-p-0 1))) #:x-min -10 #:x-max +10])
  
  (define ((make-p-1 a0 a1) x0)
(define (p x)
  (+ a0
 (* a1 (- x x0
p)
  
  (check-equal? [plot (function (make-p 1 (2) (3))) #:x-min -10 #:x-max +10]
[plot (function ((make-p-1 1 2) 3)) #:x-min -10 #:x-max +10])
  
  (define ((make-p-2 a0 a1 a2) x0 x1)
(define (p x)
  (+ a0
 (* a1 (- x x0))
 (* a2 (- x x0) (- x x1
p)
  
  (check-equal?
   [plot (function (make-p 1 (2 3) (3 4))) #:x-min -10 #:x-max +10]
   [plot (function ((make-p-2 1 2 3) 3 4)) #:x-min -10 #:x-max +10])
  
  (define ((make-p-3 a0 a1 a2 a3) x0 x1 x2)
(define (p x)
  (+ a0
 (* a1 (- x x0))
 (* a2 (- x x0) (- x x1))
 (* a3 (- x x0) (- x x1) (- x x2
p)
  
  (check-equal?
   [plot (function (make-p 1 (2 3 4) (3 4 5))) #:x-min -10 #:x-max +10] 
   [plot (function ((make-p-3 1 2 3 4) 3 4 5)) #:x-min -10 #:x-max +10])
  )

;; -
;; the functional approach

(module server racket
  (provide
   (contract-out
(make-p
 ;; compute the newton polynomial 
 (->d ((a0 number?))
  ()
  #:rest a* (listof number?)
  (_r (->d ()
   ()
   #:rest x* (and/c (listof number?)
(lambda (a*)
  (= (length x*) (length a*
   (_s (-> number? number?
  
  (define ((make-p a0 . a*) . x*)
(define (p y)
  (define-values (sum _)
(for/fold ([sum a0][factor 1]) ([a a*][x x*])
  (define delta (* factor (- y x)))
  (values (+ sum (* a delta)) delta)))
  sum)
p))

(module client racket
  (require (submod ".." server))
  (require plot rackunit)
  
  (define ((make-p-0 a0))
(define (p x)
  (+ a0))
p)
  
  (check-equal? [plot (function ((make-p 1))) #:x-min -10 #:x-max +10]
[plot (function ((make-p-0 1))) #:x-min -10 #:x-max +10])
  
  (define ((make-p-1 a0 a1) x0)
(define (p x)
  (+ a0
 (* a1 (- x x0
p)
  
  (check-equal? [plot (function ((make-p 1 2) 3)) #:x-min -10 #:x-max +10]
[plot (function ((make-p-1 1 2) 3)) #:x-min -10 #:x-max +10])
  
  (define ((make-p-2 a0 a1 a2) x0 x1)
(define (p x)
  (+ a0
 (* a1 (- x x0))
 (* a2 (- x x0) (- x x1
p)
  
  (check-equal?
   [plot (function ((make-p 1 2 3) 3 4)) #:x-min -10 #:x-max +10]
   [plot (function ((make-p-2 1 2 3) 3 4)) #:x-min -10 #:x-max +10])
  
  (define ((make-p-3 a0 a1 a2 a3) x0 x1 x2)
(define (p x)
  (+ a0
 (* a1 (- x x0))
 (* a2 (- x x0) (- x x1))
 (* a3 (- x x0) (- x x1) (- x x2
p)
  
  (check-equal?
   [plot (function ((make-p 1 2 3 4) 3 4 5)) #:x-min -10 #:x-max +10] 
   [plot (function ((make-p-3 1 2 3 4) 3 4 5)) #:x-min -10 #:x-max +10])
  
  )

(require 'client 'macro-client)

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[racket-users] Interpolating Polynomial in Newton Form

[dyrueta]

Hi All --

I'm hoping the answer to the question below will serve as an intro to macros, a 
subject I've been interested in for awhile but haven't had time to look into 
much.  Here goes, fingers crossed:

Given a list of constants (a0, a1… an) and a list of x-values (x0, x1,….xn), I 
want to design a function in Racket that produces an interpolating polynomial 
in Newton form, or p(x) = a0 + a1(x - x0) + a2(x - x0)(x - x1) + a3(x - x0)(x - 
x1) (x - x2) + ….+ an(x - x0)(x - x1)…(x - xn).   My understanding of functions 
that produce functions is limited to what’s in HtDP, and this example (I think) 
goes beyond that (and hopefully into macros).   

Any tips or advice would be much appreciated!

Cheers, 
DY

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [racket-users] Interpolating Polynomial in Newton Form

[Matthias Felleisen]

> On Nov 6, 2015, at 9:07 PM, dyrueta  wrote:
> 
> Hi All --
> 
> I'm hoping the answer to the question below will serve as an intro to macros, 
> a subject I've been interested in for awhile but haven't had time to look 
> into much.  Here goes, fingers crossed:
> 
> Given a list of constants (a0, a1… an) and a list of x-values (x0, x1,….xn), 
> I want to design a function in Racket that produces an interpolating 
> polynomial in Newton form, or p(x) = a0 + a1(x - x0) + a2(x - x0)(x - x1) + 
> a3(x - x0)(x - x1) (x - x2) + ….+ an(x - x0)(x - x1)…(x - xn).   My 
> understanding of functions that produce functions is limited to what’s in 
> HtDP, and this example (I think) goes beyond that (and hopefully into 
> macros).   
> 
> Any tips or advice would be much appreciated!


Let’s assume I don’t know what you’re talking about. But we do know together 
that HtDP requests examples for problems that you’re not quite familiar with. 
So we work through 3 instances of this problem: 

#lang racket

(require plot)

(define ((make-p-0 a0 a1) x0 x1)
  (define (p x)
(+ a0
   (* a1 (- x x0
  p)

[plot (function ((make-p-0 1 2) 3 4)) #:x-min -10 #:x-max +10]

(define ((make-p-1 a0 a1 a2) x0 x1 x2)
  (define (p x)
(+ a0
   (* a1 (- x x0))
   (* a2 (- x x0) (- x x1
  p)

[plot (function ((make-p-1 1 2 3) 3 4 5)) #:x-min -10 #:x-max +10]

(define ((make-p-2 a0 a1 a2 a3) x0 x1 x2 x3)
  (define (p x)
(+ a0
   (* a1 (- x x0))
   (* a2 (- x x0) (- x x1))
   (* a3 (- x x0) (- x x1) (- x x2
  p)

[plot (function ((make-p-2 1 2 3 4) 3 4 5 6)) #:x-min -10 #:x-max +10]

I threw in the plots for fun. Now I think one of two things is wrong: 

 — your description (making the a-sequence as long as the x-sequence) 
 — or my understanding of your description. 

Correct me. 

-- 
You received this message because you are subscribed to the Google Groups 
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.