Απλά μαθηματικά με LISP.

December 3, 2010 at 05:05 - by eelvex   |   no comments (Leave a comment)

Share on RedditShare on FacebookShare on Google+Tweet about this on TwitterShare on StumbleUponPrint this page


[TOC]

Μέσος όρος

Μια απλή συνάρτηση μέσου όρου.

(defun average (nums)
  (/ (reduce #'+ nums)
      (length nums)))

μερικά παραδείγματα:

> (average '(1 2 3 4))
5/2
> (average (loop for i to 100 collect i))
50
> (average '(#C(0 1) 1 ))  ; Μιγαδικοί
#C(1/2 1/2)

Παραγώγιση

Θα φτιάξουμε μια συνάρτηση d που θα δέχεται μια έκφραση και μια μεταβλητή παραγώγισης και θα μας επιστρέφει την παράγωγο της έκφρασης, ως εξής:

(defun d (expression var)
  ...)

Παράδειγμα:

> (d '(+ (sin x) x) 'x)
"cos(x) + 1"

 \frac{d(\sin(x) + x)}{dx} = \cos(x) + 1

>  (d '(* (exp y) y) yx)
"((exp(y)  * y)  + exp(y) ) "

\frac{d(ye^y)}{dy} = e^yy + e^y

Διαβάζουμε την έκφραση

που είναι της μορφής (πράξη έκφραση-1 [έκφραση-2]). Πχ.το \sin(x) + x είναι (+ (sin x) x), άρα πράξη = "+", έκφραση-1 = "(sin x)" και έκφραση-2 = "x".

(let ((op (first expression))
       (f   (second expression))
       (g  (third expression))) ... )
; g -> nil αν δεν υπάρχει έκφραση-2
Ορίζουμε τις παραγώγους df, dg (αναδρομικά)
(let ((df (d f var))
      (dg (d g var))) ... )
Ορίζουμε τους βασικούς κανόνες
  • dx = 1
  • dh = 0 (h σταθερή ως προς x)
  • d(f + g) = df + dg
  • d(f - g) = df - dg
  • d(f * g) = df g + f dg
  • d(f / g) = df/g - f dg/g^2
(if (atom expression)
    (if (eq expression var)
       1 0) ; Οι δύο πρώτοι κανόνες
 (case op
   (+ (list '+ df dg))
   (- (list '- df dg))
   (* (list '+
                (list '* df g)
                (list '* f dg)))
   (/ (list '-
                (list '/ df g)
                (list '/ (list '* f dg)
                         (list '* g g))))))
Έτοιμο
(defun d (expression var)
  (if (atom expression)
    (if (eq expression var)
      1 0)                        
    (let* ((op (first expression))
       (f   (second expression))
       (g  (third expression))
       (df (d f var))
       (dg (d g var)))
      (case op
    (+ (list '+ df dg))
    (- (list '- df dg))
    (* (list '+
         (list '* df g)
         (list '* f dg)))  
    (/ (list '-
         (list '/ df g)
         (list '/ (list '* f dg)
               (list '* g g))))))))

Μπορούμε πολύ εύκολα να το επεκτείνουμε προσθέτοντας κανόνες απλοποίησης ή κανόνες για άλλες συναρτήσεις, πχ για την sin() και την exp()

(case op
     ...
    (exp (list '* df expression))
    (sin (list '* df (list 'cos f))))

Αριθμοί Fibonacci (tail recursive)

Χρησιμοποιούμε την αναδρομή F(n, a, b) = F(n-1, b, a+b), F(0,a,b) = a. Το "labels" μπαίνει για ευκολία: να μπορούμε να καλούμε (fibonacci n) αντί (fibonacci n 0 1).

(defun fibonacci (n)
 (labels ((fib-tr (n a b)
       (if (zerop n)
        a
        (fib-tr (1- n) b (+ a b)))))
  (fib-tr n 0 1)))

Λόγω του tail-recursion, μπορούμε άνετα να υπολογίσουμε τον 30000ο αριθμό fibonacci (22ms) ενώ με ένα απλοϊκό recursion  (+ (fibonacci (1- n)) (fibonacci (- n 2))) ήδη από τον 45ο είναι άβολα τα πράματα (45s).

(time (fibonacci 30000))

Evaluation took:
  0.027 seconds of real time
  0.022111 seconds of total run time (0.019051 user, 0.003060 system)
  [ Run times consist of 0.003 seconds GC time, and 0.020 seconds non-GC time. ]
  81.48% CPU
  71,020,388 processor cycles
  39,763,184 bytes consed
 
19042435673462438748500976847175750289440229160233351927339118405204480186334015645055143398261
49631374646268041440688856308385005560365774031061971819892894792971414339261146902465648344930
82628835531989332440953142111541549920917976020744635281408398688209952783539056482888371523133
...
97555130614783032625712814963740147386298196451593410722797807059680187465689980167167579318510
85594809396320544086719336015145194967885808440864695192876846039732476947907308218104433670979
60000

Λύση της f(x) = 0

Με τη μέθοδο Newton - Raphson μια προσέγγιση της λύσης x είναι η x = x_0 - \frac{f(x_0)}{f'(x_0)} όταν η x_0 είναι μια προηγούμενη προσέγγιση της λύσης. Την παράγωγο της f, την υπολογίζουμε και αυτή με προσέγγιση από τον τύπο: f'(x) \equiv \frac{f(x+h) - f(x-h)}{2h} για ένα μικρό h.

(defun d (f x &optional (h 0.001d0))
 "Προσέγγιση παραγώγου της f στο σημείο x"
  (/ (- (funcall f (+ x h)) (funcall f (- x h)))
     (* 2 h)))

(defun newton (f x0)
  (loop for x = x0
        then (- x (/ (funcall f x) (d f x)))
        repeat 1000
        finally (return x)))

Το παραπάνω δίνει άριστα αποτελέσματα για καλά συμπεριφερόμενες συναρτήσεις. Πχ:

(newton #'(lambda (x) (- (exp x) 5)) 1)
; exp(x) - 5 =0 => x = ln(5)
1.609438
(newton #'(lambda (x) (- (* x x) 3)) 5)
; x^2 - 3 = 0 => x = sqrt(3)
1.7320508075688774d0
No tips yet.
Be the first to tip!
Like this post? Tip me with bitcoin!

197MRTJQ5rcvHX2LQfLTcBNfV6xsvcZS2N

Share on RedditShare on FacebookShare on Google+Tweet about this on TwitterShare on StumbleUponPrint this page
{ Tags: }

no comments

RSS / trackback

respond

Real Time Analytics