344 lines
10 KiB
Scheme
344 lines
10 KiB
Scheme
; Copyright (c) 1993-1999 by Richard Kelsey and Jonathan Rees. See file COPYING.
|
||
|
||
; This is file bignum.scm.
|
||
|
||
; Integer arithmetic
|
||
|
||
(define-extended-number-type :bignum (:exact-integer)
|
||
(make-bignum sign magnitude)
|
||
bignum?
|
||
(sign bignum-sign)
|
||
(magnitude bignum-magnitude))
|
||
|
||
(define (integer->bignum m)
|
||
(if (bignum? m)
|
||
m
|
||
(cond ((>= m 0)
|
||
(make-bignum 1 (integer->magnitude m)))
|
||
((= m least-non-bignum)
|
||
(make-bignum -1 least-non-bignum-magnitude))
|
||
(else
|
||
(make-bignum -1 (integer->magnitude (- 0 m)))))))
|
||
|
||
;(define (bignum->integer n) ;For debugging
|
||
; (* (bignum-sign n)
|
||
; (reduce (lambda (d n) (+ d (* n radix)))
|
||
; 0
|
||
; (bignum-magnitude n))))
|
||
|
||
(define (make-integer sign mag)
|
||
(if (> sign 0)
|
||
(if (smaller-magnitude? greatest-non-bignum-magnitude mag)
|
||
(make-bignum sign mag)
|
||
(magnitude->integer mag))
|
||
(if (smaller-magnitude? least-non-bignum-magnitude mag)
|
||
(make-bignum sign mag)
|
||
(if (same-magnitude? mag least-non-bignum-magnitude)
|
||
least-non-bignum
|
||
(- 0 (magnitude->integer mag))))))
|
||
|
||
; Arithmetic
|
||
|
||
(define (integer+ m n)
|
||
(let ((m (integer->bignum m))
|
||
(n (integer->bignum n)))
|
||
(let ((m-sign (bignum-sign m))
|
||
(m-mag (bignum-magnitude m))
|
||
(n-sign (bignum-sign n))
|
||
(n-mag (bignum-magnitude n)))
|
||
(if (= m-sign n-sign)
|
||
(make-integer m-sign (add-magnitudes m-mag n-mag))
|
||
(if (smaller-magnitude? m-mag n-mag)
|
||
(make-integer (- 0 m-sign) (subtract-magnitudes n-mag m-mag))
|
||
(make-integer m-sign (subtract-magnitudes m-mag n-mag)))))))
|
||
|
||
(define (integer- m n)
|
||
(integer+ m (integer-negate n)))
|
||
|
||
(define (integer-negate m)
|
||
(cond ((bignum? m)
|
||
(make-integer (- 0 (bignum-sign m))
|
||
(bignum-magnitude m)))
|
||
((= m least-non-bignum)
|
||
(make-bignum 1 least-non-bignum-magnitude))
|
||
(else (- 0 m))))
|
||
|
||
(define (integer* m n)
|
||
(let ((m (integer->bignum m))
|
||
(n (integer->bignum n)))
|
||
(make-integer (* (bignum-sign m) (bignum-sign n))
|
||
(multiply-magnitudes
|
||
(bignum-magnitude m)
|
||
(bignum-magnitude n)))))
|
||
|
||
(define (integer-divide m n cont)
|
||
(let ((m (integer->bignum m))
|
||
(n (integer->bignum n)))
|
||
(divide-magnitudes
|
||
(bignum-magnitude m)
|
||
(bignum-magnitude n)
|
||
(lambda (q r)
|
||
(cont (make-integer (* (bignum-sign m) (bignum-sign n)) q)
|
||
(make-integer (bignum-sign m) r))))))
|
||
|
||
(define (integer-quotient m n)
|
||
(integer-divide m n (lambda (q r) q)))
|
||
|
||
(define (integer-remainder m n)
|
||
(integer-divide m n (lambda (q r) r)))
|
||
|
||
(define integer=
|
||
(lambda (m n)
|
||
(let ((m (integer->bignum m))
|
||
(n (integer->bignum n)))
|
||
(and (= (bignum-sign m) (bignum-sign n))
|
||
(same-magnitude? (bignum-magnitude m)
|
||
(bignum-magnitude n))))))
|
||
|
||
(define integer<
|
||
(lambda (m n)
|
||
(let ((m (integer->bignum m))
|
||
(n (integer->bignum n)))
|
||
(let ((m-sign (bignum-sign m))
|
||
(n-sign (bignum-sign n)))
|
||
(or (< m-sign n-sign)
|
||
(and (= m-sign n-sign)
|
||
(if (< m-sign 0)
|
||
(smaller-magnitude? (bignum-magnitude n)
|
||
(bignum-magnitude m))
|
||
(smaller-magnitude? (bignum-magnitude m)
|
||
(bignum-magnitude n)))))))))
|
||
|
||
|
||
; Magnitude (unsigned integer) arithmetic
|
||
|
||
(define log-radix 14) ;Cutting it close here...
|
||
(define radix (expt 2 log-radix))
|
||
|
||
(define greatest-non-bignum (+ (expt 2 28) (- (expt 2 28) 1)))
|
||
(define least-non-bignum (* (expt 2 28) -2))
|
||
|
||
(define zero-magnitude '())
|
||
(define zero-magnitude? null?)
|
||
|
||
(define (low-digit m)
|
||
(if (zero-magnitude? m)
|
||
0
|
||
(car m)))
|
||
|
||
(define (high-digits m)
|
||
(if (zero-magnitude? m)
|
||
m
|
||
(cdr m)))
|
||
|
||
(define (adjoin-digit d m)
|
||
(if (and (= d 0) (zero-magnitude? m))
|
||
m
|
||
(cons d m)))
|
||
|
||
(define (integer->magnitude n)
|
||
(if (= n 0)
|
||
zero-magnitude
|
||
(let ((digit (remainder n radix)))
|
||
(adjoin-digit digit
|
||
(integer->magnitude (quotient n radix))))))
|
||
|
||
(define (magnitude->integer m)
|
||
(if (zero-magnitude? m)
|
||
0
|
||
(+ (low-digit m)
|
||
(* radix (magnitude->integer (high-digits m))))))
|
||
|
||
(define greatest-non-bignum-magnitude
|
||
(integer->magnitude greatest-non-bignum))
|
||
|
||
(define least-non-bignum-magnitude
|
||
(adjoin-digit (- 0 (remainder least-non-bignum radix))
|
||
(integer->magnitude
|
||
(- 0 (quotient least-non-bignum radix)))))
|
||
|
||
; Combine two numbers digitwise using op.
|
||
|
||
(define (combine-magnitudes m n op)
|
||
(let recur ((m m) (n n) (carry 0))
|
||
(if (and (zero-magnitude? m) (zero-magnitude? n))
|
||
(integer->magnitude carry)
|
||
(let ((result (+ carry (op (low-digit m) (low-digit n)))))
|
||
(let ((q (quotient result radix))
|
||
(r (remainder result radix)))
|
||
(if (< r 0)
|
||
(adjoin-digit (+ r radix)
|
||
(recur (high-digits m)
|
||
(high-digits n)
|
||
(- q 1)))
|
||
(adjoin-digit r
|
||
(recur (high-digits m)
|
||
(high-digits n)
|
||
q))))))))
|
||
|
||
(define (add-magnitudes m n)
|
||
(combine-magnitudes m n +))
|
||
|
||
(define (subtract-magnitudes m n)
|
||
(combine-magnitudes m n -))
|
||
|
||
; Compare
|
||
|
||
(define same-magnitude? equal?)
|
||
|
||
(define (smaller-magnitude? m n)
|
||
(let ((m-len (length m))
|
||
(n-len (length n)))
|
||
(cond ((< m-len n-len)
|
||
#t)
|
||
((< n-len m-len)
|
||
#f)
|
||
(else
|
||
(let loop ((m m) (n n) (a #f))
|
||
(cond ((zero-magnitude? m)
|
||
(or (not (zero-magnitude? n)) a))
|
||
((zero-magnitude? n) #f)
|
||
(else
|
||
(loop (high-digits m)
|
||
(high-digits n)
|
||
(or (< (low-digit m) (low-digit n))
|
||
(and (= (low-digit m) (low-digit n)) a))))))))))
|
||
|
||
; Multiply
|
||
|
||
(define (multiply-magnitudes m n)
|
||
(let recur ((m m) (a zero-magnitude))
|
||
(if (zero-magnitude? m)
|
||
a
|
||
(let ((a (combine-magnitudes a n (lambda (d e)
|
||
(+ d (* e (low-digit m)))))))
|
||
(adjoin-digit (low-digit a)
|
||
(recur (high-digits m) (high-digits a)))))))
|
||
|
||
; Divide m/n: find q and r such that m = q*n + r, where 0 <= r < n.
|
||
; Oh no... time to get out Knuth...
|
||
; The main thing we don't do that Knuth does is to normalize the
|
||
; divisor (n) by shifting it left.
|
||
|
||
(define (divide-magnitudes m n cont)
|
||
(if (zero-magnitude? (high-digits n))
|
||
(divide-by-digit m (low-digit n)
|
||
(lambda (q r)
|
||
(cont q (adjoin-digit r zero-magnitude))))
|
||
(let recur ((m m) (cont cont))
|
||
(if (smaller-magnitude? m n)
|
||
(cont zero-magnitude m)
|
||
(recur
|
||
(high-digits m)
|
||
(lambda (q r)
|
||
;; 0 <= r < n and d < b
|
||
;; so b*r + d < b*n.
|
||
(divide-step (adjoin-digit (low-digit m) r)
|
||
n
|
||
(lambda (q1 r)
|
||
(cont (adjoin-digit q1 q) r)))))))))
|
||
|
||
; Divide m by n, where n <= m < b*n, i.e. 1 <= quotient < b.
|
||
; E.g. if n = 100 then 100 <= m <= 999
|
||
; if n = 999 then 999 <= m <= 9989
|
||
|
||
(define (divide-step m n cont)
|
||
(do ((m-high m (high-digits m-high))
|
||
(n-high n (high-digits n-high)))
|
||
((zero-magnitude? (high-digits (high-digits n-high)))
|
||
;; Occasionally q^ is one larger than the actual first digit.
|
||
;; This loop will never iterate more than once.
|
||
(let loop ((q^ (min (guess-quotient-digit m-high n-high)
|
||
(- radix 1))))
|
||
(let ((r (combine-magnitudes m n (lambda (d e)
|
||
(- d (* e q^))))))
|
||
(if (improper-magnitude? r)
|
||
;; (begin (write `(addback ,m ,n ,q^ ,r)) (newline) ...)
|
||
(loop (- q^ 1))
|
||
(cont q^ r)))))))
|
||
|
||
; Compute q such that [m1 m2 m3] = q*[n1 n2] + r with 0 <= r < [n1 n2]
|
||
; Can assume b <= [0 n1 n2] <= [m1 m2 m3] <= [n1 n2 b-1]
|
||
; Some examples:
|
||
; m / n : 100[1] / 10[02], 099 / 10, 099[1] / 99[0], 999[8] / 99[99]
|
||
; Various hacks are possible to improve performance. In particular, the
|
||
; second division can be eliminated if the divisor is normalized.
|
||
; See Knuth.
|
||
; [m1 m2] = q0*[n1] + r0
|
||
; [m1 m2 m3] = q0*[n1 n2] + r^
|
||
; r^ = b*r0 + m3 - q0*n2
|
||
|
||
(define (guess-quotient-digit m n)
|
||
(let ((n1 (low-digit (high-digits n)))
|
||
(n2 (low-digit n))
|
||
(m1 (low-digit (high-digits (high-digits m))))
|
||
(m2 (low-digit (high-digits m)))
|
||
(m3 (low-digit m)))
|
||
(let ((m12 (+ (* m1 radix) m2)))
|
||
(let ((q0 (quotient m12 n1))
|
||
(r0 (remainder m12 n1)))
|
||
(let ((r^ (- (+ (* radix r0) m3) (* q0 n2)))
|
||
(n12 (+ (* n1 radix) n2)))
|
||
(let ((q1 (quotient r^ n12))
|
||
(r1 (remainder r^ n12)))
|
||
(if (> q1 0)
|
||
(begin (display "This should never happen: q1 = ")
|
||
(write q1) (newline)))
|
||
(let ((q (+ q0 q1)))
|
||
(if (< r1 0) (- q 1) q))))))))
|
||
|
||
(define (improper-magnitude? m)
|
||
(and (not (zero-magnitude? m))
|
||
(or (< (low-digit m) 0)
|
||
(improper-magnitude? (high-digits m)))))
|
||
|
||
; Special case of division algorithm for single-digit divisor.
|
||
|
||
(define (divide-by-digit m d cont)
|
||
(if (= d 0)
|
||
(error "integer division by zero" m d)
|
||
(let recur ((m m) (cont cont))
|
||
(if (and (zero-magnitude? (high-digits m))
|
||
(< (low-digit m) d))
|
||
(cont zero-magnitude (low-digit m))
|
||
(recur (high-digits m)
|
||
(lambda (q r)
|
||
(let ((m1 (+ (low-digit m) (* radix r))))
|
||
(cont (adjoin-digit (quotient m1 d) q)
|
||
(remainder m1 d)))))))))
|
||
|
||
;(define (divide-test seed)
|
||
; (let ((random (make-random seed)))
|
||
; (let loop ()
|
||
; (let* ((z1 (integer+ (random) (integer* (random) 10000000)))
|
||
; (z2 (integer+ (random) (integer* (random) 10000000)))
|
||
; (n (max z1 z2))
|
||
; (r (min z1 z2))
|
||
; (q (random))
|
||
; (m (integer+ (integer* n q) r)))
|
||
; (if (not (= n r))
|
||
; (integer-divide m n
|
||
; (lambda (q1 r1)
|
||
; (if (and (= q q1) (= r r1))
|
||
; (begin (display ".")
|
||
; (force-output (current-output-port)))
|
||
; (error "division error" m n q q1 r r1)))))
|
||
; (loop)))))
|
||
|
||
|
||
; Extend the generic arithmetic operators.
|
||
|
||
(define-method &integer? ((n :bignum)) #t)
|
||
(define-method &exact? ((n :bignum)) #t)
|
||
|
||
(define-method &+ ((n1 :exact-integer) (n2 :exact-integer)) (integer+ n1 n2))
|
||
(define-method &- ((n1 :exact-integer) (n2 :exact-integer)) (integer- n1 n2))
|
||
(define-method &* ((n1 :exact-integer) (n2 :exact-integer)) (integer* n1 n2))
|
||
(define-method &= ((n1 :exact-integer) (n2 :exact-integer)) (integer= n1 n2))
|
||
(define-method &< ((n1 :exact-integer) (n2 :exact-integer)) (integer< n1 n2))
|
||
|
||
(define-method "ient ((n1 :exact-integer) (n2 :exact-integer))
|
||
(integer-quotient n1 n2))
|
||
(define-method &remainder ((n1 :exact-integer) (n2 :exact-integer))
|
||
(integer-remainder n1 n2))
|