## Booth’s Algorithm

### April 12, 2013

Our code closely tracks the code from Wikipedia:

`(define (booth lt? xs)`

(define (eq? a b)

(and (not (lt? a b)) (not (lt? b a))))

(let* ((n (len xs)) ; length of cycle

(xv (make-vector (+ n n))) ; elements of cycle, repeated

(fv (make-vector (+ n n) -1)) ; failure function

(k 0)) ; current minimum rotation

(do ((i 0 (+ i 1)) (xs xs (cdr xs))) ((= n i))

(vector-set! xv i (car xs))

(vector-set! xv (+ i n) (car xs)))

(do ((j 1 (+ j 1))) ((= (+ n n) j))

(let ((i (vector-ref fv (- j k 1))))

(while (and (not (= i -1))

(not (eq? (vector-ref xv j)

(vector-ref xv (+ k i 1)))))

(if (lt? (vector-ref xv j) (vector-ref xv (+ k i 1)))

(set! k (- j i 1)))

(set! i (vector-ref fv i)))

(if (and (= i -1)

(not (eq? (vector-ref xv j)

(vector-ref xv (+ k i 1)))))

(begin

(if (lt? (vector-ref xv j) (vector-ref xv (+ k i 1)))

(set! k j))

(vector-set! fv (- j k) -1))

(vector-set! fv (- j k) (+ i 1)))))

(let loop ((i 0) (zs (list)))

(if (= i n) (reverse zs)

(loop (+ i 1) (cons (vector-ref xv (+ i k)) zs))))))

Then the cyclic equality tester checks that the two cyclic lists have the same length, calls `booth`

on each, and checks if the two outputs are the same.

`(define (ceq? lt? xs ys)`

(and (= (len xs) (len ys))

(equal? (booth lt? xs) (booth lt? ys))))

Here is the same list of examples as the prior exercise:

`> (ceq? < (cycle 1 2 3 4) (cycle 1 2 3 4))`

#t

> (ceq? < (cycle 1 2 3 4) (cycle 2 3 4 1))

#t

> (ceq? < (cycle 1 2 3 4) (cycle 3 4 1 2))

#t

> (ceq? < (cycle 1 2 3 4) (cycle 4 1 2 3))

#t

> (ceq? < (cycle 1 2 3 4) (cycle 1 2 3 5))

#f

> (ceq? < (cycle 1 1 1 1) (cycle 1 1 1 1))

#t

> (ceq? < (cycle 1 1 1 1) (cycle 1 1 1 2))

#f

> (ceq? < (cycle 1 1 1 1) (cycle 1 1 1))

#f

You can run the program at http://programmingpraxis.codepad.org/kpl1ksXq.

Pages: 1 2