t3x.org / sketchy / library / ndivide.html
SketchyLISP
Reference
  Copyright (C) 2006
Nils M Holm

ndivide

Conformance: SketchyLISP Core

Purpose: Divide two natural numbers, giving a result of the form
(quotient 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
        (#t (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)
        (#t (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))
        (#t (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))
      (#t (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*.