; approximate median

(define rand ; knuth random number generator with shuffle box
  (let* ((a 69069) (c 1234567) (m 4294967296) (k 32)
         (seed 19380110) ; Happy Birthday DEK!
         (next (lambda ()
           (set! seed (modulo (+ (* a seed) c) m)) seed))
         (init (lambda (seed) (let ((box (make-vector k)))
           (do ((j 0 (+ j 1))) ((= j k) box)
             (vector-set! box j (next))))))
         (box (init seed)))
    (lambda args
      (when (pair? args)
        (set! seed (modulo (car args) m)) (set! box (init seed)))
      (let* ((j (quotient (* k seed) m)) (n (vector-ref box j)))
        (set! seed (next)) (vector-set! box j seed) (/ n m)))))

(define (randint . args)
  (let ((lo (if (pair? (cdr args)) (car args) 0))
        (hi (if (pair? (cdr args)) (cadr args) (car args))))
    (+ lo (floor (* (rand) (- hi lo))))))

(define (copysign magnitude sign)
  (* (abs magnitude) (if (negative? sign) -1 1)))

(define (median n gen tolerance)
  (let loop ((n n) (x (gen)) (average 0.0) (median 0.0))
    (if (zero? n) median
      (let ((average (+ (* (- x average) 0.1) average)))
        (loop (- n 1) (gen) average
              (+ (copysign (* average tolerance) (- x median))
                 median))))))

(define (gen) (randint 101))

(display  (median 100000 gen 0.01)) (newline)