SICPを読み始めた。 問題1.17

６月頭から３週間ほど、東京の某企業でインターン(アルバイト)をしてきた。
そこでは朝９時出勤、夜10時へとへとな状態で帰宅という生活を経験し、
「社会人になったら勉強する時間はない、今のうちに勉強しよう」と切に感じた。

特に、CS関連の基礎を勉強をしようと考え、SICPを読み始めた。
SICPとはStructure and Interpretation of Computer Programsの略であり、書籍のこと。
アルゴリズムの教科書だと思う。
以下のURLに詳しい解説がある。

計算機プログラムの構造と解釈
http://ja.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E6%A9%9F%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0%E3%81%AE%E6%A7%8B%E9%80%A0%E3%81%A8%E8%A7%A3%E9%87%88

で、SICPを読み進めた結果を、ここに残しておこうと思う。
具体的には、SICPに載っている問題の、僕の解答例を残す。
SICPではschemeでアルゴリズムが解説される。
その流れにのっとって、解答例もschemeで残す。

今日は問題1.17を解いた。
問題1.17は、かけ算を、足し算(+)と、引数を２倍にする関数(double)、引数を半分にする関数(halve)でなるべく少ないステップで実行できるように実装せよ、というもの。

例えば、ステップ数が多くてもよいならば、かけ算は以下のように実装できる。
sample:

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

この方法だと、bの数だけ(* a b)という関数が呼ばれる。
このことをbに線形のステップ数というらしい。

僕の解答は以下。

解答:

define (* a b)
 (if (= b 1)
     a
     (if (even? b)
          (double (* a (halve b)))
          (+ a (* a (- b 1)))
     )
  )
)

(define (double x)
  (+ x x)
)

(define (halve x)
  (halvecmp x 1)
)

(define (halvecmp x y)
  (if (= x (double y))
      y
      (halvecmp x (+ y 1))
  )
)

halveをどう実装するか悩んだ。
もっと短くできるかもしれない。