Hello,
I tested the use of 12 padding bits for 64bit boxed integers. Everything seemed to work fine, for the most part, except that a few unit tests failed with the exception:
we don't yet support multi-digit divisors
I'm guessing some of the values produced during constant propagation are outside of what is representable with a single big digit. Marc, would you have time to implement support for multiple big digit divisors?
- Maxime
Afficher les réponses par date
On 2011-03-23, at 5:08 PM, chevalma@iro.umontreal.ca wrote:
Hello,
I tested the use of 12 padding bits for 64bit boxed integers. Everything seemed to work fine, for the most part, except that a few unit tests failed with the exception:
we don't yet support multi-digit divisors
I'm guessing some of the values produced during constant propagation are outside of what is representable with a single big digit. Marc, would you have time to implement support for multiple big digit divisors?
No. But I can show you the 3 or 4 pages of Scheme code which implements the algorithm. If this is not a top priority then we can ask Olivier to work on that.
My guess is that you are trying to divide by 2^12... perhaps you could right shift by 12. Also, on machine with 64 bit words, the radix can be 2^30, and that might be big enough to make the divisions doable with a single digit divisor.
Marc
No. But I can show you the 3 or 4 pages of Scheme code which implements the algorithm. If this is not a top priority then we can ask Olivier to work on that.
Can't you scheme-to-js it all ;)
My guess is that you are trying to divide by 2^12... perhaps you could right shift by 12.
No, I'm actually doing division/modulo of unboxed integers during constant propagation. It's not really practical to do it on boxed integers directly with the current IR.
Also, on machine with 64 bit words, the radix can be 2^30, and that might be big enough to make the divisions doable with a single digit divisor.
One limiting factor is that JS only allows bitwise operations on 32 bit values. Was this one of the factors in your decision to limit the precision of big digits?
Also, if we have only 52 bits available in our boxed integers, can the radix really be 2^30?
- Maxime
On 2011-03-23, at 5:27 PM, chevalma@iro.umontreal.ca wrote:
No. But I can show you the 3 or 4 pages of Scheme code which implements the algorithm. If this is not a top priority then we can ask Olivier to work on that.
Can't you scheme-to-js it all ;)
I don't think so... trampolines and all that stuff.
My guess is that you are trying to divide by 2^12... perhaps you could right shift by 12.
No, I'm actually doing division/modulo of unboxed integers during constant propagation. It's not really practical to do it on boxed integers directly with the current IR.
OK.
Also, on machine with 64 bit words, the radix can be 2^30, and that might be big enough to make the divisions doable with a single digit divisor.
One limiting factor is that JS only allows bitwise operations on 32 bit values. Was this one of the factors in your decision to limit the precision of big digits?
That is not relevant if we are bootstrapping on Tachyon which has wider integers (if we want to).
Also, if we have only 52 bits available in our boxed integers, can the radix really be 2^30?
Ha! I hadn't thought of that! Indeed if fixnums are artificially limited to only have 52 significant bits as you are doing, then the radix must be <= 2^26.
Marc
That is not relevant if we are bootstrapping on Tachyon which has wider integers (if we want to).
I'd prefer to implement most of the compiler in standard JS, as much as possible. Otherwise, we might as well say the bignum code is pointless to begin with... We could have made wrappers for the int32 and int64 types directly.
Ha! I hadn't thought of that! Indeed if fixnums are artificially limited to only have 52 significant bits as you are doing, then the radix must be <= 2^26.
That would probably be sufficient for the case I'm dealing with, but for the sake of future-proofing, would it really be that difficult to port your existing bignum division implementation?
- Maxime
On 2011-03-23, at 9:32 PM, chevalma@iro.umontreal.ca wrote:
Ha! I hadn't thought of that! Indeed if fixnums are artificially limited to only have 52 significant bits as you are doing, then the radix must be <= 2^26.
That would probably be sufficient for the case I'm dealing with, but for the sake of future-proofing, would it really be that difficult to port your existing bignum division implementation?
Well, take a look. How long would it take to rewrite this algorithm in JavaScript and test it on all the corner cases? I just don't feel it is a top priority right now.
Can you explain where this is needed in the Tachyon compiler? Is it blocking us from progressing? Moreover, in JavaScript there is no integer division, so how can the bignum division help constant fold expressions like 101/4 or 2/3 ?
Marc
;;---------------------------------------------------------------------------
;; Bignum division
(define (bignum-div x y)
(define (single-digit-divisor-div x y lenx leny r)
;; simple algo for single digit divisor
(let ((d (bignum-digit-ref y 1))) (let loop1 ((i (- lenx 1)) (k 0)) (if (< 0 i) (let ((w (+ (* k (bignum-radix)) (bignum-digit-ref x i)))) (bignum-digit-set! r i (quotient w d)) (loop1 (- i 1) (remainder w d))) (cons (bignum-remove-leading-zeroes r) (fixnum->bignum (if (bignum-negative? x) (- 0 k) k)))))))
(define (multi-digit-divisor-div x y lenx leny r)
;; general algo from Knuth
;; STEP 1: normalize x and y
(let loop2 ((shift 1) (n (* (bignum-digit-ref y (- leny 1)) 2))) (if (< n (bignum-radix)) (loop2 (* shift 2) (* n 2))
(let ((nx (make-bignum (+ lenx 1))) (ny (make-bignum leny)))
(bignum-sign-set! nx (bignum-sign x))
(let loop3 ((i 1) (c 0)) (if (< i lenx) (let ((w (+ (* (bignum-digit-ref x i) shift) c))) (bignum-digit-set! nx i (modulo w (bignum-radix))) (loop3 (+ i 1) (quotient w (bignum-radix)))) (bignum-digit-set! nx i c)))
(let loop4 ((i 1) (c 0)) (if (< i leny) (let ((w (+ (* (bignum-digit-ref y i) shift) c))) (bignum-digit-set! ny i (modulo w (bignum-radix))) (loop4 (+ i 1) (quotient w (bignum-radix))))))
(let loop5 ((i lenx)) (if (not (< i leny))
;; STEP 2: calculate next digit in quotient
(let ((msd-of-ny (bignum-digit-ref ny (- leny 1))) (next-msd-of-ny (bignum-digit-ref ny (- leny 2))) (msd-of-nx (bignum-digit-ref nx i)) (next-msd-of-nx (bignum-digit-ref nx (- i 1))) (next-next-msd-of-nx (bignum-digit-ref nx (- i 2))))
(define (next-digit q u) (if (< u (bignum-radix)) (let* ((temp1 (* q next-msd-of-ny)) (temp2 (quotient temp1 (bignum-radix)))) (if (or (< u temp2) (and (= temp2 u) (< next-next-msd-of-nx (remainder temp1 (bignum-radix))))) (next-digit (- q 1) (+ u msd-of-ny)) q)) q))
(let ((q (if (= msd-of-nx msd-of-ny) (next-digit (bignum-radix-minus-1) (+ msd-of-ny next-msd-of-nx)) (let ((temp (+ (* msd-of-nx (bignum-radix)) next-msd-of-nx))) (next-digit (quotient temp msd-of-ny) (modulo temp msd-of-ny))))))
;; STEP 3: multiply and substract
(let loop7 ((j 1) (k (- i (- leny 1))) (b 0)) (if (< j leny)
(let ((w (- (+ (bignum-digit-ref nx k) b) (* (bignum-digit-ref ny j) q)))) (bignum-digit-set! nx k (modulo w (bignum-radix))) (loop7 (+ j 1) (+ k 1) (quotient (- w (bignum-radix-minus-1)) (bignum-radix))))
(let ((w (+ (bignum-digit-ref nx k) b))) (bignum-digit-set! nx k (modulo w (bignum-radix))) (if (< w 0) (begin (bignum-digit-set! r (- i (- leny 1)) (- q 1)) (let loop8 ((j 1) (k (- i (- leny 1))) (c 0)) (if (< j leny)
(let ((w (+ (+ (bignum-digit-ref nx k) (bignum-digit-ref ny j)) c))) (bignum-digit-set! nx k (modulo w (bignum-radix))) (loop8 (+ j 1) (+ k 1) (quotient w (bignum-radix)))) (bignum-digit-set! nx k (modulo (+ (bignum-digit-ref nx k) c) (bignum-radix)))))) (bignum-digit-set! r (- i (- leny 1)) q)) (loop5 (- i 1)))))))))
(let loop9 ((i (- leny 1)) (k 0)) (if (< 0 i) (let ((w (+ (* k (bignum-radix)) (bignum-digit-ref nx i)))) (bignum-digit-set! nx i (quotient w shift)) (loop9 (- i 1) (remainder w shift)))))
(cons (bignum-remove-leading-zeroes r) (bignum-remove-leading-zeroes nx))))))
(define (div x y lenx leny) (if (< lenx leny)
(cons bignum-zero x)
(let ((r (make-bignum (+ (- lenx leny) 2))))
(if (= (bignum-sign x) (bignum-sign y)) (bignum-set-nonneg! r) (bignum-set-neg! r))
(if (= leny 2) (single-digit-divisor-div x y lenx leny r) (multi-digit-divisor-div x y lenx leny r)))))
(if (bignum-zero? y) (snow-error "divide by zero") (div x y (bignum-length x) (bignum-length y))))
(define (bignum-quotient x y) (bignum-normalize (car (bignum-div x y))))
(define (bignum-remainder x y) (bignum-normalize (cdr (bignum-div x y))))
(define (bignum-modulo x y) (let ((r (cdr (bignum-div x y)))) (if (or (bignum-zero? r) (eqv? (bignum-negative? x) (bignum-negative? y))) (bignum-normalize r) (bignum+ r y))))
;;---------------------------------------------------------------------------
Well, take a look. How long would it take to rewrite this algorithm in JavaScript and test it on all the corner cases?
Rewrite it, perhaps one or two hours, assuming the code is very similar to the one you ported to JS. Testing it for a dozen cases, some number of minutes. There is no such thing as perfect testing.
Can you explain where this is needed in the Tachyon compiler? Is it blocking us from progressing? Moreover, in JavaScript there is no integer division, so how can the bignum division help constant fold expressions like 101/4 or 2/3 ?
Blocking us? No. It would just help us be closer to feature complete.
There is integer division in our IIR, and when an integer perfectly divides another.
Perhaps we can look at it together at some point and I can do the porting when I have time.
- Maxime
-
chevalma＠iro.umontreal.ca -
Marc Feeley