Simple Scheme で電卓をつくってみる(5.3)

多倍長計算で加減算を行う関数を定義しましょう。

桁ごとに足してから繰り上がり、という順序で処理します。

桁ごとに足すためにmap2を定義します*1。

(define (map2 f l1 l2)
  (build-list (length l1) (lambda (i) (f (list-ref l1 i) (list-ref l2 i)))))

"945+257"
(map2 + '(9 4 5) '(2 5 7))
"945-257"
(map2 - '(9 4 5) '(2 5 7))

f:id:brv00:20191107081005j:plain

この結果に対して繰り上がり処理をするわけです。

末尾の要素を10で割って商を1つ上位の桁に足し、新たな末尾とします。これを繰り返しながら10で割ったときに出る余りを右から順に並べると足し算の結果を10進法で表したリストが得られます。リストの末尾からの処理は、Simple Schemeの場合は、foldrが便利です。

(foldr (lambda (x ds) (cons (/ (+ x (car ds)) 10) (cons (% (+ x (car ds)) 10) (cdr ds))))
       '(0) '(11 9 12))

f:id:brv00:20191107081050j:plain

945+257は1202ですね。正しい結果（正しい10進表現）が得られました。引き算のほうも同じようにしてみましょう。

(foldr (lambda (x ds) (cons (/ (+ x (car ds)) 10) (cons (% (+ x (car ds)) 10) (cdr ds))))
       '(0) '(7 -1 -2))

f:id:brv00:20191107081113j:plain

945-257は10進法で表すと688ですがそうなっていません。
%は、絶対値が除数より小さく、符号が被除数と同じであるような値を返す剰余関数のようです。
ここで欲しいのは、絶対値が除数より小さく、負でない値を返す剰余関数、つまり次のような関数です。

(define (i% x y) (let ((r (% x y))) (if (< r 0) (+ r y) r)))

商を得る関数も新たに定義しなければなりません。
/は、除数をかけてから%で得られる余りを足すともとの数が得られるような値を返す関数です。
ここで必要なのは、除数をかけてから上で定義したi%で得られるような余りを足すともとの数が得られるような値を返す関数です。

剰余と商はリストにこの順でconsするので、この2つをまとめたリストを返す関数を定義しましょう。
これをappendするようにすれば(foldr ...)も少しすっきりします。

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

(foldr (lambda (x ds) (append (i/% (+ x (car ds)) 10) (cdr ds)))
       '(0) '(7 -1 -2))