Fix the recursive optimized power calculation

[TD_LISP.git] / exercices / arithmetic.lsp

#!/usr/bin/env newlisp

;O(N)
(define (Puissance1 P N)
  (cond
    ((= N 0) 1)
    ((= N 1) P)
    ((< N 0) (div 1 (Puissance1 P (- N))))
    ((* P (Puissance1 P (- N 1))))))
(println "Puissance1")
(println (Puissance1 5 5))
(println (Puissance1 2 12))

;(trace true)

;O(log N)
(define (Puissance2 P N)
  (cond
    ((= N 1) P)
    ((= N 2) (* P P))
    ((> N 2)
     (cond
       ((= (mod N 2) 0) (Puissance2 (Puissance2 P 2) (/ N 2)))
       ((* P (Puissance2 (Puissance2 P 2) (/ (- N 1) 2))))))))
(println "Puissance2")
(println (Puissance2 5 5))
(println (Puissance2 2 12))

;(trace nil)

; https://fr.wikipedia.org/wiki/Algorithme_d%27Euclide
(define (pgcd N P) 
  (cond
    ((< N P) (pgcd P N))
    ((= N P) N)
    ((= P 0) N)
    ((pgcd (- N P) P))))
(println "PGCD")
(println (pgcd 12 4))
(println (pgcd 25 5))
(println (pgcd 21 7))

;(trace true)

; https://fr.wikipedia.org/wiki/Coefficient_binomial
; relation de pascal commenté
(define (comb N P) 
  (cond
    ((= P 0) 1)
    ((= N P) 1)
    ;((+ (comb (- N 1) P) (comb (- N 1) (- P 1))))))
    ((/ (* N (comb (- N 1) (- P 1))) P))))
(println "comb")
(println (comb 5 4))
(println (comb 60 4))
(println "(comb 12 8) = "(comb 12 8))

;(trace nil)

(setq L '(3 7 + 4 2 + *))
(setq P '())
(define (calculExp P L)
  (cond
    ((null? L) 0)
    ((= (first L) '+) (+ (first P) (calculExp (rest P) (rest L)))) 
    ((= (first L) '-) (- (first P) (calculExp (rest P) (rest L))))
    ((= (first L) '*) (* (first P) (calculExp (rest P) (rest L))))
    ;FIXME: test for divide by zero
    ((= (first L) '/) (/ (first P) (calculExp (rest P) (rest L))))
    ((cons (first L) (calculExp P (rest L))))))    
;(println (calculExp P L))

(exit)