#!/usr/bin/env newlisp
-(define (Puissance P N)
+;O(N)
+(define (Puissance1 P N)
(cond
((= N 0) 1)
((= N 1) P)
- ((< N 0) (div 1 (Puissance P (- N))))
- ((* P (Puissance P (- N 1))))))
-(println (Puissance 5 5))
+ ((< N 0) (div 1 (Puissance1 P (- N))))
+ ((* P (Puissance1 P (- N 1))))))
+(println "Puissance1")
+(println (Puissance1 5 5))
+
+;(trace true)
+
+;O(log N)
+(define (Puissance2 P N)
+ (cond
+ ((= N 0) 1)
+ ((= N 1) P)
+ ((> N 1)
+ (cond
+ ((= (mod N 2) 0) (Puissance2 (Puissance2 P 2) (/ N 2)))
+ ((* P (Puissance2 (Puissance2 P 2) (/ (- 1 N) 2))))))))
+(println "Puissance2")
+;(println (Puissance2 5 5))
+
+;(trace nil)
; https://fr.wikipedia.org/wiki/Algorithme_d%27Euclide
(define (pgcd N P)
((= 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
(define (comb N P)
(cond
((= P 0) 1)
((= N P) 1)
- ((+ (comb (- 1 N) P) (comb (- 1 N) (- 1 P))))))
-;(println (comb 5 4))
+ ((+ (comb (- N 1) P) (comb (- N 1) (- P 1))))))
+(println "comb")
+(println (comb 5 4))
+(println (comb 60 4))
+
+;(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)