Email list hosting service & mailing list manager


Re: Fwd: Proposed document change 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))