Simple Scheme で電卓をつくってみる(10) ―割り算させてみる―

加減乗除のうちまだないのは除算―割り算だけですね。割り算を組み込みましょう。

電卓の内部で数はリストで表現されていますが、リスト÷リストだと大変なのでリスト÷整数型にします。
まず具体的に割り算してみましょう。

(define (i/% x y)
  (let ((q (/ x y)) (r (% x y))) (if (< r 0) (list (-- q) (+ r y)) (list q r))))

"3330088÷106"
(foldl (lambda (x ds) (append (reverse (i/% (+ x (* 10 (car ds))) 106)) (cdr ds)))
       '(0) '(3 3 3 0 0 8 8))

f:id:brv00:20191120202348j:plain:w250

あらかじめ整数型に変換した除数で、リストで表された被除数を1要素ずつ割り、余りを（10倍して）次の要素に足しつつ、商を並べていく方法―つまり小学校で習う筆算と同じ方法で割り算しています。
foldlの各段階で、xsの処理済み部分の①余りがdsのcarに入り、②商がひと桁ずつcdrに並びます。また、③xsは先頭から処理されdsは末尾から生成されるので、下位桁ほど手前に来ます。
以上の3点を踏まえてこの実行結果をみると、3330088を106で割ったら余りが98、商が0031415になるということがわかります。

これを核として割り算関数を定義しましょう。
先に商の整数部分を求めれば桁数が調整しやすくなります。
このとき、整数部分と小数部分のそれぞれを求めるため上記の処理は2回実行しなければなりません。字数が多いので関数にしてしまいましょう。

(define (ldiv xs y carry-digit)
  (foldl (lambda (x ds) (append (reverse (i/% (+ x (* 10 (car ds))) y)) (cdr ds)))
         (list carry-digit) xs))

まず整数部分を計算します。除数をnum->intで整数にすると、小数点が小数部分の長さ分だけ右に移動することになるので、被除数もそれに合わせて小数点を移動させます。この操作によって被除数の整数部分は(append (num-i x) (trim (num-f x) lfy))となります（trimの定義）。lfyは除数の小数部分の長さです。
このリストをldivを用いて除数で割れば商の整数部分（と余り）が得られます。
割り算関数を整数部分を求めるところまで書いてみます。

(define (div x y)
  (let ((sign (mul-signs-of x y)) (lfy (length (num-f y))) (y (num->int y)))
    (let* ((ix (append (num-i x) (trim (num-f x) lfy)))
           (rq (ldiv ix y 0)) (i (drop0s (reverse (cdr rq))))
       (i (if (null? i) '(0) i)))
      i)))

; テスト
"3330088÷106"
(div (make-num plus '(3 3 3 0 0 8 8) '()) (make-num plus '(1 0 6) '()))
"99999999÷0.5"
(div (make-num plus '(9 9 9 9 9 9 9 9) '()) (make-num plus '(0) '(5)))

f:id:brv00:20191121224102j:plain:w250

整数部分の桁数がmax-ndigitsより大きいときはエラーであり*1、小数部分はエラー処理に必要ないので計算せずに空リストを返します。

      (if (> (length i) max-ndigits)
          (make-num sign i '())
          ...

そうでないときの小数部分の計算のやり方を考えましょう。
小数点の移動によって被除数の小数部分は、(drop (num-f x) lfy)となります。
また、ldivによって得られる商の長さ*2は第1引数と同じなので、被除数の小数部分を、商の小数部分と同じ長さにtrimすればよいことになります。商の小数部分の長さはmax-ndigitsから商の整数部分の長さを引いた値なので、(trim (drop (num-f x)) (- max-ndigits (length i)))でよさそうです*3。しかしxの小数部分がlfyより短い場合、この式はBad popになり、電卓が止まります。なので、被除数の小数部分を表すリストは次のように求めることにしました*4。

(drop (trim (num-f x) (- (+ max-ndigits lfy) (length i))) lfy)

そして割り算部分の全体は次のようになります。

(define (ldiv xs y carry-digit)
  (foldl (lambda (x ds) (append (reverse (i/% (+ x (* 10 (car ds))) y)) (cdr ds)))
         (list carry-digit) xs))

(define (div x y)
  (let ((sign (mul-signs-of x y)) (lfy (length (num-f y))) (y (num->int y)))
    (let* ((ix (append (num-i x) (trim (num-f x) lfy))) (rq (ldiv ix y 0))
           (i (drop0s (reverse (cdr rq)))) (i (if (null? i) '(0) i)))
      (if (> (length i) max-ndigits)
          (make-num sign i '())
          (let ((fx (drop (trim (num-f x) (- (+ max-ndigits lfy) (length i))) lfy)))
            (make-num sign i (reverse (drop0s (cdr (ldiv fx y (car rq)))))))))))

; テスト
"3330088÷106"
(div (make-num plus '(3 3 3 0 0 8 8) '()) (make-num plus '(1 0 6) '()))
"99999999÷0.5"
"1÷11"
(div (make-num plus '(1) '()) (make-num plus '(1 1) '()))
(div (make-num plus '(9 9 9 9 9 9 9 9) '()) (make-num plus '(0) '(5)))