arithmetic-encoding.rkt

(define (density symbol)
  (list-ref
    (list 0 (/ 25 100) (/ 55 100) (/ 80 100) (/ 100 100))
    symbol))

(define (next-section a b i)
  (let ([l (- b a)])
       (cons
           (+ a (* l (density (- i 1))))
           (+ a (* l (density i))))))

(define (interval sequence)
  (define (iter a b tail)
    (if (null? tail)
        (cons a b)
        (let ([section (next-section a b (car tail))])
            (iter (car section) (cdr section) (cdr tail)))))
  (iter 0 1 sequence))

(define (include-power-of-2? a b)
  (define (iter i)
    (writeln i)
    (if (< a i) i (iter (* 2 i))))
  (< (iter 1) b))

(define (code interval)
  (define a (car interval))
  (define b (cdr interval))
  (define (iter c d i)
    (if [include-power-of-2? (* i c) (* i d)]
        i
        (iter c d (+ i 1))))
  (iter (/ (denominator b) (numerator b))
        (/ (denominator a) (numerator a)) 1))

(writeln (interval (list 1 2 1 3 4)))

(writeln
  (code (interval (list 1 2 1 3 4))))