;;; Fichier exporap.drs / 2 avril 1999

(define (exponentielle x n)
  (cond ((= n 1) x)
        (else (mat*mat x (exponentielle x (- n 1))))))


(define (expo-rapide x n)
  (cond ((= n 1) x)
        ((even? n) (expo-rapide (mat*mat x x) (/ n 2)))
        (else (mat*mat x (expo-rapide  x (- n 1))))))

;;; Temps de calcul:
;;; (time exp) renvoie le resultat de l'evaluation de exp en affichant
;;; cpu time: ? real time: ? gc time: ? en milliemes de secondes (cpu = real)

(define (affiche-temps x n1 n2)
  (display "n=") (display n1) (newline)
  (display "rapide = ") (time (expo-rapide x n1))
  (display "normal = ") (time (exponentielle x n1))
  (if (< n1 n2) (affiche-temps x (+ n1 10) n2) 'stop))


;;; Produit de matrices:

(define (mat*mat m1 m2)
  (cond ((null? m1) '())
        (else (cons (ligne*mat (car m1) m2)
                    (mat*mat (cdr m1) m2)))))

(define (ligne*col l c)
  (cond ((null? l) 0)
        (else (+ (* (car l) (car c))
                 (ligne*col (cdr l) (cdr c))))))

(define (premiere-col m) (map car m))
(define (reste-col m) (map cdr m))
(define (vide-col? m) (null? (car m)))

(define (ligne*mat l m)
  (cond ((vide-col? m) '())
        (else (cons (ligne*col l (premiere-col m))
                    (ligne*mat l (reste-col m))))))


;;; Quelques matricesnilpotentes:

(define *p3*
'((0 2 2)
  (0 0 2)
  (0 0 0)))

(define *p4*
'((0 2 2 2)
  (0 0 2 2)
  (0 0 0 2)
  (0 0 0 0)))

(define *p16*
'((0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) 
(1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0) 
(1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0) 
(1 1 1 0 1 0 1 1 0 1 1 0 1 1 1 0) 
(1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0) 
(1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0) 
(1 1 1 0 1 0 0 1 0 1 1 0 1 1 1 0) 
(1 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0) 
(1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0) 
(1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 0) 
(1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0) 
(1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0) 
(1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0) 
(1 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0) 
(1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0) 
(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0)))