ndivide

Conformance: SketchyLISP Core

Purpose: Divide two natural numbers, giving a quotient and a remainder.

Arguments:
A - natural number (dividend)
B - natural number (divisor)

Implementation:

(define (ndivide a b)
  (letrec
    ; Equalize the divisor by shifting it to the left
    ; (multiplying it by 10) until it has the same number
    ; of digits as the dividend.
    ; A - list of digits (dividend)
    ; B - reverse list of digits (divisor)
    ; R - result of the form (new divisor . one I per shift)
    ((eql
       (lambda (a b r)
         (cond
           ; end of dividend?
           ((null? a)
             ; reverse the divisor
             (cons (reverse (car r)) (cdr r)))
           ; end of divisor?
           ((null? b)
             (eql (cdr a) '()           ; go to next digit
               (cons (cons 0d (car r))  ; prepend 0 to divisor
                     (cons 'i (cdr r)))))  ; count shift
           ; default: copy a digit
           (else (eql (cdr a) (cdr b)
                   (cons (cons (car b) (car r))
                         (cdr r)))))))
     ; Divide two lists of digits which have a quotient
     ; less than 10.
     ; A - dividend
     ; B - divisor
     ; R - result of the form (A/B*B . A/B)
     (div10
       (lambda (a b r)
         (cond ((n< (car r) a)
             (div10 a b
               (cons (n+ (car r) (list->integer b #t))
                     (n+ (cdr r) 1))))
           ((= (car r) a) r)
           (else (cons (n- (car r) (list->integer b #t))
                       (n- (cdr r) 1))))))
     ; X / 10
     (d10
       (lambda (x)
         (reverse (cdr (reverse x)))))
     ; X * 10
     (x10
       (lambda (x)
         (list->integer
           (append (integer->list x) '(0d)))))
     ; Divide two lists of digits
     ; A - list of digits (dividend)
     ; B - divisor of the form (EQL A B ...)
     ; R - result (list of digits in normal order)
     (div
       (lambda (a b r)
         (cond ((null? (cdr b))
             (list (normalize r) a))
           (else (let ((quot (div10 a (car b) (cons 0 0))))
                   (div (n- a (car quot))
                        (cons (d10 (car b)) (cddr b))
                        (n+ (x10 r) (cdr quot)))))))))
    (cond ((zero? b)
        (bottom 'divide-by-zero))
      ((n< a b) (list 0 a))
      (else (div a (eql (integer->list a)
                        (integer->list b) '(() i))
                   0)))))

Example:

(ndivide 11 3) 
=> (3 2)

See also:
digits, divide, divide, nquotient, nremainder, n*.