第4夜:わけのわからない数と大根

数の悪魔*1を題材にプログラミングしてます。今回は大根です。本では計算機で出していました。

じゃ、このトリックの名前、ぜひおぼえておこう。「後ろにホップする」じゃなくて、「大根を抜く」っていうんだ。ほら、地面から根を引き抜くみたいに - 数の悪魔

(define (radish v)
	(define (separate2fig n l)
		(if (< n 1)
			l
			(separate2fig (quotient n 100) (cons (remainder n 100) l))))

	(define (max-number v d)
		(define (max-number-iter n m)
			(if (>= v m)
				(values n (- v m))
				(max-number-iter (- n 1) (- m (* d 10) n n -1))))
		(max-number-iter 9 (+ (* d 90) 81)))

	(define (radish-iter l d a r)
		(if (null? l)
			(cons a r)
			(receive (na nr)
				(max-number (+ (* r 100) (car l)) d)
				(radish-iter (cdr l) (+ (* d 10) na na) (+ (* a 10) na) nr))))

	(radish-iter (separate2fig v '()) 0 0 0)
)

(define (main args)
	(print (radish 5929))
0)

筆算式の開平法で書いてみました。自然数の(小さくて一番近い)平方根を求め、その値と余りをconsセルで返します。結果はこちら。

(77 . 0)

もう少し何か無いかなと探していた途中、2進法を使ったスマートな処理を見つけました(SICPを翻訳された和田英一氏でしょうか)。パラメトロン計算機: 開平法
http://listlibrary.net/ruby-math/2003/08/00vP80du/にあったNewton法も興味深いです。
ルートを開こうは開平法の参考にさせていただきました。
センスは磨けるうちに磨けと思った日でした。
最後に、ウルフラム・アルファさんに聞いてみよう：http://www.wolframalpha.com/input/?i=sqrt%285929%29

*1:Hans Magnus Enzensberger,1997,Der Zahlenteufel,エンツェンスベルガー 丘沢静也(訳),2000,数の悪魔,晶文社