exercices/arithmetic.lsp

   1 #!/usr/bin/env newlisp
   2
   3 ;O(N)
   4 (define (Puissance1 P N)
   5   (cond
   6     ((= N 0) 1)
   7     ((= N 1) P)
   8     ((< N 0) (div 1 (Puissance1 P (- N))))
   9     ((* P (Puissance1 P (- N 1))))))
  10 (println "Puissance1")
  11 (println (Puissance1 5 5))
  12 (println (Puissance1 2 12))
  13
  14 ;(trace true)
  15
  16 ;O(log N)
  17 (define (Puissance2 P N)
  18   (cond
  19     ((= N 1) P)
  20     ((= N 2) (* P P))
  21     ((> N 2)
  22      (cond
  23        ((= (mod N 2) 0) (Puissance2 (Puissance2 P 2) (/ N 2)))
  24        ((* P (Puissance2 (Puissance2 P 2) (/ (- N 1) 2))))))))
  25 (println "Puissance2")
  26 (println (Puissance2 5 5))
  27 (println (Puissance2 2 12))
  28
  29 ;(trace nil)
  30
  31 ; https://fr.wikipedia.org/wiki/Algorithme_d%27Euclide
  32 (define (pgcd N P)
  33   (cond
  34     ((< N P) (pgcd P N))
  35     ((= N P) N)
  36     ((= P 0) N)
  37     ((pgcd (- N P) P))))
  38 (println "PGCD")
  39 (println (pgcd 12 4))
  40 (println (pgcd 25 5))
  41 (println (pgcd 21 7))
  42
  43 ;(trace true)
  44
  45 ; https://fr.wikipedia.org/wiki/Coefficient_binomial
  46 ; relation de pascal commenté
  47 (define (comb N P)
  48   (cond
  49     ((= P 0) 1)
  50     ((= N P) 1)
  51     ;((+ (comb (- N 1) P) (comb (- N 1) (- P 1))))))
  52     ((/ (* N (comb (- N 1) (- P 1))) P))))
  53 (println "comb")
  54 (println (comb 5 4))
  55 (println (comb 60 4))
  56 (println "(comb 12 8) = "(comb 12 8))
  57
  58 ;(trace nil)
  59 ;(trace true)
  60
  61 (setq L '(3 7 + 4 2 + *))
  62 (setq M '(4 3 7 + * 2 -))
  63 (setq N '(10 10 5 / +))
  64 (define (calculExp P L)
  65   (cond
  66     ((null? L) (first P))
  67     ; all these conditions could probably be simplified
  68     ((= (first L) '+) (calculExp (cons (+ (P 1) (first P)) (rest (rest P))) (rest L)))
  69     ((= (first L) '-) (calculExp (cons (- (P 1) (first P)) (rest (rest P))) (rest L)))
  70     ((= (first L) '*) (calculExp (cons (* (P 1) (first P)) (rest (rest P))) (rest L)))
  71     ;FIXME: test for divide by zero
  72     ((= (first L) '/) (calculExp (cons (/ (P 1) (first P)) (rest (rest P))) (rest L)))
  73     ((number? (first L)) (calculExp (cons (first L) P) (rest L)))))
  74 (println "calculExp")
  75 (println (calculExp '() L))
  76 ;(trace true)
  77 (println (calculExp '() M))
  78 (println (calculExp '() N))
  79
  80 ;(trace nil)
  81
  82 (setq Q '(+ (* x 0) (* 10 (+ y 0))))
  83 (define (algsimplificator L)
  84   (cond
  85     ((null? L) '())
  86     ; I'm having hard time to find a way of escaping the '(' and ')' characters
  87     ((= (first L) ) (rest L))
  88     ;here is the idea: detect the lower well formed expression: begin with (op and finish with ) where op = + - * / and have only two parameters that are atoms.
  89     ;then if it match a know pattern, simplify it by following the matching rule.
  90     ;do it again on the upper layer recursively until we only have (op A B) that just match no known simplication rules.
  91
  92     ))
  93 (println "algsimplificator")
  94 ;(println algsimplificator(Q))
  95
  96 (define (fibonacci N)
  97   (cond
  98     ((= N 0) 0)
  99     ((= N 1) 1)
 100     ((> N 1) (+ (fibonacci (- N 1)) (fibonacci (- N 2))))))
 101 (println "fibonacci")
 102 ;(println (fibonacci 21))
 103 ;(println (fibonacci 14))
 104 (println (fibonacci 20))
 105 (println (time (fibonacci 20)))
 106
 107 ;(trace true)
 108
 109 (define (fibo:fibo n)
 110   (if (not fibo:mem) (set 'fibo:mem '(0 1)))
 111   (dotimes (i (- n 1))
 112     ;this create a LIFO (or stack) of all previous fibonnaci serie result values
 113     (push (+ (fibo:mem -1) (fibo:mem -2)) fibo:mem -1))
 114   (last fibo:mem))
 115 (println "fibo")
 116 (println (fibo 20))
 117 (println (time (fibo 20)))
 118
 119 ;(trace nil)
 120 ;(trace true)
 121
 122 (setq S '())
 123 (define (Somme3ou5 N)
 124     (dolist (i (sequence 0 N))
 125       (cond
 126         ((= (mod i 3) 0) (setq S (cons i S)))
 127         ((= (mod i 5) 0) (setq S (cons i S)))))
 128     (apply + S))
 129 (println "Somme3ou5")
 130 (println (Somme3ou5 100))
 131
 132 ;(trace nil)
 133
 134 (exit)