[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/gAbRGnwD    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on May 30:
; big numbers: addition, subtraction and multiplication

(define big-base 1000)

(define (integer->big int)
  (if (zero? int) (list 0)
    (if (negative? int)
        (let ((x (integer->big (- int))))
          (cons (- (car x)) (cdr x)))
        (let loop ((int int) (big '()))
          (if (< int big-base)
              (cons (+ (length big) 1)
                    (reverse (cons int big)))
              (loop (quotient int big-base)
                    (cons (modulo int big-base) big)))))))

(define (big->integer big)
  (if (zero? (car big)) 0
    (if (negative? (car big))
        (- (big->integer (cons (- (car big)) (cdr big))))
        (let loop ((bs (reverse (cdr big))) (n 0))
          (if (null? bs) n
            (loop (cdr bs) (+ (car bs) (* n big-base))))))))

(define (big-abs big)
  (if (positive? (car big)) big (cons (- (car big)) (cdr big))))
(define (big-negate big) (cons (* (car big) -1) (cdr big)))

(define (big-positive? big) (positive? (car big)))
(define (big-negative? big) (negative? (car big)))
(define (big-zero? big) (zero? (car big)))

(define (big-even? big)
  (or (big-zero? big) (even? (cadr big))))
(define (big-odd? big)
  (not (or (big-zero? big) (even? (cadr big)))))

(define (big-compare big1 big2)
  ; big1 < big2 => -1 ; big1 = big2 => 0 ; big1 > big2 => 1
  (cond ((< (car big1) (car big2)) -1)
        ((< (car big2) (car big1)) 1)
        (else (let loop ((b1 (reverse (cdr big1)))
                         (b2 (reverse (cdr big2))))
                (cond ((null? b1) 0)
                      ((< (car b1) (car b2)) -1)
                      ((< (car b2) (car b1)) 1)
                      (else (loop (cdr b1) (cdr b2))))))))

(define (big-eq? big1 big2)
  (zero? (big-compare big1 big2)))
(define (big-ne? big1 big2)
  (not (zero? (big-compare big1 big2))))
(define (big-lt? big1 big2)
  (negative? (big-compare big1 big2)))
(define (big-gt? big1 big2)
  (positive? (big-compare big1 big2)))
(define (big-le? big1 big2)
  (not (positive? (big-compare big1 big2))))
(define (big-ge? big1 big2)
  (not (negative? (big-compare big1 big2))))

(define (big-plus big1 big2)
  (define (reduce xs)
    (if (null? (cdr xs)) xs
      (if (positive? (car xs)) xs
        (reduce (cdr xs)))))
  (define (add b1 b2)
    (let loop ((b1 b1) (b2 b2) (c 0) (bs '()))
      (cond ((null? b1)
              (if (zero? c) (reverse bs) (reverse (cons 1 bs))))
            ((null? b2)
              (let* ((sum (+ (car b1) c))
                     (new-c (if (<= big-base sum) 1 0)))
                (loop (cdr b1) b2 new-c
                      (cons (modulo sum big-base) bs))))
            (else (let* ((sum (+ (car b1) (car b2) c))
                         (new-c (if (<= big-base sum) 1 0)))
                    (loop (cdr b1) (cdr b2) new-c
                          (cons (modulo sum big-base) bs)))))))
  (define (sub b1 b2)
    (let loop ((b1 b1) (b2 b2) (c 0) (bs '()))
      (cond ((null? b1) (reverse (reduce bs)))
            ((null? b2)
              (let* ((diff (- (car b1) c))
                     (new-c (if (< diff 0) 1 0)))
                (loop (cdr b1) b2 new-c
                      (cons (modulo diff big-base) bs))))
            (else (let* ((diff (- (car b1) (car b2) c))
                         (new-c (if (< diff 0) 1 0)))
                    (loop (cdr b1) (cdr b2) new-c
                          (cons (modulo diff big-base) bs)))))))
  (if (zero? (car big1)) big2
    (if (zero? (car big2)) big1
      (let* ((b1 (cdr big1)) (b2 (cdr big2))
             (lt? (big-lt? (big-abs big1) (big-abs big2)))
             (s1 (if (positive? (car big1)) 1 -1))
             (s2 (if (positive? (car big2)) 1 -1))
             (x (apply (if (= s1 s2) add sub)
                       (if lt? (list b2 b1) (list b1 b2))))
             (len (length x)))
        (if (equal? x (list 0)) x
          (cons (* len (if (or (and lt? (= s2 1))
                           (and (not lt?) (= s1 1)))
                         1 -1))
                x))))))

(define (big-minus big1 big2)
  (big-plus big1 (big-negate big2)))

(define (big-times big1 big2)
  (define (add b1 b2)
    (let loop ((b1 b1) (b2 b2) (c 0) (bs '()))
      (cond ((null? b1)
              (if (zero? c) (reverse bs) (reverse (cons 1 bs))))
            ((null? b2)
              (let* ((sum (+ (car b1) c))
                     (new-c (if (<= big-base sum) 1 0)))
                (loop (cdr b1) b2 new-c
                      (cons (modulo sum big-base) bs))))
            (else (let* ((sum (+ (car b1) (car b2) c))
                         (new-c (if (<= big-base sum) 1 0)))
                    (loop (cdr b1) (cdr b2) new-c
                          (cons (modulo sum big-base) bs)))))))
  (define (sign x) (if (negative? x) -1 (if (positive? x) 1 0)))
  (define (times big1 big2)
    (let loop ((b1 big1) (b2 big2) (zs '())
               (c 0) (ps '()) (bs '()))
      (cond ((null? b1) bs)
            ((null? b2) (let ((zs (cons 0 zs)))
              (loop (cdr b1) big2 zs 0 zs
                (add (reverse (if (zero? c) ps (cons c ps))) bs))))
            (else (let* ((x (+ (* (car b1) (car b2)) c))
                         (c (quotient x big-base))
                         (p (modulo x big-base)))
                    (loop b1 (cdr b2) zs c (cons p ps) bs))))))
  (if (or (big-zero? big1) (big-zero? big2)) (list 0)
    (let* ((b1 (cdr big1)) (b2 (cdr big2))
           (x (times b1 b2)) (len (length x)))
      (cons (* len (sign (* (car big1) (car big2)))) x))))

(display
  (big->integer
    (big-plus (integer->big 12345678)
              (integer->big 987654321))))
(newline)

(display
  (big->integer
    (big-minus (integer->big 12345678)
              (integer->big 987654321))))
(newline)

(display
  (big->integer
    (big-times (integer->big 12345678)
              (integer->big 987654321))))
(newline)


Output:
1
2
3
999999999
-975308643
12193262222374638


Create a new paste based on this one


Comments: