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))
