*Bradley Lucier*04 Dec 2022 16:48 UTC

On 12/4/22 10:51 AM, Taylor R Campbell wrote: >> Date: Sat, 3 Dec 2022 12:26:26 -0500 >> From: Bradley Lucier <xxxxxx@math.purdue.edu> >> References: <xxxxxx@jupiter.mumble.net> >> >> On 11/28/22 9:59 PM, Taylor R Campbell wrote: >>> Attached is a collection of known-answer test that you could try -- I >>> generated it just now with MIT Scheme. It tests the cartesian product >>> of: >>> >>> - the five operators {floor/, ceiling/, truncate/, euclidean/, round/} >>> - the nine numerators {0, 1, 2, 3, 4, 5, 6, 7, 8} >>> - both signs for numerators >>> - the eight denominators {1, 2, 3, 4, 5, 6, 7, 8} >>> - both signs for denominators >>> >>> These 1440 test cases cover zero, units, primes, a square, a composite >>> of distinct primes, and a cube. (They don't, however, cover anything >>> that requires bignum arithmetic.) I haven't vetted these answers in >>> any way other than verifying the tests pass in MIT Scheme -- I >>> recommend running them through the property tests, and eyeballing them >>> to spot-check for reasonableness. >> >> Just for curiosity's sake, I searched for arguments that would >> distinguish between every pair of the six (including balanced/) division >> procedures (i.e., for every pair of different division procedures, those >> two division procedures differ on at least one of these arguments). The >> list is surprisingly short and simple, at least to me: >> >> ((-1 2) (2 3) (1 -2) (1 4) (1 2)) > > Neat. Although The fact that none of these numerators is composite or > even greater than the denominator suggests maybe one should search a > larger space for such examples! This is the code I used to test my implementation. The implementation has a fixnum-specific code path, so I needed to test arguments around the fixnum limits. The round/ procedures gave me a bit of a puzzle about how to characterize the solutions. ;; exact tests (let* ((big-arguments (map (lambda (inc) (+ ##bignum.-min-fixnum inc)) (iota 5 -2))) (really-big-arguments (apply append (map (lambda (x) (map (lambda (y) (* x y)) big-arguments)) big-arguments))) (positive-arguments (append big-arguments really-big-arguments (iota 8 1))) (nonzero-arguments (append positive-arguments (map - positive-arguments))) (all-arguments (cons 0 nonzero-arguments))) (for-each (lambda (n) (for-each (lambda (d) (call-with-values (lambda () (balanced/ n d)) (lambda (quo rem) (check-true (and (= n (+ (* d quo) rem)) (<= (- (/ (abs d) 2) rem)) (< rem (/ (abs d) 2)))) (check-eqv? (balanced-quotient n d) quo) (check-eqv? (balanced-remainder n d) rem)))) nonzero-arguments)) all-arguments) (for-each (lambda (n) (for-each (lambda (d) (call-with-values (lambda () (round/ n d)) (lambda (quo rem) (check-true (and (= n (+ (* d quo) rem)) (or (< (* 2 (abs rem)) (abs d)) (and (= (abs d) (* 2 (abs rem))) (even? quo))))) (check-eqv? (round-quotient n d) quo) (check-eqv? (round-remainder n d) rem)))) nonzero-arguments)) all-arguments) (for-each (lambda (n) (for-each (lambda (d) (call-with-values (lambda () (floor/ n d)) (lambda (quo rem) (check-true (and (= n (+ (* d quo) rem)) (< (abs rem) (abs d)) (or (= rem 0) (and (eq? (negative? d) (negative? rem)))))) (check-eqv? (floor-quotient n d) quo) (check-eqv? (floor-remainder n d) rem)))) nonzero-arguments)) all-arguments) (for-each (lambda (n) (for-each (lambda (d) (call-with-values (lambda () (ceiling/ n d)) (lambda (quo rem) (check-true (and (= n (+ (* d quo) rem)) (< (abs rem) (abs d)) (or (= rem 0) (and (eq? (negative? d) (positive? rem)))))) (check-eqv? (ceiling-quotient n d) quo) (check-eqv? (ceiling-remainder n d) rem)))) nonzero-arguments)) all-arguments) (for-each (lambda (n) (for-each (lambda (d) (call-with-values (lambda () (truncate/ n d)) (lambda (quo rem) (check-true (and (= n (+ (* d quo) rem)) (< (abs rem) (abs d)) (or (= rem 0) (and (eq? (negative? n) (negative? rem)))))) (check-eqv? (truncate-quotient n d) quo) (check-eqv? (truncate-remainder n d) rem)))) nonzero-arguments)) all-arguments) (for-each (lambda (n) (for-each (lambda (d) (call-with-values (lambda () (euclidean/ n d)) (lambda (quo rem) (check-true (and (= n (+ (* d quo) rem)) (< -1 rem (abs d)))) (check-eqv? (euclidean-quotient n d) quo) (check-eqv? (euclidean-remainder n d) rem)))) nonzero-arguments)) all-arguments) (for-each (lambda (n) (for-each (lambda (d) (check-eqv? (quotient n d) (truncate-quotient n d)) (check-eqv? (remainder n d) (truncate-remainder n d)) (check-eqv? (modulo n d) (floor-remainder n d))) nonzero-arguments)) all-arguments)) ;; inexact-tests (let* ((positive-arguments (iota 8 1)) (nonzero-arguments (append positive-arguments (map - positive-arguments))) (all-arguments (cons 0 nonzero-arguments)) (operations (list truncate/ floor/ ceiling/ round/ euclidean/ balanced/))) (for-each (lambda (operation) (for-each (lambda (n) (for-each (lambda (d) (call-with-values (lambda () (operation n d)) (lambda (exact-quo exact-rem) (call-with-values (lambda () (operation (inexact n) (inexact d))) (lambda (inexact-quo inexact-rem) (check-= exact-quo inexact-quo 0) (check-= exact-rem inexact-rem 0)))))) nonzero-arguments)) all-arguments)) operations))