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")))
Afficher les réponses par date
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
On 2010-10-13, at 4:16 PM, chevalma@iro.umontreal.ca wrote:
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,
No I mean the x86 "mul" instruction, as in
movl $3435973837,%edx mull %edx
which multiplies the 32 bit %eax by the 32 bit 3435973837 (which was put in %edx). The result of the multiplication is always stored in %edx:%eax (a total of 64 bits). So if after the multiplication %edx is right shifted by 2 bits, it will contain the initial content of %eax divided by 5.
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?
I only know that it works for unsigned numbers. You'll have to check what happens with negative integers.
Marc
which multiplies the 32 bit %eax by the 32 bit 3435973837 (which was
put in %edx). The result of the multiplication is always stored in %edx:%eax (a total of 64 bits). So if after the multiplication %edx is right shifted by 2 bits, it will contain the initial content of %eax divided by 5.
I think the back-end, in its current state, doesn't give access to the high order bits. It only assigns a register dest to the low order bits if I'm not mistaken (the low order bits are the ones usually regarded as the "result" without overflow, I believe?). Can you confirm this, Erick?
I only know that it works for unsigned numbers. You'll have to check
what happens with negative integers.
Ok. If/when the back-end supports it, I'll implement the algorithm and check the results. It seems pretty obvious, at least, that dividing by powers of 2 using the signed right shift should work.
- Maxime
I tried your code a little bit. Am I right in thinking that there are actually few divisors for which this works? For 32 bit values, it seems the multipliers easily fall outside of the signed 32 bit range.
- Maxime
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")))
Tachyon-list mailing list Tachyon-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/tachyon-list
-
chevalma＠iro.umontreal.ca -
Marc Feeley -
Maxime Chevalier-Boisvert