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).
div and idiv seem to use two registers, one for the quotient, and one for the remainder, is that what you mean? The quotient here is the only thing that we care about,
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.
So you ignore the remainder and shift the quotient register by 2 bits?
Does this work just as well for signed divide? Some of the values you printed are outside the positive range of 32 bit signed integers, do you then just treat these as negative values and use a signed multiply and signed shift?
- Maxime
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")))
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list