SketchyLISP Reference |
Copyright (C) 2006 Nils M Holm |
<<[natural?] | [Index] | [negate]>> |
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*.
<<[natural?] | [Index] | [negate]>> |