Here is the algorithm for division by a constant, which does a multiplication and a shift.
The first command-line argument is the divisor, and the second argument is the width of the word (in the example, 32 bit words). The machine multiplication instruction typically produces a result that is twice the word width, in 2 registers (the hi 32 bits and the lo 32 bits of the result). So if a 34 bit right shift is needed (for example when dividing by 5), it is really a right shift of the hi 32 bit register by 2 bits.
Marc
% ./div.scm 5 32 given x is a 32 bit wide integer: x/5 = (x * 3435973837) / 2^34 % ./div.scm 17 32 given x is a 32 bit wide integer: x/17 = (x * 4042322161) / 2^36 % ./div.scm 128 32 given x is a 32 bit wide integer: x/128 = (x * 1) / 2^7 % cat div.scm #!/usr/bin/env gsi-script
(define (log2 x) ;; retourne le plus petit k tel que 2^k >= x (if (= x 1) 0 (+ 1 (log2 (quotient x 2)))))
(define (div2 x) ;; retourne le plus grand k tel que x mod 2^k = 0 (if (odd? x) 0 (+ 1 (div2 (quotient x 2)))))
(define (div divisor width) (let* ((a (+ (log2 (- divisor 1)) 1)) (m (ceiling (/ (expt 2 (+ width a)) divisor))) (b (div2 m)) (shift (+ width (- a b))) (m/2^b (quotient m (expt 2 b)))) (list m/2^b shift)))
(define (main divisor-str width-str) (let* ((divisor (string->number divisor-str)) (width (string->number width-str)) (params (div divisor width)) (m/2^b (car params)) (shift (cadr params)))
(print "given x is a " width " bit wide integer:\n") (print "x/" divisor " = (x * " m/2^b ") / 2^" shift "\n")))