... this page is part of the Web Site of George North ...
Differentiate a Polynomial
Differentiate a Polynomial
Simplify as much as possible
by: George North
Spring 1995
Program Language Structure
CSCI 4501
Spring 1995
Dr. Jaime Nino
Programed in Scheme
a functional language similar to LISP
Loading "Gemini: .. :Homework 2.sch"
Differentiate an expression with respect to - x -
Enter an expression to Differentiate (0 to exit): (+ x 3)
Answer is: 1
Exp ? (- x y)
Ans = 1
Exp ? (* x y)
Ans = y
Exp ? (/ x y)
Ans = (/ y (** y 2))
Exp ? (** x 3)
Ans = (** x 2)
Exp ? (sin x)
Ans = (cos x)
Exp ? (cos x)
Ans = (* -1 (sin x))
Exp ? (tan x)
Ans = (sec2 x)
Exp ? (ln x)
Ans = (/ 1 x)
Exp ? x
Ans = 1
Exp ? y
Ans = 0
Exp ? (+ (* y (** x 2)) (* x (** 2)))
Ans = (+ (* y x) (+ (* x (Not a valid expression ** 2)) (** 2)))
Exp ? (+ (* y (** x 2)) (* x (** x 2)))
Ans = (+ (* y x) (+ (* x x) (** x 2)))
Exp ? (* y (** x 2))
Ans = (* y x)
Exp ? (* x (** x 2))
Ans = (+ (* x x) (** x 2))
Exp ? (* x)
Ans = (Not a valid expression * x)
Exp ? (/ x y)
Ans = (/ y (** y 2))
Exp ? (/ y x)
Ans = (/ y (** x 2))
Exp ? (ln (** x 2))
Ans = (/ x (** x 2))
Exp ? (/ x (** x 2))
Ans = (/ (- (** x 2) (* x x)) (** (** x 2) 2))
Exp ? (/ (- (** x 2) (* x x)) (** (** x 2) 2))
Ans = (/ (- (* (** (** x 2) 2) (- x (+ x x))) (* (- (** x 2) (* x x)) (* (** x 2) x))) (**
(** (** x 2) 2) 2))
Exp ? (/ (- (* (** (** x 2) 2) (- x (+ x x))) (* (- (** x 2) (* x x)) (* (** x 2) x))) (**
(** (** x 2) 2) 2))
Ans = (/ (- (* (** (** (** x 2) 2) 2) (- (+ (* (** (** x 2) 2) -1) (* (- x (+ x x))
(* (** x 2) x))) (+ (* (- (** x 2) (* x x)) (+ (** x 2) (* x x))) (* (* (** x 2)
x) (- x (+ x x)))))) (* (- (* (** (** x 2) 2) (- x (+ x x))) (* (- (** x 2) (* x
x)) (* (** x 2) x))) (* (** (** x 2) 2) (* (** x 2) x)))) (** (** (** (** x 2) 2) 2) 2))
Exp ? (/ (cos x) (sin x))
Ans = (/ (- (* (sin x) (* -1 (sin x))) (* (cos x) (cos x))) (** (sin x) 2))
Exp ? (cos 1)
Ans = 0.
Exp ? (sin 0)
Ans = 0
Exp ? (** x y)
Ans = (** x (- y 1))
Exp ? (** x 4)
Ans = (** x 3)
Exp ? (+ (+ (** x 2) (+ (* 3 x) (* 4 x))) 12 )
Ans = (+ x 7)
Exp ? (+ (** (+ x 4) 2) (** (+ x 3) 2))
Ans = (+ (+ x 4) (+ x 3))
Exp ? (+ (+ x 4) (+ x 3))
Ans = 2
Exp ? (* x 4)
Ans = 4
Exp ? (/ (* x 4) (+ (+ x 4) (+ x 3)) )
Ans = (/ (- (* (+ (+ x 4) (+ x 3)) 4) (* (* x 4) 2)) (** (+ (+ x 4) (+ x 3)) 2))
Exp ? (* (* x 4) (+ (+ x 4) (+ x 3)) )
Ans = (+ (* (* x 4) 2) (* (+ (+ x 4) (+ x 3)) 4))
Exp ? (ln (* x 4) (+ (+ x 4) (+ x 3)) )
Ans = (/ 4 (* x 4))
Exp ? (ln (* 4 4) (+ (+ x 4) (+ x 3)) )
Ans = 0
Exp ? (** 4 x)
Ans = 0
Exp ? (** 4 (ln x))
Ans = 0
Exp ? (** (ln x) 5
)
Ans = (* (** (ln x) 4) (/ 1 x))
Exp ? (** )
Ans = (Not a valid expression **)
Exp ? (* y)
Ans = (Not a valid expression * y)
Exp ? (cos )
Ans = (Not a valid expression cos)
Exp ? ()
Ans = (Not a valid expression)
Source Code
; Homework 2, CSCI 4501
; by George North
; March 8,1995
; Program: Symbolic Differentiation
;
; Name:
deriv
; a scheme function with two arguments: "exp" and "var"
;
;
Syntax
(deriv exp var)
- take the derivative of "exp" relative to "var"
;
;
Preconditions
:
;
; "exp" is defined as:
; <operator> -> + | - | * | / | ** | cos | sin | tan | ln
; <letter> -> a | b | c | ... | x | y | z
; <symbol> -> <letter> | <letter><symbol>
; <digit> -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
; <constant> -> {digit}
; <operand> -> <symbol> | <constant> | <exp>
; <exp> -> ( <operator> <operand> [ <operand> ] )
; | '<symbol> | <constant>
; -- Note: (1) operators cos | sin | tan | ln - can have only
; 1 operand.
; -- Note: (2) operators + | - | * | / | ** - must have 2 operands.
; -- Note: (3) expression is a valid Scheme Integer, Symbol or List
;
; "var" is defined as:
; <var> -> <symbol>
;
;
;
Examples of expressions
:
; (+ ( * x (** (cos x) 2)) (* x 5) 1)
; (* x y)
; 12
; c
;
; Sample use of this function:= (deriv (* x y) x)
; intermediate output := (+ (* x 0) (* 1 y)
; final output := (+ y)
; my hoped for best output := y
;
;
;
Postcondition
: the derivative of "exp" relative to "var",
; simplified as much as possible
;
;
;
Note
: Invalid expressions will be skipped and an error reported,the remaining
; nested expressions will be evaluated ... not very robust error checking.
;
;
;
Algorithm
:
; 1. Recursively process a prefix expression (a valid scheme list
; 1.1 if an element is an integer, return 0
; 1.2 if an element is a symbol then
; return a 1 if the symbol is equal to the derive symbol
; else return a 0 (same as a constant)
; 2. This element must be a list, if not report an error
; 2.1 Verify list is valid prefix expression using rules above
; 2.1.1 (car exp) must be a valid operator
; 2.1.2 (cdr exp) must have 1 or 2 operands by operator
; 3. For every operator, apply basic differentiation rules
; 4. Simplify result if possible. i.e. multiplication by 0
;
;
;------------------------------------------------------------------------------
;
Function declarations
;------------------------------------------------------------------------------
; Function: valid_opcode?
;
; Preconditions: takes one argument:
; a_code: <operator> to be verified
;
; Postcondition: returns: 0 if an invalid <operator>
; 1 if <operator> requires 1 operand
; 2 if <operator> requires 2 operands
;
; Example: (valid_opcode? '*) returns 2 (valid)
; (valid_opcode? 'sin) returns 1 (valid)
; (valid_opcode? '%) returns 0 (invalid opcode)
;
(define valid_opcode?
(lambda (a_code)
;; return 0 (invalid opcode) after checking all possibilities
(case a_code
('+ 2)
('- 2)
('* 2)
('/ 2)
('** 2)
('sin 1)
('cos 1)
('tan 1)
('ln 1)
(else 0)
)
)
)
;------------------------------------------------------------------------------
; Function: valid_exp?
;
; Preconditions: requires one arguments: an expression to verify
;
; Postcondition: using <expression> rules given above,
; returns: #t if a valid expression
; returns: an error message if NOT a valid expression
;
; Example: (valid_exp? '(* x y)) returns #t
; (valid_exp? '(* x) returns "Not enough operands"
; (valid_exp? '(% x) returns "Not a valid operator"
;
(define valid_exp?
(lambda (exp)
(if (or (not (list? exp)) (null? exp) ) (cons "Not a valid expression" exp)
(let ( (op (car exp)) )
(if (list? op) (valid_exp? op)
(let ( (n_of_operands (valid_opcode? op) )
(operands (cdr exp))
)
(cond ( (eq? n_of_operands 0)
(cons "Not a valid operator" exp) )
( (null? operands) (cons "Missing operands" exp) )
( (eq? n_of_operands 1) #t )
(else (if (null? (cdr operands))
(cons "Not enough operands" exp)
#t
)
)
)
)
)
)
)
)
)
;------------------------------------------------------------------------------
; Function: deriv
;
; Preconditions: requires two arguments: exp - an expression as defined above
; var - a symbol as defined above
;
; Postcondition: returns the derivative of "exp" relative to "var"
; d/dx[?] = d/d"var"["exp"] = ???
;
; Example: (deriv '(* x y) 'x) returns y
;
(define deriv
(lambda (exp var)
;; if "exp" is an integer, derivative is 0
(cond ((integer? exp) 0)
;; if "exp" is a symbol equal to "var" then derivative is 1 else 0
((symbol? exp) (if (eq? exp var) 1 0))
;; if "exp" is not a list than it is not a valid expression
((eq? (valid_exp? exp) #t)
(let ((operator (car exp)) (operands (cdr exp)))
;; identify operator, derive for its operands
(case operator
('+ (deriv_plus_or_mins operator operands var))
('- (deriv_plus_or_mins operator operands var))
('* (deriv_mult operands var))
('/ (deriv_divd operands var))
('** (deriv_powr operands var))
('sin (deriv_sin operands var))
('cos (deriv_cos operands var))
('tan (deriv_tan operands var))
('ln (deriv_ln operands var))
)
)
)
(else (cons "Not a valid expression" exp))
)
)
)
;------------------------------------------------------------------------------
; Function: .+or-
; Preconditions: requires 3 arguments: operator (+ or -)
; symbol or number
; symbol or number
; Postcondition: returns a simplified expression, eliminating
; addition or subtraction of 0
(define .+or-
(lambda (operator u v)
(let ( (r (cons operator (list u v))) )
(cond ( (and (number? u) (number? v) ) (eval r) )
( (eq? u 0) v)
( (eq? v 0) u)
( else r)
)
)
)
)
; Function: .+
; Rationale, make code easier to read by substituting for .+or-
(define .+
(lambda (u v)
(.+or- '+ u v)
)
)
; Function: .-
; Rationale, make code easier to read by substituting for .+or-
(define .-
(lambda (u v)
(.+or- '- u v)
)
)
;------------------------------------------------------------------------------
; Function: deriv_plus_or_mins
; Preconditions: requires two arguments: operator (+ or -)
; operands - a list of 2 <operand>'s
; var - a symbol
; Postcondition: returns the derivative of "exp" relative to "var"
; using the rule for derivation of addition
; rule: d/dx[u+v] = (d/dx[u]) + (d/dx[v])
; or: (+ (d/dx[u]) (d/dx[v]) )
(define deriv_plus_or_mins
(lambda (operator operands var)
(let ( (du (deriv (car operands) var))
(dv (deriv (cadr operands) var))
)
(.+or- operator du dv)
)
)
)
;------------------------------------------------------------------------------
; Function: .*
;
; Preconditions: requires 2 arguments: 1- symbol or number
; 2- symbol or number
;
; Postcondition: returns a simplified expression, eliminating
; multiplication by 0 or 1
;
(define .*
(lambda (u v)
(let ( (r (cons '* (list u v))) )
(cond ( (and (number? u) (number? v) ) (eval r) )
( (eq? u 0) 0)
( (eq? v 0) 0)
( (eq? u 1) v)
( (eq? v 1) u)
( else r)
)
)
)
)
;------------------------------------------------------------------------------
; Function: deriv_mult
;
; Preconditions: requires two arguments: operands - a list of 2 <operand>'s
; var - a symbol
;
; Postcondition: returns the derivation of "exp" relative to "var"
; using the rule for derivation of multiplication
; rule: d/dx[u*v] = (u * d/dx[v]) + (v * d/dx[u])
; or: (+ (* u d/dx[v]) (* v d/dx[u])
;
(define deriv_mult
(lambda (operands var)
(let* ( (u (car operands) )
(v (cadr operands) )
(du (deriv u var) )
(dv (deriv v var) )
)
(.+ (.* u dv) (.* v du))
)
)
)
;------------------------------------------------------------------------------
; Function: ./
;
; Preconditions: requires 2 arguments: 1- symbol or number
; 2- symbol or number
;
; Postcondition: returns a simplified expression, eliminating
; division 0 1
;
(define ./
(lambda (u v)
(let ( (r (cons '/ (list u v))) )
(cond ( (eq? v 0) '("Division by 0") )
( (and (number? u) (number? v) ) (eval r) )
( (eq? u 0) 0)
( (eq? v 1) u)
( else r)
)
)
)
)
;------------------------------------------------------------------------------
; Function: deriv_divd
;
; Preconditions: requires two arguments: operands - a list of 2 <operand>'s
; var - a symbol
;
; Postcondition: returns the derivation of "exp" relative to "var"
; using the rule for derivation of division
; rule: d/dx[u/v] = ( (v * d/dx[u]) - (u * d/dx[v]) ) / v**2
; or (/ ( (- (* v d/dx[u]) (* u d/dx[v])) ) (** v 2) )
;
(define deriv_divd
(lambda (operands var)
(let* ( (u (car operands) )
(v (cadr operands) )
(du (deriv u var) )
(dv (deriv v var) )
)
(./ (.- (.* v du) (.* u dv)) (.** v 2)
)
)
)
)
;------------------------------------------------------------------------------
; Function: eval**
; Preconditions: requires 2 arguments: 1- number
; 2- number
; Postcondition: returns 1st number multiplied by itself 2nd number times
; u ** n
(define eval**
(lambda (u n)
(if (eq? n 0) 1
(* u (eval** u (- n 1)))
)
)
)
;------------------------------------------------------------------------------
; Function: .**
; Preconditions: requires 2 arguments: 1- symbol or number
; 2- symbol or number
; Postcondition: returns a simplified expression, eliminating
; powers of 0 or 1
(define .**
(lambda (u n)
(let ( (r (cons '** (list u n))) )
(cond ( (and (number? u) (number? n) ) (eval** u n) )
( (eq? u 0) 0)
( (eq? n 0) 1)
( (eq? u 1) 1)
( (eq? n 1) u)
( else r)
)
)
)
)
;------------------------------------------------------------------------------
; Function: deriv_powr
;
; Preconditions: requires two arguments: operands - a list of 2 <operand>'s
; var - a symbol
;
; Postcondition: returns the derivation of "exp" relative to "var"
; using the rule for derivation of u to power of n
; rule: d/dx[u**n] = (nu ** n-1) * d/dx[u])
; or (* (** u (- n 1) ) d/dx[u])
;
(define deriv_powr
(lambda (operands var)
(let* ( (u (car operands) )
(n (cadr operands) )
(du (deriv u var) )
)
(.* (.** u (.- n 1) ) du)
)
)
)
;------------------------------------------------------------------------------
; Function: .sin
;
; Preconditions: requires 1 argument: symbol or number
;
; Postcondition: returns a simplified expression, eliminating
; sin of a constant number
;
(define .sin
(lambda (u)
(let ( (r (cons 'sin (list u))) )
(cond ( (number? u) (eval r) )
( else r)
)
)
)
)
;------------------------------------------------------------------------------
; Function: deriv_cos
;
; Preconditions: requires two argument: operands - a list of 1 <operand>
; var - a symbol
;
; Postcondition: returns the derivation of "exp" relative to "var"
; using the rule for derivation of cosine
; rule: d/dx[cos u] = -1 * (sin u) * d/dx[u]
; or: (* -1 (* (sin u) d/dx[u]) )
;
(define deriv_cos
(lambda (operands var)
(let* ( (u (car operands) )
(du (deriv u var) )
)
(.* (.* -1 (.sin u)) du)
)
)
)
;------------------------------------------------------------------------------
; Function: .cos
;
; Preconditions: requires 1 argument: symbol or number
;
; Postcondition: returns a simplified expression, eliminating
; sin of a constant number
;
(define .cos
(lambda (u)
(let ( (r (cons 'cos (list u))) )
(cond ( (number? u) (eval r) )
( else r)
)
)
)
)
;------------------------------------------------------------------------------
; Function: deriv_sin
;
; Preconditions: requires two argument: operands - a list of 1 <operand>
; var - a symbol
;
; Postcondition: returns the derivation of "exp" relative to "var"
; using the rule for derivation of sine
; rule: d/dx[sin u] = (cos u) * (d/dx[u])
; or: (* (cos u) d/dx[u])
;
(define deriv_sin
(lambda (operands var)
(let* ( (u (car operands) )
(du (deriv u var) )
)
(.* (.cos u) du)
)
)
)
;------------------------------------------------------------------------------
; Function: deriv_tan
;
; Preconditions: requires two argument: operands - a list of 1 <operand>
; var - a symbol
;
; Postcondition: returns the derivation of "exp" relative to "var"
; using the rule for derivation of cosine
; rule: d/dx[u*v] = ((sec ** 2) u) * d/dx[u])
; or: (* ((sec ** 2) u) d/dx[u] )
;
(define deriv_tan
(lambda (operands var)
(let* ( (u (car operands) )
(du (deriv u var) )
)
(if (eq? du 0) 0 (.* (cons 'sec2 (list u)) du)
)
)
)
)
;------------------------------------------------------------------------------
; Function: deriv_ln
;
; Preconditions: requires two arguments: operands - a list of 1 <operand>
; var - a symbol
;
; Postcondition: returns the derivation of "exp" relative to "var"
; using the rule for derivation of natural logarithm
; rule: d/dx[u*v] = (u * d/dx[v]) + (v * d/dx[u])
; or: (+ (* u d/dx[v]) (* v d/dx[u])
;
(define deriv_ln
(lambda (operands var)
(let* ( (u (car operands) )
(du (deriv u var) )
)
(./ du u)
)
)
)
;------------------------------------------------------------------------------
; the driver function
;------------------------------------------------------------------------------
;
;
(define (run_homework_2)
(newline)
(display "Differentiate an expression with respect to - x -")
(newline)
(newline)
(display "Enter an expression to Differentiate (0 to exit): ")
(let ((exp (read)))
(if (or (not (eof-object? exp)) (not (= exp 0) ) )
(let ( (dif (deriv exp 'x)) )
(newline)
(display "Answer is: ")
(display dif)
(newline)
(newline)
(run_hw2)
)
)
)
)
(define (run_hw2)
(display "Exp ? ")
(let ((exp (read)))
(if (or (not (eof-object? exp)) (not (= exp 0) ) )
(let ( (dif (deriv exp 'x)) )
(display "Ans = ")
(display dif)
(newline)
(run_hw2)
)
)
)
)
(run_homework_2)