Programming Praxis

The current version of the big number library is shown on the next page. It includes a few functions we haven’t seen before: big?, which tests if an object is in the proper form to be considered a big number, big-sign which consolidates the tests for positive, negative and zero, big-quotient and big-remainder, for when you need one or the other but not both, and big-modulo. Also, the code has been refactored so that common subroutines appear only once, and (very) brief documentation is provided.

Our test consists of a long list of edge conditions followed by a thousand randomly-generated tests of arithmetic; the arithmetic tests use division, which tests all the other functions:

(define (test-big) ; no news is good news
  (let ((zero '(0)) (one '(1 1)) (minus-one '(-1 1))
        (base '(2 0 1)) (minus-base '(-2 0 1))
        (b1 (string->big "737")) (b2 (string->big "13290059"))
        (ten25 (string->big "10000000000000000000000000"))
        (ten24 (string->big "1000000000000000000000000")))
    (assert (string->big "0") zero)
    (assert (big->string (string->big "0")) "0")
    (assert (big->string (string->big "1")) "1")
    (assert (big->string (string->big "2")) "2")
    (assert (big->string (string->big "-1")) "-1")
    (assert (big->string (string->big "42")) "42")
    (assert (big->string (string->big "-42")) "-42")
    (assert (big->string (string->big "737")) "737")
    (assert (big->string (string->big "13290059")) "13290059")
    (assert (big-abs one) one)
    (assert (big-abs minus-one) one)
    (assert (big-negate one) minus-one)
    (assert (big-negate minus-one) one)
    (assert (big-negate base) minus-base)
    (assert (big->string (big-negate b1)) "-737")
    (assert (big->string (big-negate b2)) "-13290059")
    (assert (big-zero? zero) #t)
    (assert (big-zero? b2) #f)
    (assert (big-zero? minus-one) #f)
    (assert (big-positive? zero) #f)
    (assert (big-positive? b2) #t)
    (assert (big-positive? minus-one) #f)
    (assert (big-negative? zero) #f)
    (assert (big-negative? b2) #f)
    (assert (big-negative? minus-one) #t)
    (assert (big-even? zero) #t)
    (assert (big-odd? zero) #f)
    (assert (big-even? b2) #f)
    (assert (big-odd? b2) #t)
    (assert (big-even? minus-base) #t)
    (assert (big-odd? minus-base) #f)
    (assert (big-lt? b1 b2) #t)
    (assert (big-lt? b1 (big-negate b2)) #f)
    (assert (big-le? b1 b1) #t)
    (assert (big-le? b2 b1) #f)
    (assert (big-lt? zero one) #t)
    (assert (big-le? zero one) #t)
    (assert (big-lt? b1 b1) #f)
    (assert (big-eq? b1 b1) #t)
    (assert (big-eq? b1 b2) #f)
    (assert (big-ne? b1 b2) #t)
    (assert (big-ne? b1 b1) #f)
    (assert (big-gt? b1 b2) #f)
    (assert (big-gt? b1 (big-negate b2)) #t)
    (assert (big-ge? b1 b1) #t)
    (assert (big-ge? b2 b1) #t)
    (assert (big-gt? zero one) #f)
    (assert (big-ge? zero one) #f)
    (assert (big-gt? b1 b1) #f)
    (do ((i 0 (+ i 1))
         (n (next ten25) (next ten25))
         (d (next ten24) (next ten24)))
        ((= i 1000))
      (call-with-values
        (lambda () (big-divide n d))
        (lambda (q r)
          (if (big-negative? n)
              (begin (assert (big-le? r '(0)) #t)
                     (assert (big-lt? (big-negate (big-abs d)) r) #t))
              (begin (assert (big-ge? r '(0)) #t)
                     (assert (big-lt? r (big-abs d)) #t)))
          (assert (big-minus (big-times q d) (big-negate r)) n))))))

Random numbers are provided by a Park-Miller random number generator; it is built specifically for the test and should not be used otherwise:

(define next ; park-miller generator, suitable only for testing
  (let ((a (string->big "16807"))
        (m (string->big "2147483647"))
        (seed (string->big "1043618065")))
    (lambda (n)
      (let* ((minus-n (big-negate n))
             (span (big-plus (big-times n '(1 2)) '(1 1))))
        (set! seed (big-modulo (big-times a seed) m))
        (big-plus minus-n (big-quotient (big-times seed span) m))))))

To call the test, say (test-big); if it produces no output, all is well. The only bug that testing revealed was in the string->big function, which returned (1 0) instead of (0) when given the string "0"; once found, the bug was easy to fix. You can run the program at http://programmingpraxis.codepad.org/um9s9k8r.

Pages: 1 2 3