十と三: 2014

2014年12月23日火曜日

何故、夜になると暗くなるのか？

娘と近所のショッピング・モールで買い物をした後の帰り道、娘から質問を受けました。

何故、夜になると暗くなるの？

ようやく、こういう疑問を持つようになってきた＼(^o^)／

いくらでも答えたるで＼(^o^)／

当面は、天動説を唱えることにしよう＼(^o^)／

この大地は、お盆のような形をしています。
落っこちないように巨大な亀に乗った４頭の象によって支えられています。
海の向こうは滝になっていて、巨大な怪物が船乗りを狙っています。
太陽や星は、大地を中心にグルグルと回っています。

この説の問題は、亀の下に何がいるのか不明な点(~_~;)

2014年12月22日月曜日

タイトルの通り、eo光のコースを100Mから1Gへ上げたら繋がらなくなりました。繋がるようになったので、これを書いているのですが、結論は無線LANのファームウェアを更新すれば繋がりました。

eo光から設定を変更する書類に従い、接続設定をした時は使えていました。コース変更をした翌月の10日ぐらいに100Mのコースが使えなくなるのですが、どうやらその日を境に接続できなくなったようです。

最初、無線LANのルータが老朽化のために壊れたのかと思い、新しいものに買い替えたのですが、それでも繋がりませんでした。ただ、全く繋がらないという訳ではなく、次の２つを確認できました。

IDとパスワードを正しく入力すると接続できる旨が表示され、間違えると間違えている旨が表示されるため、eo光のサーバとは通信できている。
IDとパスワードを入力後、無線LANの時刻が設定されていたのでNPTは通っている。

無線LANを介してPCやiPadから外に行けない(~_~;)

あれこれと試した結果、無線LANのファームウェアを更新できることに気付き、更新をしたところPCから外へ繋げることが出来ました＼(^o^)／

2014年12月9日火曜日

高嶺の花

日経新聞の記事です。

記事の文章を引用します。

「何色にも染まらない、高根の花」

「高根の花」って何やねん＼(^o^)／

「高嶺の花」とは、自分には手の届かない高い嶺に咲いている美しい花のことであって、根っこが高い花ではありません(~_~;)

大丈夫か日経新聞＼(^o^)／

2014年12月8日月曜日

[筋トレ] 2014.12.01の週

今週の記録です。
１２/０１（月）73.70kg

　休み

１２/０２（火）73.75kg

　プッシュアップ　２０、　９　　（膝をついた状態）
　ナロースタンス　　５、　４　　（両手の間を拳一つ開けた状態）

　アームカール　　２０、１５　　（5kgの鉄アレイ）

１２/０３（水）73.00kg
　ジョギング　　　1.7km　12'13"

１２/０４（木）72.90kg

　休み

１２/０５（金）73.35kg

　休み

１２/０６（土）74.50kg

　ジョグ　　　　　5.1km 34'39"

ランジ　　　　　５０、５０歩

１２/０７（日）74.35kg

　ジョグ　　　　　4.0km 27'29"

完全にダレています(~_~;)

来週は気合を入れていきます＼(^o^)／

2014年12月6日土曜日

[SICP] 問題 1.40 : Newton法

newtons-methodの手続きと一緒に

(newtons-method (cubic a b c) 1)

の形の式で使い, 三次式 x³ + ax² + bx + c の零点を近似する手続き cubicを定義せよ.

Newton法のための手続きと問題文で指定されたcubic手続きを定義します.

(define dx 0.00001)

(define tolerance 0.00001)

(define (square x) (* x x))

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))

(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) ((deriv g) x)))))

(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))

(define (cubic a b c)
  (lambda (x)
    (+ (* x x x)
       (* a x x)
       (* b x)
       c)))

(newtons-method (cubic 0 0 -10) 1)

実行例として10の三乗根を求めてみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (newtons-method (cubic 0 0 -10) 1)
2.154434690031893
> (expt 2.154434690031893 3)
10.000000000000131
>

2014年12月4日木曜日

[SICP] 問題 1.39 : 正弦関数の連分数展開

正接関数の連分数展開は1770年にドイツの数学者 J. H. Lambertが発表した. xをラジアンで表し,
Lambertの式に基づいて正接関数の近似値を計算する手続き(tan-cf x k) を定義せよ. kは問題1.37と同様, 計算する項数を指定する.

問題文の式から手続きを定義します. 分子がx²となる項からcont-fracを使います.

(define (square x) (* x x))

;; 反復的プロセスを生成
(define (cont-frac n d k)
  (define (iter i result)
    (if (= i 0)
        result
        (iter (- i 1)
              (/ (n i)
                 (+ (d i) result)))))
  (iter k 0))

(define (tan-cf x k)
  (/ x
     (+ 1 (cont-frac (lambda (i) (- (square x)))
                     (lambda (i) (+ (* i 2) 1))
                     k))))

tanは定義済みですので, その結果と比較します.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (tan 1.0)
1.5574077246549023
> (tan-cf 1.0 10)
1.557407724654902
> (tan-cf 1.0 100)
1.557407724654902
>

2014年12月2日火曜日

[SICP] 問題 1.38 : 連分数による自然対数の底eの近似

1737年, スイスの数学者 Leonhard Eulerは De Fractionibus Continuisというメモを発表した. その中にeを自然対数の底としてe - 2 の連分数展開がある. この分数ではNiはすべて1, Diは順に1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ... . 問題1.37のcont-fracを使い, Eulerの展開によりeを近似するプログラムを書け.

D_iの値は, iを3で割った余りが2のときに2, 4, 6, 8と増えています. 手続きを定義すると次のようになります.

;; 反復的プロセスを生成
(define (cont-frac n d k)
  (define (iter i result)
    (if (= i 0)
        result
        (iter (- i 1)
              (/ (n i)
                 (+ (d i) result)))))
  (iter k 0))

(define (euler k)
  (+ 2
     (cont-frac (lambda (i) 1.0)
                (lambda (i) 
                  (if (= (remainder i 3) 2)
                      (* 2.0 (/ (+ i 1) 3))
                      1.0))
                k)))

実行してみます.自然対数の底は定義済みでしたので,その結果と比較します.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> e
2.718281828459045
> (euler 10)
2.7182817182817183
> (euler 100)
2.7182818284590455
>

それらしい値が得られています.

2014年12月1日月曜日

[筋トレ] 2014.11.24の週

今週の記録です。
11/２４（月）75.10kg

　休み

11/２５（火）74.50kg

　休み

11/２６（水）73.45kg

　ランジ（左）　　１５、１０　　
　ランジ（右）　　１５、１０　　
　リアレイズ　　　１０、１０　　（5kgの鉄アレイ）

　レッグレイズ　　１５、　８

11/２７（木）73.65kg

　プッシュアップ　２０、１１　　（膝をついた状態）
　ナロースタンス　　５、　４　　（両手の間を拳一つ開けた状態）

11/２８（金）73.70kg

　休み

11/２９（土）74.80kg

　ジョグ　　　　　5.1km 37'11"

11/３０（日）74.70kg

　ランジ（左）　　１６、１５　　
　ランジ（右）　　２０、１８　　
　リアレイズ　　　１２、１０　　（5kgの鉄アレイ）

　レッグレイズ　　１５、１１

少し、サボリ気味(~_~;)

2014年11月29日土曜日

[SICP] 問題 1.37 : 連分数

a. 無限の連分数(continued fraction)は
の形の式である. 例えばNiとDiがすべて1の無限連分数展開が1/φになることが示せる. φは(1.2.2節で示した)黄金比. 無限連分数の近似値のとり方の一つは, 与えられた項数で展開を中断することで, そういう中断--- k項有限連分数(k-term finite continued fraction)という---は
の形である. nとdを一引数(項の添字i)で連分数の項のNiとDiを返す手続きとする. (cont-frac n d k)がk項有限連分数を計算するような手続きcont-fracを定義せよ.

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           k)

のkの順次の値で1/φの近似をとり, 手続きを調べよ. 4桁の精度の近似を得るのに, kはどのくらい大きくしなければならないか.

b. cont-fracが再帰的プロセスを生成するなら, 反復的プロセスを生成するものを書け. 反復的プロセスを生成するなら, 再帰的プロセスを生成するものを書け.

連分数を求める手続きを定義します.

;; 再帰的プロセスを生成
(define (cont-frac-r n d k)
  (define (iter i)
    (if (> i k)
        0
        (/ (n i)
           (+ (d i) (iter (+ i 1))))))
  (iter 1))

;; 反復的プロセスを生成
(define (cont-frac-i n d k)
  (define (iter i result)
    (if (= i 0)
        result
        (iter (- i 1)
              (/ (n i)
                 (+ (d i) result)))))
  (iter k 0))

(define (phi-r k)
  (/ 1 (cont-frac-r (lambda (i) 1.0)
                    (lambda (i) 1.0)
                    k)))

(define (phi-i k)
  (/ 1 (cont-frac-i (lambda (i) 1.0)
                    (lambda (i) 1.0)
                    k)))

再帰的プロセスを生成する手続きは, 上の方から計算しています. 反復的プロセスを生成する手続きは, 下の方から計算するようにしています.

黄金比Φの計算をしてみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (phi-r 15)
1.6180327868852458
> (phi-i 15)
1.6180327868852458
>

kの値を15にすれば良さそうです.

2014年11月28日金曜日

[SICP] 問題 1.36 : x^x=1000

問題1.22で示した基本のnewlineとdisplayを使い, 生成する近似値を順に印字するようfixed-pointを修正せよ. 次にx log(1000)/log(x)の不動点を探索することで, xx = 1000の解を見つけよ. (自然対数を計算するSchemeの基本log手続きを使う.) 平均緩和を使った時と使わない時のステップ数を比べよ. ({ fixed-pointの予測値を1にして始めてはいけない. log(1)=0による除算を惹き起すからだ.)

近似値を表示するための処理をfixed-pointに追加しなくてはなりません. 追加する場所は, 内部手続tryが適切でしょう. 修正した手続きは次のとおりです.

(define (average x y)
  (/ (+ x y) 
     2))

(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (display guess)
      (newline)
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

x^x=1000を満たすxを求めてみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fixed-point (lambda (x) (/ (log 1000) (log x))) 
               2.0)
2.0
9.965784284662087
3.004472209841214
6.279195757507157
3.759850702401539
5.215843784925895
4.182207192401397
4.8277650983445906
4.387593384662677
4.671250085763899
4.481403616895052
4.6053657460929
4.5230849678718865
4.577114682047341
4.541382480151454
4.564903245230833
4.549372679303342
4.559606491913287
4.552853875788271
4.557305529748263
4.554369064436181
4.556305311532999
4.555028263573554
4.555870396702851
4.555315001192079
4.5556812635433275
4.555439715736846
4.555599009998291
4.555493957531389
4.555563237292884
4.555517548417651
4.555547679306398
4.555527808516254
4.555540912917957
4.555532270803653
> (expt 2 3)
8
> (expt 4.555532270803653 4.555532270803653)
999.9913579312362
>

期待した結果が得られているようです.

平均緩和を使ってみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 
               2.0)
2.0
5.9828921423310435
4.922168721308343
4.628224318195455
4.568346513136242
4.5577305909237005
4.555909809045131
4.555599411610624
4.5555465521473675
4.555537551999825
>

ステップ数が1/3以下になっています.

2014年11月27日木曜日

[SICP] 問題 1.35 : 不動点の探索による黄金比の計算

(1.2.2節の)黄金比φが変換 x → 1 + 1/x の不動点であることを示し, この事実を使いfixed-point手続きによりφを計算せよ.

黄金比の定義は次のとおりです.
　　φ² = φ + 1
この両辺をφで割ります.
　　φ = 1 + 1/φ
この結果から,
　　変換 x → 1 + 1/x
が得られます.

不動点を求める手続きは次のとおりです.

(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

実行してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fixed-point (lambda (x) (+ 1 (/ 1 x)))
               1.0)
1.6180327868852458
>

p.21から黄金比の値は約1.6180ですから, 求める結果が得られています.

2014年11月26日水曜日

[SICP] 問題 1.34 : (f f)の評価

手続き

(define (f g)
  (g 2))

を定義したとする. その時

(f square)
4

(f (lambda (z) (* z (+ z 1))))
6

解釈系に組合せ(f f)を(意地悪く)評価させるとどうなるか. 説明せよ.

問題文の手続きを定義して実行してみます. 手続きは次の通り.

(define (f g)
  (g 2))

(define (square x) (* x x))

実行結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (f square)
4
> (f (lambda (z) (* z (+ z 1))))
6
> (f f)
. . application: not a procedure;
 expected a procedure that can be applied to arguments
  given: 2
  arguments...:
   2
>

(f f)を評価するとエラーが生じています. その理由を考えます.

手続きfの定義から(f f)を評価した場合の置き換えは次のようになります.

  (f f)
= (f 2)
= (2 2)

「２」は手続きではないのでエラーが生じます.

2014年11月25日火曜日

[SICP] 1.2.6 : expmodでbaseのexp乗をmで割った余りが求まる理由

baseのexp乗をmで割った余りを求める手続きexpmodは次のような定義になります.

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

法演算について馴染みがないと, なぜ, この手続で余りが求まるか分からないと思います. ここで簡単に計算の仕組みを説明します.

まず, 整数aをmで割った余りをr, 整数bをmで割った余りをtとします. すると整数aとbは次のように表現できます.

   a = qm + r
   b = sm + t

このaとbの和をmで割った余りを求めます.

   a + b = (qm + r) + (sm + t)
         = (q + s)m + (r + t)

(q + s)mはmで割り切れるので, a + bをmで割った余りはr+tをmで割った余りと等しくなります.

aにある整数cを掛けた値をmで割った余りも求めてます.

   ca = cqm + cr

caをmで割った余りはcrをmで割った余りと等しくなります.

続けて, aとbの積をmで割った余りを求めます.

   ab = (qm + r)(sm + t)
      = qsm^2 + (qt + rs)m + rt

abをmで割った余りはrtをmで割った余りと等しくなります.

積についての結果から,　aのx乗をmで割った余りはrのx乗をmで割った余りと等しくなります.

ここで, 手続きの定義に戻り, baseのexp乗をmで割った余りを考えます.

１）expが偶数のときを考えます.

baseの(exp/2)乗をmで割った余りをrとします. 上で計算した結果から, rの2乗をmで割った余りは, baseのexp乗をmで割った余りと等しくなります.

2) expが奇数のときを考えます.

baseの(exp-1)乗をmで割った余りをrとします. 上で計算した結果から, base*rをmで割った余りは, baseのexp乗をmで割った余りと等しくなります.

これらの結果から, 手続きexpmodによりbaseのexp乗をmで割った余りを求められることが分かります.

2014年11月24日月曜日

[筋トレ] 2014.11.17の週

今週の記録です。
11/1７（月）73.65kg

　プッシュアップ　１７、　４　　（膝をついた状態）
　ナロースタンス　　５、　６　　（両手の間を拳一つ開けた状態）
　アームカール　　１５、１２　　（5kgのダンベル）

11/1８（火）73.65kg

　ジョグ　　　　　3.4km 25'22"

11/1９（水）74.45kg

　ランジ（左）　　１５、　６　　
　ランジ（右）　　１５、１０　　
　リアレイズ　　　１４、　８　　（5kgの鉄アレイ）

　レッグレイズ　　１５、１０

11/２０（木）73.30kg

　プッシュアップ　１７、　７　　（膝をついた状態）
　ナロースタンス　　６、　５　　（両手の間を拳一つ開けた状態）
　アームカール　　１５、１５　　（5kgのダンベル）

11/２１（金）73.65kg

　休み

11/２２（土）74.80kg
　休み

11/２３（日）75.10kg

　ジョグ　　　　　4.1km 29'38"

　ランジ　　　　　４０、３０歩

スクワットが効かないのでランジに変更しました。

娘の相手をしなくても良くなってきたので、ジョギングできるようになりました＼(^o^)／

体を慣らすために、かなりゆっくりペースです。

2014年11月23日日曜日

三菱鉛筆のスタイルフィットを使いやすくする方法

三菱鉛筆のスタイルフィットは、ゲルインクボールペンの中でも使いやすい方だと思います。同じ三菱鉛筆のシグノよりも文字を書いた時の線の広がりが抑えられており、性能が良いように感じています。

しかし、スタイルフィットのホルダーは使いにくい(~_~;)

ペンを持つところにゴムが付いていないので、手の脂がつくと滑りやすい。
ちょっとした衝撃でペン先が戻ってしまう。

色々と試した結果、パイロットの4色ボールペンであればスタイルフィットの芯を使えました＼(^o^)／

2014年11月22日土曜日

[SICP] 問題 1.27 : カーマイケル数

脚注47のCarmichael数が本当にFermatテストをだますことを示せ. それには整数nをとり, a < nなるすべてのaで, aⁿがnを法としてaの合同になるかどうか見る手続きを書き, Carmichael数でその手続きを使ってみる.

a < nを満たす正の整数aについて, expmodを用いてaⁿがnを法としてaと合同になるか調べます. 手続きは次のとおりです.

(define (square x) (* x x))

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

(define (pass-fermat-test? n)
  (define (loop a)
    (or (= a n)
        (and (= (expmod a n n) a)
             (loop (+ a 1)))))
  (loop 1))

評価してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (pass-fermat-test? 561)
#t
> (pass-fermat-test? 1105)
#t
> (pass-fermat-test? 1729)
#t
> (pass-fermat-test? 2465)
#t
> (pass-fermat-test? 2821)
#t
> (pass-fermat-test? 6601)
#t
> (pass-fermat-test? 6605)
#f
> (pass-fermat-test? 6607)
#t
>

脚注のカーマイケル数は, フェルマー・テストをパスしています. 間違えて, 必ず#tを返す手続きを実装していては困りますので, 合成数6605では#fが返ってくることを確認しています.

2014年11月21日金曜日

[SICP] 問題 1.26 : expmodの計算に必要なステップ数

Louis Reasonerは問題1.24がなかなかうまくいかなかった. 彼の fast-prime?はprime?よりずっと遅いようであった. Louisは友人のEva Lu Atorに助けを求めた. Louisのプログラムを見ていると, squareを呼び出す代りに乗算を陽に使うように変っていた.

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (* (expmod base (/ exp 2) m)
                       (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

「違いが分らん」とLouis, 「分る」とEvaがいった. 「手続きをこのように書き替えたので, Θ(log n)のプロセスをΘ(n)のプロセスにしてしまった.」説明せよ.

引数expの値に注目して, 手続きが生成するプロセスを図示してみます. まず, squareを用いた場合.

13 -- 12 -- 6 -- 3 -- 2 -- 1 -- 0

まず, squareを用いず, 乗算を用いた場合.

13 -- 12 -- 6 -- 3 -- 2 -- 1 -- 0
       |    |         |
       |    |         + -- 1 -- 0
       |    |
       |    + -- 3 -- 2 -- 1 -- 0
       |              |
       |              + -- 1 -- 0
       |
       + -- 6 -- 3 -- 2 -- 1 -- 0
            |         |
            |         + -- 1 -- 0
            |
            + -- 3 -- 2 -- 1 -- 0
                      |
                      + -- 1 -- 0

このように, squareを用いずに乗算を用いた場合, expの値が偶数の場合, expmodを２回呼び出しています. そのため, Θ(log n)のプロセスをΘ(n)のプロセスにしてしまい, 計算に時間がかかるようになります.

2014年11月20日木曜日

[SICP] 問題 1.25 : expmodの必要性

Alyssa P. Hackerはexpmodを書くのに多くの余分なことをやったと不満で, 結局べき乗の計算法は知っているから

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))

と単純に書ける筈だといった. これは正しいか. これも高速素数テストと同じに使えるか, 説明せよ.

テキストp.29の脚注48にあるように, ここでは200桁の整数が素数であるかどうかを問題としています. expmodの引数であるbaseやexpに200桁の整数が与えられるため, fast-exptで計算することは困難であり現実的ではありません. そのため, p.28のexpmodの定義が必要となります.

2014年11月19日水曜日

[SICP] 問題 1.24 : フェルマー・テスト

問題1.22のtimed-prime-test手続きをfast-prime?(Fermat法参照) を使うように変え, その問題で見つけた12個の素数をテストせよ. FermatテストはΘ(log n)の増加なので, 1,000,000近くの素数をテストする時間を1000近くの素数をテストする時間と比べ, どの位と予想するか. データはその予想を支持するか. 違いがあれば説明出来るか.

フェルマーの小定理を用いた素数性のテストをする手続きを定義します. 手続きrandomの引数の範囲に制限があるため, 少し小細工をしています.

(define (square x) (* x x))

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))  

(define (rnd n)
  (remainder (* (random (remainder n 4294967087))
                (random (remainder n 4294967087)))
             n))

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (rnd (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))

;; 素数を求めるために必要な時間を計測する
(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (current-milliseconds)))

(define (start-prime-test n start-time)
  (if (fast-prime? n 10000)
      (report-prime (- (current-milliseconds) start-time))))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

(define (search-for-primes start end)
  (cond ((< start end)
         (timed-prime-test start)
         (search-for-primes (+ start 1) end))
        (else 
         (newline)
         (display "end"))))

素数を求めてみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (search-for-primes 100000000000000 100000000000100)
100000000000031 *** 325
100000000000067 *** 344
100000000000097 *** 312
end
> (search-for-primes 1000000000000000 1000000000000200)
1000000000000037 *** 342
1000000000000091 *** 351
1000000000000159 *** 340
end
> (search-for-primes 10000000000000000 10000000000000100)
10000000000000061 *** 390
10000000000000069 *** 375
10000000000000079 *** 366
end
>

この程度のデータでは, 何も言えそうにありません.

2014年11月18日火曜日

[筋トレ] 2014.11.10の週

今週の記録です。
11/10（月）

　娘の腸炎が伝染って休み

11/11（火）

　休み

11/12（水）72.95kg

　休み

11/13（木）73.40kg
　スクワット　　　２０、２０　　（5kgの鉄アレイ）
　リアレイズ　　　１０、　８　　（5kgの鉄アレイ）
　レッグレイズ　　１５、１０

11/14（金）73.55kg

　プッシュアップ　２０、１０　　（膝をついた状態）
　ナロースタンス　　３、　５　　（両手の間を拳一つ開けた状態）
　アームカール　　１２、　９　　（5kgのダンベル）

11/15（土）74.00kg
　娘の看病のため休み

11/16（日）74.45kg
　スクワット　　　３０、３０　　（5kgの鉄アレイ）
　リアレイズ　　　１２、１０　　（5kgの鉄アレイ）
　レッグレイズ　　１６、１２

娘の腸炎が伝染ってしまい、嘔吐と発熱に苦しめられました(~_~;)

ほぼ２日間、絶食したので体重は減りました。週の後半には順調に回復しました＼(^o^)／

2014年11月17日月曜日

[SICP] 問題 1.23 : 素数性を判定する数を奇数に限定

本節の初めのsmallest-divisorは多くの不要な計算をする: 数が2で割り切れるか調べた後は, より大きい偶数で割り切れるか調べるのは無意味である. test-divisorが使う値は, 2, 3, 4, 5, 6, ...ではなく, 2, 3, 5, 7, 9, ...であるべきだ. この変更を実装するため, 入力が2なら3 を返し, そうでなければ入力に2足したものを返す手続きnextを定義せよ. smallest-divisorを(+ test-divisor 1)ではなく, (next test-divisor)を使うように修正せよ. このように修正した smallest-divisorにしたtimed-prime-testで, 問題1.22で見つけた12 個の素数をテストせよ. この修正はテストのステップを半分にしたので, 二倍速く走ることが期待される. この期待は確められるか. そうでなければ, 得られた二つのアルゴリズムの速度の比はどうであったか. それが2と違う事情を説明せよ.

問題文にあるように手続きを修正します.

(define (square x) (* x x))

(define (divides? a b)
  (= (remainder b a) 0))

;; 問題文により追加
(define (next n)
  (if (= n 2)
      3
      (+ n 2)))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (next test-divisor)))))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (prime? n)
  (= n (smallest-divisor n)))

;; 素数を求めるために必要な時間を計測する
(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (current-milliseconds)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (current-milliseconds) start-time))))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

(define (search-for-primes start end)
  (cond ((< start end)
         (timed-prime-test start)
         (search-for-primes (+ start 1) end))
        (else 
         (newline)
         (display "end"))))

問題 1.22で求めた12個の素数を判定するための時間を計測します.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (search-for-primes 100000000000000 100000000000100)
100000000000031 *** 624  (939)
100000000000067 *** 571  (1397)
100000000000097 *** 598  (949)
end
> (search-for-primes 1000000000000000 1000000000000200)
1000000000000037 *** 1907  (2891)
1000000000000091 *** 1965  (2928)
1000000000000159 *** 1877  (2919)
end
> (search-for-primes 10000000000000000 10000000000000100)
10000000000000061 *** 5925  (9149)
10000000000000069 *** 5887  (9166)
10000000000000079 *** 5887  (9174)
end
>

カッコ内に問題 1.22で計測した時間を書いています. 問題 1.22の結果と見比べると, 時間は短くなっていますが, 半分とまでは言えません. 手続きnextでnが2であるかどうかを判定しているからでしょう.

2014年11月16日日曜日

３歳児が吐いた時の対策

娘が深夜２時頃に吐き出したのに気づき、仕方がないので両手で受けました(T_T)

その後、娘の体調は良くなったのですが、娘が吐き出して４８時間後に私と妻の体調が一気に悪化、嘔吐と発熱に苦しめられました(T_T)

今回学んだこと。

嘔吐物を素手で受けない、処理するときは手袋をはめる。
手袋に加えてマスクもする。
洗面器に新聞で覆っておくと、吐いた時に洗面器を洗わなくて済む。
服などを消毒するときは塩素系の洗剤を使う。アルコールは効かないらしい。
消毒がめんどくさい時は捨てる。
ドアノブ、手すりなども消毒する。
ポカリスエットを用意する。アクエリアスはダメらしい。

次は感染しないように準備をしておきます＼(^o^)／

2014年11月15日土曜日

[SICP] 問題 1.22 : 素数を求めるために必要な計算量

殆んどのLispの実装には基本手続きruntimeがあり, システムが走った時間を(例えばマイクロ秒で)示す整数を返す. 次のtimed-prime-test手続きは整数nで呼び出されると, nを印字し, nが素数かどうかを調べ, nが素数なら手続きは三つの星印とテストに要した時間を印字する.

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

この手続きを使い, 指定範囲の連続する奇整数について素数性を調べる手続きsearch-for-primesを書け. その手続きで, それぞれ1,000, 10,000, 100,000, 1,000,000より大きい, 小さい方から三つの素数を見つけよ. 素数をテストする時間に注意せよ. テストのアルゴリズムはΘ(√n)の増加の程度だから, 10,000前後の素数のテストは1,000前後の素数のテストの√10倍かかると考えよ. 時間のデータはこれを支持するか. 100,000, 1,000,000のデータは√n予想のとおりだろうか. 結果はプログラムが計算に必要なステップ数に比例した時間で走るという考えに合っているか.

手続きruntimeの代わりにcurrent-millisecondsを使います. 手続きは次のようになります.

(define (square x) (* x x))

(define (divides? a b)
  (= (remainder b a) 0))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (prime? n)
  (= n (smallest-divisor n)))

;; 素数を求めるために必要な時間を計測する
(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (current-milliseconds)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (current-milliseconds) start-time))))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

(define (search-for-primes start end)
  (cond ((< start end)
         (timed-prime-test start)
         (search-for-primes (+ start 1) end))
        (else 
         (newline)
         (display "end"))))

問題文では, 素数を求める範囲を1000から始めていますが, 時間を計測できないため, もっと大きな数字から始めます. 測定結果は次のとおりです. 見やすいように, 不要な結果を削除しています.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (search-for-primes 100000000000 100000000100)
100000000003 *** 45
100000000019 *** 29
100000000057 *** 28
100000000063 *** 29
end
> (search-for-primes 1000000000000 1000000000100)
1000000000039 *** 97
1000000000061 *** 90
1000000000063 *** 90
end
> (search-for-primes 10000000000000 10000000000100)
10000000000037 *** 293
10000000000051 *** 302
10000000000099 *** 307
end
> (search-for-primes 100000000000000 100000000000100)
100000000000031 *** 939
100000000000067 *** 1397
100000000000097 *** 949
end
> (search-for-primes 1000000000000000 1000000000000200)
1000000000000037 *** 2891
1000000000000091 *** 2928
1000000000000159 *** 2919
end
> (search-for-primes 10000000000000000 10000000000000100)
10000000000000061 *** 9149
10000000000000069 *** 9166
10000000000000079 *** 9174
end

結果を見ると, nを１桁増やすと時間は約３倍になっており、 nを２桁増やすと時間は約10倍になっています. このことから, プログラムが計算に必要なステップ数に比例した時間で走るという考えに合っていると言えます.

問題文には, search-for-primesは「指定範囲の連続する奇整数について」とありますが, この条件を満たしていません. 実害はないのでこのままとします.

2014年11月14日金曜日

[SICP] 問題 1.21 : 最小除数の探索

smallest-divisor手続きを使い, 次の数の最小除数を見つけよ: 199, 1999, 19999.

テキストの手続きを入力します.

(define (square x) (* x x))

(define (divides? a b)
  (= (remainder b a) 0))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (prime? n)
  (= n (smallest-divisor n)))

評価してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (smallest-divisor 199)
199
> (smallest-divisor 1999)
1999
> (smallest-divisor 19999)
7
>

2014年11月13日木曜日

[SICP] 問題 1.33 : filtered-accumulate

組み合せる項にフィルタ(filter)の考えを入れることで, accumulate(問題1.32)の更に一般的なものが得られる. つまり範囲から得られて, 指定した条件を満した項だけを組み合せる. 出来上ったfiltered-accumulate抽象は, accumulate と同じ引数の他, フィルタを指定する一引数の述語をとる. filtered-accumulateを手続きとして書け. filtered-accumulateを使い, 次をどう表現するかを示せ.

a. 区間a, bの素数の二乗の和(prime?述語は持っていると仮定する.)
b. nと互いに素で, nより小さい正の整数(つまりi < nでGCD(i, n)=1なる全整数i)の積

フィルターに対応したaccumulateを定義します. 考え方としては, filterが真を返すときはaccumulateと同様の処理をし, 偽を返すときはcombinerを使った計算をしないようにします. 手続きは次のようになります.

(require (lib "racket/trace.ss"))

(define (inc x) (+ x 1))

(define (square x) (* x x))

(define (cube x) (* x x x))

(define (divides? a b)
  (= (remainder b a) 0))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

(define (smallest-divisor n)
  (find-divisor n 2))

(define (prime? n)
  (= n (smallest-divisor n)))

;; 再帰的プロセスを生成する.
(define (filtered-accumulate-r filter combiner null-value term a next b)
  (cond ((> a b) 
         null-value)
        ((filter a)
         (combiner (term a)
                   (filtered-accumulate-r filter combiner null-value term (next a) next b)))
        (else
         (filtered-accumulate-r filter combiner null-value term (next a) next b))))

;; 反復的プロセスを生成する.
(define (filtered-accumulate-i filter combiner null-value term a next b)
  (define (iter a result)
    (cond ((> a b) 
           result)
          ((filter a) 
           (iter (next a) (combiner (term a) result)))
          (else
           (iter (next a) result))))
  (iter a null-value))

;; 区間a, bの素数の二乗の和
(define (sum-prime-square a b)
  (filtered-accumulate-r prime?
                         +
                         0
                         square
                         a
                         inc 
                         b))

;; nと互いに素で, nより小さい正の整数の積
(define (product-disjoint n)
  (define (disjoint? x) (= 1 (gcd n x)))
  (filtered-accumulate-r disjoint?
                         *
                         1
                         identity
                         1
                         inc
                         (- n 1)))

区間a, bの素数の二乗の和を求めてみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (sum-prime-square 2 10)   
87
> (+ (square 2) (square 3) (square 5) (square 7))
87
>

2から10の間の素数は, 2, 3, 5, 7ですから, 計算は合っています.

nと互いに素で, nより小さい正の整数の積を求めてみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (product-disjoint 10)
189
> (* 1 3 7 9)
189
>

10よりも小さい正の整数で10と互いに素になる数は, 1, 3, 7, 9ですから, 計算は合っています.

2014年11月12日水曜日

[SICP] 問題 1.19 : Fibonacci数を対数的ステップ数で計算する

Fibonacci数を対数的ステップ数で計算するうまいアルゴリズムがある. 1.2.2 節のfib-iterプロセスで使った状態変数aとbの変換: a ← a + bとb ← aに注意しよう. この変換をTと呼ぶ. 1と0から始め, Tを繰り返してn回作用させると, Fib(n + 1)とFib(n)の対が出来る. いいかえれば, Fibonacci数は対(1, 0)にTⁿ, つまり変換Tのn乗を作用させると得られる. さて, T_pqは対(a, b)をa ← bq + aq + apとb ← bp + aqに従って変換するものとし, Tを変換族T_pqのp = 0とq = 1の特例としよう. 変換T_pqを二回使うとその効果は同じ形式の変換T_p'q'を一回使ったのと同じになることを示し, p'とq'をp, qを使って表せ. これで変換を二乗する方法が得られ, fast-exptのように逐次平方を使い, Tⁿを計算することが出来る. これらをすべてまとめ, 対数的ステップ数の以下の手続きを完成せよ.

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   ＜??＞      ; p'を計算
                   ＜??＞      ; q'を計算
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

変換T_pqは次のような行列として表現できます.

T_pq=	[	p+q	q	]
		q	p

変換T_p'q'はT_pq²となります. T_pq²を計算し整理すると次のようになります.

T_p'q'=	[	(p²+q²) + (2pq+q²)	2pq+q²	]
		2pq+q²	p²+q²

変換T_p'q'とT_pqを見比べると, p'とq'はpとqを用いて次のように表せます.

p'=	p²+q²
q'=	2pq+q²

上で求めたp'とq'を使って手続きを定義すると次のようになります. 計算結果を検証するために, p.22の手続きもfib0として定義します.

(require (lib "racket/trace.ss"))

(define (fib0 n)
  (define (iter a b count)
    (if (= count 0)
        b
        (iter (+ a b) a (- count 1))))
  (iter 1 0 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (* p p) (* q q))
                   (+ (* 2 p q) (* q q))
                   (/ count 2)))
        (else
         (fib-iter (+ (* b q) (* a q) (* a p))
                   (+ (* b p) (* a q))
                   p
                   q
                   (- count 1)))))

(define (fib n)
  (fib-iter 1 0 0 1 n))

;;(trace fib-iter)

計算結果が正しいことを確認します.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (map fib0 '(0 1 2 3 4 5 6 7))
(0 1 1 2 3 5 8 13)
> (map fib '(0 1 2 3 4 5 6 7))
(0 1 1 2 3 5 8 13)
>

トレースしてみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fib 30)
>(fib-iter 1 0 0 1 30)
>(fib-iter 1 0 1 1 15)
>(fib-iter 2 1 1 1 14)
>(fib-iter 2 1 2 3 7)
>(fib-iter 13 8 2 3 6)
>(fib-iter 13 8 13 21 3)
>(fib-iter 610 377 13 21 2)
>(fib-iter 610 377 610 987 1)
>(fib-iter 1346269 832040 610 987 0)
<832040
832040
>

トレースの結果を見ると, 対数的ステップ数で計算していることが分かります.

2014年11月11日火曜日

[筋トレ] 2014.11.03の週

今週の記録です。
11/03（月）75.30kg

　プッシュアップ　１５、１０　　（膝をついた状態）
　ナロースタンス　　３、　３　　（両手の間を拳一つ開けた状態）
　アームカール　　１５、２０　　（5kgのダンベル）

11/04（火）74.30kg

　休み

11/05（水）74.60kg

　スクワット　　　３０、２５　　（5kgの鉄アレイ）
　リアレイズ　　　１２、　７　　（5kgの鉄アレイ）
　レッグレイズ　　１５、１０

11/06（木）74.85kg

　プッシュアップ　１６、１２　　（膝をついた状態）
　ナロースタンス　　５、　４　　（両手の間を拳一つ開けた状態）
　アームカール　　２０、１７　　（5kgのダンベル）

11/07（金）74.75kg

　休み

11/08（土）75.15kg
　娘の看病のため休み

11/09（日）75.35kg
　娘の看病のため休み

土日もトレーニングをする予定だったのですが、娘が土曜日の午前２時ぐらいから夕食を吐いて、明け方まで何度も吐いたのでトレーニングできませんでした。

日曜の昼過ぎには回復したみたいで、色々と食べれるようになりました。一安心です。

2014年11月9日日曜日

11月3日にボーネルンド KID-O-KIDへ行ってきました＼(^o^)／

１ヶ月ぶりぐらいに娘をボーネルンド KID-O-KIDへ連れて行きました。マンガのような目に遭いました(T_T)

11時前に入って、出たのが13時半ぐらい。２時間半も遊ぶとは(~_~;)
まだ遊び足りないみたいで、地下1Fのボーネルンドのショップで遊び始める。
ボーネルンドのショップを出たのが14時半ぐらい。
この時点で予定より1時間以上遅れている(~_~;)
15時ちょうどのバスに乗れば、実家の近くで降りられて便利。
バスに間に合う電車に乗ろうと頑張ったが目の前で電車の扉が閉じる(T_T)
実家の最寄り駅に着いたらバスは5分前に出ていた。
15時30分のバスに乗れば、実家まで700m程度なので悪くない(^O^)
少し離れたバス停から実家へ向けて歩いていたら途中にある公園で娘が遊び始める。
いつの間にか娘が犬のウンコを踏んでいる。しかも出来たてを踏んだっぽい(T_T)
娘を実家へ連れて行き、遅い昼食を食べさせている間に靴を洗う。
靴を洗い終わってから、遅い昼食をとる。夕食も近いので軽く。
いつもなら、父に駅まで車で送ってもらえるのだが、父が酔っ払っているorz
17時に駅に向かう最終のバスが出るので、食べ終わったらすぐにバス停へ移動。

ふんだり蹴ったりでした。

この遊び場は、有料で10分延長するごとに100円かかります。こういう場所へ子供を連れてきて、子供を放ったらかしてスマホで何かし続けている親御さんを見かけます。子供より大事なことが書いてあるのでしょう。

2014年11月8日土曜日

[SICP] 問題 1.18 : 対数的ステップ数の乗算手続き（反復的プロセス）

問題1.16, 1.17の結果を使い, 加算, 二倍, 二分による, 対数的ステップ数の, 二つの整数の乗算の反復的プロセスを生成する手続きを工夫せよ.

問題 1.16の結果を参考にして手続きを定義します. 0や負の数をかけた場合の扱いは, ループに入る前に判定してます.

(require (lib "racket/trace.ss"))

(define (double x) (* x 2))

(define (halve x) (/ x 2))

(define (fast-mult-iter a b p)
  (cond ((= b 0) p)
        ((even? b) (fast-mult-iter (double a) (halve b) p))
        (else (fast-mult-iter a (- b 1) (+ a p)))))

(define (fast-mult a b)
  (cond ((< b 0) (* -1 (fast-mult-iter a (abs b) 0)))
        ((= b 0) 0)
        (else (fast-mult-iter a b 0))))

(trace fast-mult-iter)

p+a×bを考え, pに計算の途中経過をため込むことにします. pを0から始めます. p + a×bの計算について, 奇数と偶数の場合に分けて, 計算をどのように進めるかを考えます.

1) bが奇数の場合, b = m+1とする. 次の式が成立する.

p + a×(m+1) = (p+a) + (a×m)

(p+a)が次のpとなります.
2) nが偶数の場合, b = 2mとする. 次の式が成立する.

P + a×(2m) = p + double(a)×m

double(a)が次のaとなります.

実行結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fast-mult 3 45)
>(fast-mult-iter 3 45 0)
>(fast-mult-iter 3 44 3)
>(fast-mult-iter 6 22 3)
>(fast-mult-iter 12 11 3)
>(fast-mult-iter 12 10 15)
>(fast-mult-iter 24 5 15)
>(fast-mult-iter 24 4 39)
>(fast-mult-iter 48 2 39)
>(fast-mult-iter 96 1 39)
>(fast-mult-iter 96 0 135)
<135
135
> (fast-mult 4 0)
0
> (fast-mult 5 -8)
>(fast-mult-iter 5 8 0)
>(fast-mult-iter 10 4 0)
>(fast-mult-iter 20 2 0)
>(fast-mult-iter 40 1 0)
>(fast-mult-iter 40 0 40)
<40
-40
>

トレースの結果から, 反復的プロセスを生成していることが分かります.

2014年11月7日金曜日

[SICP] 問題 1.32 : accumulate

a. sumと(問題1.31の)productは, 一般的なアキュムレーションの関数:

(accumulate combiner null-value term a next b)

を使い, 項の集りを組み合せるaccumulateという更に一般的なものの特殊な場合であることを示せ.
accumulateは引数としてsumや productと同様, 項と範囲指定と, 先行する項のアキュムレーションと現在の項をどう組み合せるかを指定する(二引数の)combiner手続き, 項がなくなった時に使う値を指定するnull-valueをとる. accumulateを書き, sumやproductがaccumulateの単なる呼出しで定義出来ることを示せ.

b. 上のaccumulateが再帰的プロセスを生成するなら, 反復的プロセスを生成するものを書け. 反復的プロセスを生成するなら, 再帰的プロセスを生成するものを書け.

手続きsumとproductを比較すると, 「＋」と「＊」がcombiner, 「０」と「１」がnull-valueに対応します. 手続きを定義すると次のようになります.

(require (lib "racket/trace.ss"))

(define (square x) (* x x))

(define (cube x) (* x x x))

;; 再帰的プロセスを生成する.
(define (accumulate-r combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a)
                (accumulate-r combiner null-value term (next a) next b))))

;; 反復的プロセスを生成する.
(define (accumulate-i combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner (term a) result))))
  (iter a null-value))

;; 総和の定義
(define (sum term a next b)
  (accumulate-r + 0 term a next b))

;; 定積分を求める.
(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx))

;; 指定した範囲の関数値の積を求める.
(define (product term a next b)
  (accumulate-i * 1 term a next b))

;; 円周率を求める. 
(define (my-pi n)
  (define (term x) 
    (/ (* x (+ x 2)) (square (+ x 1))))
  (define (next x)
    (+ x 2))
  (* 4.0 (product term 2 next n)))

実行してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (integral cube 0 1 0.01)
0.24998750000000042
> (integral cube 0 1 0.001)
0.249999875000001
> (my-pi 10000)
3.141749705738071
> (my-pi 100000)
3.141608361278168
>

これまでの問題と同様に計算できています.

2014年11月5日水曜日

[SICP] 問題 1.31 : productの定義

a. sum手続きは高階手続きとして書ける, 同様な数多い抽象の最も単純なものに過ぎない.51 与えられた範囲の点での関数値の積を返すproductという似た手続きを書け. productを使って, factorialを定義せよ. また式

π　　２・４・４・６・６・８・・・
−＝−−−−−−−−−−−−−−− 
４　　３・３・５・５・７・７・・・

によってπの近似値を計算するのにproductを使え.
b. 上のproductが再帰的プロセスを生成するなら, 反復的プロセスを生成するものを書け. 反復的プロセスを生成するなら, 再帰的プロセスを生成するものを書け.

与えられた範囲の関数値の積を求める手続きproductを定義します. 和を積に変えているだけなので, sumの定義を利用できます. 手続きは次のようになります.

(require (lib "racket/trace.ss"))

(define (inc x) (+ x 1))

(define (square x) (* x x))

;; p.18のfactorialの定義
(define (factorial-0 n)
  (if (= n 1)
      1
      (* n (factorial-0 (- n 1)))))

;; productの定義. 再帰的プロセス
(define (product-r term a next b)
  (if (> a b)
      1
      (* (term a)
         (product-r term (next a) next b))))

;; productを用いたfactorialの定義
(define (factorial n)
  (product-r identity 1 inc n))

;; 反復的プロセスを生成
(define (product-i term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (* (term a) result))))
  (iter a 1))

;; 円周率を求める. nが大きくなれば精度が良くなる.
(define (my-pi n)
  (define (term x) 
    (/ (* x (+ x 2)) (square (+ x 1))))
  (define (next x)
    (+ x 2))
  (* 4.0 (product-i term 2 next n)))

変更内容は, 「＋」を「＊」に, 初期値を0から1に変えているぐらいです. factorialの定義には再帰的プロセスを生成するproductを使用し, 円周率の計算には反復的プロセスを生成productを使用しています.

また, 円周率を計算する式は, 次のようにカッコをつけると見やすくなります.

π　　２・４　　　４・６　　　６・８
−＝（−−−）・（−−−）・（−−−）・・・
４　　３・３　　　５・５　　　７・７

計算してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (factorial-0 6)
720
> (factorial 6)
720
> (my-pi 10)
3.2751010413348074
> (my-pi 100)
3.1570301764551676
> (my-pi 1000)
3.1431607055322663
> (my-pi 10000)
3.1417497057380523
> (my-pi 100000)
3.1416083612781764
>

実行結果から, 円周率を計算できていそうです.

2014年11月4日火曜日

[筋トレ] 2014.10.27の週

今週の記録です。
10/27（月）74.90kg

　腰痛のため休み

10/28（火）74.70kg

　腰痛のため休み

10/29（水）74.85kg

　腰痛のため休み

10/30（木）74.60kg

　腰痛のため休み

10/31（金）74.65kg

　腰痛のため休み

11/01（土）75.30kg
　スクワット　　　２０、２０　　（5kgの鉄アレイ）
　リアレイズ　　　１０、　０　　（5kgの鉄アレイ）
　レッグレイズ　　１５、１０

11/02（日）75.35kg
　寝過ごしたので休み

腰痛のため、トレーニングはほぼ休みとしました。

週末には腰痛もよくなったので、ぼつぼつと再開します。

2014年11月3日月曜日

自滅する中国（エドワード・ルトワック著、芙蓉書房出版）

自滅する中国（エドワード・ルトワック著、芙蓉書房出版）

タイトルだけを見るとよくある嫌中本のようですが、別物であると考えています。
（よくある嫌中本を読んだことがないので、本当のところは判断できないのですが）

「別物」と判断した理由は、次の２つです。

Ａ．著者の経歴
　解説によると、著者のエドワード・ルトワックは、アメリカ政府・軍事機関で顧問を務めているだけでなく、日本の防衛省防衛研究所をはじめとして、世界中の軍事関係機関で招聘講師を務めている。

Ｂ．インタビューした相手
　第14章で日本について書いてあり、2011年3月にインタビューした相手の名前が書いてあります。安倍晋三、中曽根康弘など、見たことのある名前が挙がっています。また、2014年10月29日の朝刊によると、10月28日に著者が首相官邸を訪れています。

この本の副題は「なぜ世界帝国になれないのか」となっており、中国の戦略的な不味さを説明しています。著者の主張は次のとおりです。

１．中国は自国の行動が他国にどのような影響をあたえるか分かっていない。
　中国に限らず、アメリカやロシアのような大国について言えることです。国が大きくなれば、それに応じて国内問題も増えます。しかし、人間の認識能力は国の大きさに関係ありません。その結果、外交に対する関心が低下します。

２．「中華思想」や「華夷秩序」が染み付いている。
　中国は、黄河流域の文明や文化は最高のものであり、アメリカのような野蛮人もいずれは中国の文化に取り込まれると考えています。これは、漢の時代に匈奴を取り込んだ経験に基づいています。しかし、清の時代、支配者であった女真族は民族の文化を頑なに守り通したことを忘れているようです。このように、他国の文化を見下しているため、他国の理解はより低くなります。

３．「孫子」を生み出した漢民族は戦略的に優れていると勘違いしている。
　「孫子」に代表される兵法書は、春秋戦国時代に生み出されました。この時代は、同じ価値観を持つ同一の文化圏内で、同じ民族が離合集散を繰り返していました。しかし、現代の国際社会は、異なる文化や価値観を持った国家や民族間で利害を争っており、「孫子」が成立したときと条件が異なっています。これを理解せずにそのまま「孫子」を持ち出しても、利益よりも害の方が大きくなります。

　また、過去1000年の歴史を振り返ると、漢民族が中国全土を支配できた期間はわずか200年（？）に過ぎず、このような事実からも戦略的に優れていると判断することは間違いです。

４．中国の軍事力が増大すると周辺国は脅威を感じ、反中国的な行動を取る。
　中国が軍事力を増大させる理由は、国際的な影響力を強めるためることがその一つであると考えられます。しかし、中国の軍事的な圧力が高まると、親中国的な国は中立的な行動を取り、中立的であった国は反中国的な同盟を組むようになります。その結果、中国の影響力は相対的に低下します。

５．周辺国の反発を避ける唯一の道は軍事力の削減である。
　中国が周辺国の反発を受けずに、国際的な影響力を強める唯一の手段は軍事力を削減することです。しかし、歴史的な恨みから中国は国の規模に応じた軍事力を保持する事を望んでおり、また、軍事力を増大させることで利益を得る人たちもいることから、軍事力を削減することはできそうにありません。

６．経済成長をこのまま続け、軍事力で圧倒するしかない。
　中国の経済成長率は年に7%程度あり、アメリカなどを圧倒しています。このペースで経済成長を続け、それに応じて軍事力を増大させれば、中国に立ち向かえる国は無くなります。しかし、反中国的な同盟を組んだ国が中国の経済成長を妨げるような行動を取るため、現在の成長率を維持することは難しくなります。また、中国は多くの国内問題を抱えており、それらが原因で経済成長が止まる可能性があります。経済成長が止まると、中国国内の矛盾が一気に噴出します。その時、中国は持ちこたえられるでしょうか？

この本の約半分のページは、リーマン・ショック以降の中国の行動に対する周辺国（オーストラリア、日本、ベトナム、韓国、モンゴル、インドネシア、フィリピン）の行動を説明しています。ほとんどの国が反中国的な行動を取っており、反中国同盟と呼べるものです。例外は、韓国ぐらいでしょうか。

著者は各国の要人と意見を交換できる立場にありますが、この本に書いてある中国や周辺国の行動は、ニュースなどで確認できるものばかりです。読みやすい本ではありませんが、この本を読むとニュースの見方が変わるかも＼(^o^)／

2014年11月2日日曜日

[SICP] 問題 1.30 : 反復的プロセスを生成する総和

上のsumの手続きは線形再帰を生成する. 総和が反復的に実行出来るように手続きを書き直せる. 次の定義の欠けているところを補ってこれを示せ:

(define (sum term a next b)
  (define (iter a result)
    (if ＜??＞
        ＜??＞
        (iter ＜??＞ ＜??＞)))
  (iter ＜??＞ ＜??＞))

総和を求める手続きが反復的プロセスを生成するように修正します. 内部手続iterの引数resultに計算の途中経過を蓄積するようにします. 手続きの定義は次のようになります.

(require (lib "racket/trace.ss"))

(define (cube x) (* x x x))

(define (inc x) (+ x 1))

;; 再帰的プロセスを生成
(define (sum-r term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum-r term (next a) next b))))

;; 反復的プロセスを生成
(define (sum-i term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ (term a) result))))
  (trace iter) ;; 内部手続きをトレースする.
  (iter a 0))

(trace sum-r)

実行結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (sum-r identity 1 inc 10)
>(sum-r #<procedure:identity> 1 #<procedure:inc> 10)
> (sum-r #<procedure:identity> 2 #<procedure:inc> 10)
> >(sum-r #<procedure:identity> 3 #<procedure:inc> 10)
> > (sum-r #<procedure:identity> 4 #<procedure:inc> 10)
> > >(sum-r #<procedure:identity> 5 #<procedure:inc> 10)
> > > (sum-r #<procedure:identity> 6 #<procedure:inc> 10)
> > > >(sum-r #<procedure:identity> 7 #<procedure:inc> 10)
> > > > (sum-r #<procedure:identity> 8 #<procedure:inc> 10)
> > > > >(sum-r #<procedure:identity> 9 #<procedure:inc> 10)
> > > > > (sum-r #<procedure:identity> 10 #<procedure:inc> 10)
> > > >[10] (sum-r #<procedure:identity> 11 #<procedure:inc> 10)
< < < <[10] 0
< < < < < 10
< < < < <19
< < < < 27
< < < <34
< < < 40
< < <45
< < 49
< <52
< 54
<55
55
> (sum identity 1 inc 10)
>(iter 1 0)
>(iter 2 1)
>(iter 3 3)
>(iter 4 6)
>(iter 5 10)
>(iter 6 15)
>(iter 7 21)
>(iter 8 28)
>(iter 9 36)
>(iter 10 45)
>(iter 11 55)
<55
55
>

トレースの結果からも反復的プロセスを生成していることが分かります.

2014年11月1日土曜日

ダメな４星人

先日、会社で中小企業診断士の先生による研修を受けました。その中で、コンサルタントとして上手くいかない人の特徴を「ダメな４星人」と名づけて紹介していました。次の４星人です。

ダメダメ星人
デモデモ星人
クレクレ星人
グルグル星人

もう少し詳しく書きます。

１．ダメダメ星人
　人の話を聴いた時に、とりあえず否定するところから入る人です。もちろん、ダメなものはダメと言わないといけないのですが、言った方としては否定され続けると意見する気が無くなります。その結果、ダメダメ星人には情報が集まらなくなるので、コンサルタントとしてやっていくのは難しそうです。

２．デモデモ星人
　プラカードを持って抗議活動をする人ではありません。何をするにしても、「でもでも」と、できない理由を探す人です。もちろん、何かを始めるときには、最悪の場合に備えて計画を立てるべきですが、実行すると決めたのなら最善を尽くすべきです。

３．クレクレ星人
　仕事をまわして欲しいと、それだけを人に依頼する人です。そもそも、仕事がなく、暇そうにしているコンサルタントは、仕事ができなさそうに見えるので仕事を依頼したいと思いません。「くれくれ」と言うのは逆効果でしょう。世の中、ギブ・アンド・テイクといいます。まず、与えること、相手の利益を考えることを考えるぐらいで、ちょうど良いのでしょう。

４．グルグル星人
　ちょっと分かり難いのですが、思考がグルグルと同じことを回っている人です。何か新しく始めようとして計画を立てても、実行の段階で、ああでもない、こうでもない、と考えて行動に移さない人です。私もよくあります。少しずつでも行動を起こして、前に進めていかないと、何も変わりません。

この４星人にならないようにしなくては(~_~;)

2014年10月31日金曜日

[SICP] 問題 1.29 : Simpsonの公式

Simpsonの公式は上に示したのより更に正確な数値積分法である.
Simpsonの公式を使えば, aからbまでの関数fの積分は, 偶整数nに対し, h = (b - a)/nまたy_k = f(a + kh)として

(h/3)[y₀ + 4y₁ + 2y₂ + 4y₃ + 2y₄ + ・・・ + 2y_n-2 + 4y_n-1 + y_n]

で近似出来る. (nの増加は近似の精度を増加する.)
引数としてf, a, bとnをとり, Simpson公式を使って計算した積分値を返す手続きを定義せよ. その手続きを使って(n = 100とn = 1000で)0から1までcubeを積分し, またその結果を上のintegral手続きの結果と比較せよ.

Simpsonの公式の大カッコの中身をじっと見つめると, 次のようなパターンが見えてきます.

(y₀ + 4y₁ + y₂) + (y₂ + 4y₃ + y₄) + ・・・ + (y_n-4 + 4y_n-3 + y_n-2) + (y_n-2 + 4y_n-1 + y_n)

y₂に注目してください. 公式では係数が2となっていますが, それを2つに分けています.

つまり, 大カッコの中は３つの項をひとまとめにするとスッキリと書けます. 手続きを定義します.

(require (lib "racket/trace.ss"))

(define (cube x) (* x x x))

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx))

(define (simpson f a b n)
  (define h (/ (- b a) n))
  (define (y k) (f (+ a (* k h))))
  (define (term k) (+ (y k) (* 4.0 (y (+ k 1))) (y (+ k 2))))
  (define (next k) (+ k 2))
  (* (/ h 3.0)
     (sum term 0 next (- n 2))))

0から1までのcubeを積分してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (integral cube 0 1 0.01)
0.24998750000000042
> (integral cube 0 1 0.001)
0.249999875000001
> (simpson cube 0 1 100)
0.2500000000000001
> (simpson cube 0 1 1000)
0.2500000000000001
>

計算結果を見ると精度が全く異なっています.

2014年10月30日木曜日

[SICP] 問題 1.17 : 対数的ステップ数の乗算手続き（再帰的プロセス）

本節のべき乗アルゴリズムは, 乗算の繰返しによるべき乗の実行に基づいていた. 同様に整数の乗算を加算の繰返しで実行出来る. 次の乗算手続きは(この言語には加算はあるが, 乗算はないと仮定する)expt手続きに似たものである:

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

このアルゴリズムはbに線形のステップ数をとる. 加算の他に整数を二倍するdouble演算と(偶数の)整数を2で割るhalve演算もあるとしよう. これらを使い, fast-exptと類似の対数的ステップ数の乗算手続きを設計せよ.

p.25のfast-exptを参考に手続きを定義します.

(require (lib "racket/trace.ss"))

(define (double x) (* x 2))

(define (halve x) (/ x 2))

(define (fast-mult a b)
  (cond ((< b 0) (* -1 (fast-mult a (abs b))))
        ((= b 0) 0)
        ((= b 1) a)
        ((even? b) (double (fast-mult a (halve b))))
        (else (+ a (fast-mult a (- b 1))))))

(trace fast-mult)

fast-exptと同じような構造をしています. 負の数をかけた場合と０をかけた場合の扱いを追加しています.

a×bの計算について, 奇数と偶数の場合に分けて, 計算をどのように進めるかを考えます.

1) bが奇数の場合, b = m+1とする. 次の式が成立する.

a×(m+1) = a + (a×m)

2) nが偶数の場合, b = 2mとする. 次の式が成立する.

a×(2m) = double(a×m)

実行結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fast-mult 3 45)
>(fast-mult 3 45)
> (fast-mult 3 44)
> >(fast-mult 3 22)
> > (fast-mult 3 11)
> > >(fast-mult 3 10)
> > > (fast-mult 3 5)
> > > >(fast-mult 3 4)
> > > > (fast-mult 3 2)
> > > > >(fast-mult 3 1)
< < < < <3
< < < < 6
< < < <12
< < < 15
< < <30
< < 33
< <66
< 132
<135
135
> (fast-mult 4 0)
>(fast-mult 4 0)
<0
0
> (fast-mult 5 -8)
>(fast-mult 5 -8)
> (fast-mult 5 8)
> >(fast-mult 5 4)
> > (fast-mult 5 2)
> > >(fast-mult 5 1)
< < <5
< < 10
< <20
< 40
<-40
-40
>

トレースの結果から、対数的ステップ数で計算していることが分かります.

2014年10月29日水曜日

[SICP] 問題 1.16 : べき乗を求める反復的アルゴリズム

fast-exptのように, 逐次平方を使い, 対数的ステップ数の反復的べき乗プロセスを生成する手続きを設計せよ.

(ヒント: (b^n/2)² = (b²)^n/2に注意し, 指数nと底bの他にもう一つの状態変数aを用意する.
状態の移変りで積abⁿが不変であるように状態遷移を定義する.
プロセス開始時にaを1とし, プロセス終了時にaが結果になるようにする.
一般に, 状態の移変りに不変のままの不変量(invariant quantity)を定義する技法は, 反復的アルゴリズムの設計に有用である.)

問題文のヒントを参考に手続きを定義します.

(require (lib "racket/trace.ss"))

(define (square x) (* x x))

(define (fast-expt-iter b n p)
  (cond ((= n 0) p)
        ((even? n) (fast-expt-iter (square b) (/ n 2) p))
        (else (fast-expt-iter b (- n 1) (* b p)))))

(define (fast-expt b n)
  (fast-expt-iter b n 1))

(trace fast-expt-iter)

p×bⁿを考え, pに結果をため込むようにします. 奇数と偶数の場合に分けて, pとbがどのように変化するかを考えます.

1) nが奇数の場合, n = m+1とする. 次の式が成立する.

p×b^m+1 = (p×b)×b^m

右辺のカッコ内の(p×b)が次のステップのpとなる.

2) nが偶数の場合, n = 2mとする. 次の式が成立する.

p×b^2m = p×(b²)^m

右辺のカッコ内の(b²)が次のステップのbとなる.

実行結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (fast-expt 2 8)
>(fast-expt-iter 2 8 1)
>(fast-expt-iter 4 4 1)
>(fast-expt-iter 16 2 1)
>(fast-expt-iter 256 1 1)
>(fast-expt-iter 256 0 256)
<256
256
>

トレースの結果から, 反復的プロセスを生成しており, 対数的ステップ数で計算していることが分かります.

2014年10月28日火曜日

[SICP] 問題 1.15 : 正弦の計算

(ラジアンで表す)角度の正弦は, xが十分小さい時, sin x ≒ xの近似と, 正弦の引数の値を小さくするための三角関係式

sin(x) = 3sin(x/3) - 4sin3(x/3)

を使って計算出来る. (この問題のためには, 角度の大きさが0.1ラジアンより大きくなければ「十分小さい」と考える.) この方法は次の手続きに採用してある:

(define (cube x) (* x x x))

(define (p x) (- (* 3 x) (* 4 (cube x))))

(define (sine angle)
   (if (not (> (abs angle) 0.1))
       angle
       (p (sine (/ angle 3.0)))))

a. (sine 12.15)の評価で, 手続きpは何回作用させられたか.

b. (sine a)の評価で, 手続きsineの生成するプロセスが使うスペースとステップ数の増加の程度は(aの関数として)何か.

問題文の手続きを定義します. 手続きpを作用させた回数を調べるためにトレースを使います.

(require (lib "racket/trace.ss"))

(define (cube x) (* x x x))

(define (p x) (- (* 3 x) (* 4 (cube x))))

(define (sine angle)
  (if (not (> (abs angle) 0.1))
      angle
      (p (sine (/ angle 3.0)))))

(trace p)

計算結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (sin 12.5)
-0.06632189735120068
> (sine 12.5)
>(p 0.051440329218107005)
<0.153776521096694
>(p 0.153776521096694)
<0.4467840153484446
>(p 0.4467840153484446)
<0.9836111719853284
>(p 0.9836111719853284)
<-0.8557060643295382
>(p -0.8557060643295382)
<-0.060813768577286265
-0.060813768577286265
>

トレースの結果から, pを作用させた回数は５回です.

手続きの定義から, aの値が0.1より大きい時は手続きを再帰的に呼び出し, 次のaの値は1/3になっています. 「十分小さい」と判断する値をe, ステップ数をnとすると次の関係が成り立ちます.

(a/3)ⁿ	<	e
a/e	<	3ⁿ
log₃(a/e)	<	n

このことから, ステップ数の増加の程度はlog aであるといえます. また, 手続きは末尾再帰になっていないため, スペースの増加の程度もステップの増加の程度と同じです.

2014年10月27日月曜日

[筋トレ] 2014.10.20の週

今週の記録です。

10/21（火）74.05kg
　スクワット　　　２０、２０　　（5kgの鉄アレイ）
　リアレイズ　　　１５、　８　　（5kgの鉄アレイ）
　レッグレイズ　　１０、　７

10/22（水）73.85kg
　プッシュアップ　１７、　７　　（膝をついた状態）
　ナロースタンス　　０　　　　　（両手の間を拳一つ開けた状態）
　アームカール　　　６、　４　　（10kgのダンベル）

10/24（金）75.40kg
　スクワット　　　２０、２０　　（5kgの鉄アレイ）
　リアレイズ　　　１２、　７　　（5kgの鉄アレイ）
　レッグレイズ　　１３、　５

10/26（日）75.65kg
　プッシュアップ　１６、　４　　（膝をついた状態）
　ナロースタンス　　２、　３　　（両手の間を拳一つ開けた状態）
　アームカール　　　６、　４　　（10kgのダンベル）

スクワットとアームカールに使うウエイトを増やしました。スクワットは20回できてしまうので、ウエイトを増やしても良さそうです。

リアレイズについては、正しいフォームを意識したため、回数が減っています。数をこなせば良いというものではないはずです。

トレーニングは、朝にしており、体重は夜、風呂を上がった後で量っています。金曜日は飲み会だったので、体重は多めです。

更に、土日の夕食がおでんだったので、体重は増える一方です(~_~;)

2014年10月26日日曜日

[SICP] 問題 1.14 : 両替の計算が生成するプロセス

1.2.2節のcount-change手続きが11セントの両替の場合に生成するプロセスを示す木構造を描け. 両替の金額の増加につれ, このプロセスが使うスペースとステップ数の増加の程度は何か.

図を書きます. 木の節点に金額と両替に使えるコインを括弧付きで描いています.

 11 -----------------  -39
(50, 25, 10, 5, 1)     (50, 25, 10, 5, 1)
  |
  |
 11 -----------------  -14
(25, 10, 5, 1)         (25, 10, 5, 1)
  |
  |
 11 --------- 1 ------  -9
(10, 5, 1)  (10, 5, 1) (10, 5, 1)
  |           |
  |           |
  |           1 ------  -4
  |          (5, 1)     (5, 1)
  |           |
  |           |
  |           1  ------  0
  |          (1)        (1)
  |
 11 --------  6 -------  1 ----  -4
 (5, 1)      (5, 1)     (5, 1)   (5, 1)
  |           |          |
  |           |          |
  |           |          1 -----  0
  |           |         (1)      (1)
  |           |          |
  |           |          |
  |           |          1
  |           |         ( )
  |           |
  |           6 -- 5 -- 4 -- 3 -- 2 -- 1 -- 0
  |          (1)  (1)  (1)  (1)  (1)  (1)  (1)
  |           |    |    |    |    |    |
  |           |    |    |    |    |    |
  |           6    5    4    3    2    1
  |          ( )  ( )  ( )  ( )  ( )  ( )
  | 
 11 -- 10 -- 9 -- 8 -- 7 -- 6 -- 5 -- 4 -- 3 -- 2 -- 1 -- 0
 (1)   (1)  (1)  (1)  (1)  (1)  (1)  (1)  (1)  (1)  (1)  (1)
  |     |    |    |    |    |    |    |    |    |    |
  |     |    |    |    |    |    |    |    |    |    |
 11    10    9    8    7    6    5    4    3    2    1
 ( )   ( )  ( )  ( )  ( )  ( )  ( )  ( )  ( )  ( )  ( )

このプロセスが使うスペースとステップ数の増加の程度については後で考えます.

2014年10月25日土曜日

[SICP] 問題 1.13 : フィボナッチ数を求める代数方程式

Φ= (1+√5)/2としてFib(n)がΦⁿ/√5に最も近い整数であることを証明せよ. ヒント: Ψ= (1-√5)/2とする. 帰納法とFibonacci数の定義(1.2.2節参照)を用い, Fib(n)=(Φⁿ-Ψⁿ)/√5を証明せよ.

まず, Fib(n)=(Φⁿ-Ψⁿ)/√5を証明する.

(1) n=1のとき

Fib(1)	=	{Φ¹-Ψ¹} / √5
	=	{(1+√5)/2 - (1-√5)/2} / √5
	=	2√5 / √5
	=	1

(2) n=2のとき

Φ²	=	{(1+√5)/2}²
	=	{1 + 2√5 + 5} / 4
	=	{2 + 2√5 + 4} / 4
	=	{1 + √5} / 2 + 1
	=	Φ + 1

Ψ²	=	{(1-√5)/2}²
	=	{1 - 2√5 + 5} / 4
	=	{2 - 2√5 + 4} / 4
	=	{1 - √5} / 2 + 1
	=	Ψ + 1

Fib(2)	=	{Φ²-Ψ²} / √5
	=	{(Φ + 1) - (Ψ + 1)} / √5
	=	{Φ - Ψ} / √5
	=	1

(3) n=k, k+1のときFib(n)=(Φⁿ-Ψⁿ)/√5が成立すると仮定する. n=k+2のとき

Fib(k+2)	=	Fib(k+1) + Fib(k)
	=	(Φ^k+1-Ψ^k+1)/√5 + (Φ^k-Ψ^k)/√5
	=	{(Φ^k+1+Φ^k) - (Ψ^k+1+Ψ^k)} / √5
	=	{Φ^k(Φ+1) - Ψ^k(Ψ+1)} / √5
	=	{Φ^kΦ² - Ψ^kΨ²} / √5
	=	{Φ^k+2 - Ψ^k+2} / √5

(4) 以上より, 1以上の整数nについて, Fib(n)=(Φⁿ-Ψⁿ)/√5が成立する.

次に, Ψ/√5の値を計算する.

Ψ/√5 = (1-√5)/2 ≒ -0.2764

Ψ/√5 < 1/2 であるから, 1以上の整数nについて, Ψⁿ/√5 < 1/2 である.
よって、Fib(n)がΦⁿ/√5に最も近い整数であるといえる.

2014年10月24日金曜日

[SICP] 問題 1.12 : Pascal三角形

次の数のパターンをPascal三角形(Pascal's triangle)という.

三角形の辺上の数はすべて1, 三角形の内部の数はその上の二つの数の和である. 再帰的プロセスの方法でPascal三角形の要素を計算する手続きを書け.

Pascal三角形を計算する手続きを定義します. 結果の確認を容易にするための手続きも定義します.

(define (pascal x y)
  (cond ((= x 0) 1)
        ((= y 0) 1)
        ((= x y) 1)
        (else (+ (pascal (- x 1) (- y 1))
                 (pascal (- x 1) y)))))

;; 1からnまでの整数のリストを求める.
(define (int-list n)
  (define (loop result counter)
    (if (< counter 0)
        result
        (loop (cons counter result) (- counter 1))))
  (loop '() n))

;; 9行分のPascal三角形を求める.
(map (lambda (x)
       (map (lambda (y) (pascal x y)) (int-list x)))
     (int-list 8))

実行した結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
((1)
 (1 1)
 (1 2 1)
 (1 3 3 1)
 (1 4 6 4 1)
 (1 5 10 10 5 1)
 (1 6 15 20 15 6 1)
 (1 7 21 35 35 21 7 1)
 (1 8 28 56 70 56 28 8 1))
>

Pascal三角形を計算できていることを確認できます.

2014年10月23日木曜日

[SICP] 問題 1.11 : f(n)=f(n-1)+2f(n-2)+3f(n-3)

n<3に対して

  f(n)=n, n ≥ 3に対してf(n)=f(n - 1) + 2f(n - 2) + 3f(n - 3)

なる規則で定義する関数fがある. 再帰的プロセスの方法でfを計算する手続きを書け. 反復的プロセスの方法でfを計算する手続きを書け.

Fibonacci数を計算する手続きを参考にして問題文の関数fを定義します.

(require (lib "racket/trace.ss"))

(define (f-r n)
  (if (< n 3)
      n
      (+ (* 1 (f-r (- n 1)))
         (* 2 (f-r (- n 2)))
         (* 3 (f-r (- n 3))))))

(define (f-iter counter x y z)
  (if (= 0 counter)
      z
      (f-iter (- counter 1)
              (+ x (* 2 y) (* 3 z))
              x 
              y)))

(define (f-i n)
  (f-iter n 2 1 0))

;;(trace f-r f-iter)

実行して, 結果を確認します.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (map f-r '(0 1 2 3 4 5 6 7))
(0 1 2 4 11 25 59 142)
> (map f-i '(0 1 2 3 4 5 6 7))
(0 1 2 4 11 25 59 142)
>

手続きf-rとf-iterをトレースして, 手続きが生成するプロセスを確認します.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (f-r 5)
>(f-r 5)
> (f-r 4)
> >(f-r 3)
> > (f-r 2)
< < 2
> > (f-r 1)
< < 1
> > (f-r 0)
< < 0
< <4
> >(f-r 2)
< <2
> >(f-r 1)
< <1
< 11
> (f-r 3)
> >(f-r 2)
< <2
> >(f-r 1)
< <1
> >(f-r 0)
< <0
< 4
> (f-r 2)
< 2
<25
25
> (f-i 5)
>(f-iter 5 2 1 0)
>(f-iter 4 4 2 1)
>(f-iter 3 11 4 2)
>(f-iter 2 25 11 4)
>(f-iter 1 59 25 11)
>(f-iter 0 142 59 25)
<25
25
>

トレースの結果から, f-rが再帰的プロセスを生成し, f-iが反復的プロセスを生成していることが分かります.

2014年10月22日水曜日

[SICP] 問題 1.10 : Ackermann関数

次の手続きはAckermann関数という数学関数を計算する.

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

次の式の値は何か.

(A 1 10)

(A 2 4)

(A 3 3)

Aを上で定義した手続きとして, 次の手続きを考える.

(define (f n) (A 0 n))

(define (g n) (A 1 n))

(define (h n) (A 2 n))

(define (k n) (* 5 n n))

正の整数nに対して手続きf, gおよびhが計算する関数の簡潔な数学的定義を述べよ. 例えば(k n)は5n²を計算する.

Ackermann関数を定義します.

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

問題文の例を計算してみます.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (A 1 10)
1024
> (A 2 4)
65536
> (A 3 3)
65536
>

次の手続きf, g, hが計算する関数の簡潔な数学的定義を考えます. まず, 手続きを定義します.

(define (f n) (A 0 n))

(define (g n) (A 1 n))

(define (h n) (A 2 n))

手続きを使っていくつかの例を計算して結果を観察します. 見通しを良くするために, ２章で扱う手続きを使ってズルをします.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (map f '(1 2 3 4 5 6 7 8))
(2 4 6 8 10 12 14 16)
> (map g '(1 2 3 4 5 6 7 8))
(2 4 8 16 32 64 128 256)
> (map h '(1 2 3 4))
(2 4 16 65536)
>

計算結果とAckermann関数の定義から, 次のような関係がありそうです.

関数の表記を一般的な表記で書きます.

  f(n) = A(0, n) 
       = 2 * n

Ackermann関数の引数xが0の場合に相当するため, 引数yの値を2倍した結果を返します. このことから, f(n)=2nといえます.

Ackermann関数の定義とf(n)の結果から, g(n)は次のように変形できます.

  g(n) = A(1, n)
       = A(0, A(1, (n - 1)))
       = 2 * A(1, (n - 1))
       = 2 * A(0, A(1, (n - 2)))
       = 2 * 2 * A(1, (n - 2))
       = 2 * 2 * ・・・・・ * 2 * A(1, 1)
       = 2 * 2 * ・・・・・ * 2 * 2

この結果から, g(n)は2をn回掛けています. このことから, g(n)=2ⁿといえます.

Ackermann関数の定義とg(n)の結果から, h(n)は次のように変形できます. ここでは, 2ⁿを2^nと記述しています.

  h(n) = A(2, n)
       = A(1, A(2, (n - 1)))
       = 2 ^ A(2, (n - 1))
       = 2 ^ A(1, A(2, (n - 2)))
       = 2 ^ 2 - A(1, (n - 2))
       = 2 ^ 2 ^ ・・・・・ ^ 2 ^ A(2, 1)
       = 2 ^ 2 ^ ・・・・・ ^ 2 ^ 2

この結果から, h(n)は2の2乗の2乗の・・・・をn回繰り返したものです. 例えば, h(5)は上で求めたh(4)の結果を使うと次のようになります.

  h(5) = A(2, 5)
       = A(1, 65536)
       = 2 ^ 65536

つまり, 2⁶⁵⁵³⁶を計算することになります. 実際に計算してみた結果は次のとおりです.

ようこそ DrRacket, バージョン 6.1 [3m].
言語: Pretty Big; memory limit: 2048 MB.
> (A 2 5)
2003529930406846464979072351560255750447825475569751419265016973710894
0595563114530895061308809333481010382343429072631818229493821188126688
6950636476154702916504187191635158796634721944293092798208430910485599
0570159318959639524863372367203002916969592156108764948889254090805911
4570376752085002066715637023661263597471448071117748158809141357427209
6719015183628256061809145885269982614142503012339110827360384376787644
9043205960379124490905707560314035076162562476031863793126484703743782
9549756137709816046144133086921181024859591523801953310302921628001605
6867010565164675056803874152946384224484529253736144253361437372908830
3794601274724958414864915930647252015155693922628180691650796381064132
2753072671439981585088112926289011342377827055674210800700652839633221
5507783121428855167555407334510721311242739956298271976915005488390522
3804357045848197956393157853510018992000024141963706813559840464039472
1940160695176901561197269823378900176415171900511334663068981402193834
8143542638730653955296969138802415816185956110064036211979610185953480
2787167200122604642492385111393400464351623867567078745259464670903886
5477434832178970127644555294090920219595857516229733335761595523948852
9757995402847194352991354376370598692891375715374000198639433246489005
2543106629669165243419174691389632476560289415199775477703138064781342
3095961909606545913008901888875880847336259560654448885014473357060588
1709016210849971452956834406197969056546981363116205357936979140323632
8496233046421066136200220175787851857409162050489711781820400187282939
9434461862243280098373237649318147898481194527130074402207656809103762
0399920349202390662626449190916798546151577883906039772075927937885224
1294301017458086862263369284725851403039615558564330385450688652213114
8136384083847782637904596071868767285097634712719888906804782432303947
1865052566097815072986114143030581692792497140916105941718535227588750
4477592218301158780701975535722241400019548102005661773589781499532325
2085897534635470077866904064290167638081617405504051176700936732028045
4933902799249186730653993164072049223847481528061916690093380573212081
6350707634351669869625020969023162859350071874190579161241536897514808
2619048479465717366010058924766554458408383347905441448176842553272073
1558634934760513741977952519036503219802010876473836868253102518337753
3908861426184800374008082238104076468878471647552945326947661700424461
0633112380211345886945322001165640763270230742924260515828110703870183
4532456763562595143003203743274078087905628366340696503084422585596703
9271869461158513793386475699748568670079823960604393478850861649260304
9450617434123658283521448067266768418070837548622114082365798029612000
2744132443843240233125740354501935242877643088023285085588608996277445
8164680857875115807014743763867976955049991643998284357290415378143438
8473034842619033888414940313661398542576355771053355802066221855770600
8255128889333222643628198483861323957067619140963853383237434375883085
9233722284644287996245605476932428998432652677378373173288063210753211
2386806046747084280511664887090847702912081611049125555983223662448685
5665140268464120969498259056551921618810434122683899628307165486852553
6914850299539675503954938371853405900096187489473992880432496373165753
8036735867101757839948184717984982469480605320819960661834340124760966
3951977802144119975254670408060849934417825628509272652370989865153946
2193004607364507926212975917698293892367015170992091531567814439791248
4757062378046000099182933213068805700465914583872080880168874458355579
2625846512476308714856631352893416611749061752667149267217612833084527
3936469244582892571388877839056300482483799839692029222215486145902373
4782226825216399574408017271441461795592261750838890200741699262383002
8228624928418267124340575142418856999427233160699871298688277182061721
4453142574944015066139463169197629181506579745526236191224848063890033
6690743659892263495641146655030629659601997206362026035219177767406687
7746354937531889958786628212546979710206574723272137291814466665942187
2003474508942830911535189271114287108376159222380276605327823351661555
1493693757784666701457179719012271178127804502400263847587883393968179
6295069079881712169068692953824852983002347606845411417813911064856023
6549754227497231007615131870024053910510913817843721791422528587432098
5249578780346837033378184214440171386881242499844186181292711985333153
8256732187042153063119774853521467095533462633661086466733229240987984
9256691109516143618601548909740241913509623043612196128165950518666022
0307156136847323646608689050142639139065150639081993788523183650598972
9912540447944342516677429965981184923315155527288327402835268844240875
2811283289980625912673699546247341543333500147231430612750390307397135
2520693381738433229507010490618675394331307847980156551303847581556852
3621801041965025559618193498631591323303609646190599023611268119602344
1843363334594927631946101716652913823717182394299216272538461776065694
5422978770713831988170369645886898118632109769003557358846244648357062
9145305275710127887202796536447972402540544813274839179412882642383517
1949197209797145936887537198729130831738033911016128547415377377715951
7280841116275971863849242228023734419254699919836721921312870355853079
6694271341639103388275431861364349010094319740904733101447629986172542
4423355612237435715825933382804986243892498222780715951762757847109475
1190334822414120251826887137281931042534781961284401764795315050571107
2297431456991522345164312184865757578652819756484350895838472292353455
9464521215831657751471298708225909292655638836651120681943836904116252
6687100445602437042006637090019411855571604720446436969328500600469281
4050711906926139399390273553454556747031490388602202463994826050176243
1969305640666366626090207048887438898907498152865444381862917382901051
8208699363826618683039152732645812867828066013375000965933646251460917
2318031293034787742123467911845479131110989779464821692250562939995679
3483801699157439700537542134485874586856047286751065423341893839099110
5864655951136460610551568385412174598018071331636125730796111683438637
6766730735458349478978831633012924080083635682593915711313097803051644
1716682518346573675934198084958947940983292500086389778563494693212473
4261030627137450772861569225966285738579055332406418490184513282846327
0926975383086730840914224765947443997334813081098639941737978965701068
7026734161967196591599588537834822988270125605842365589539690306474965
5841479813109971575420432563957760704851008815782914082507777385597901
2912940730946278594450585941227319481275322515232480150346651904822896
1406646890305102510916237770448486230229488966711380555607956620732449
3733740278367673002030116152270089218435156521213792157482068593569207
9021450227713309998772945959695281704458218195608096581170279806266989
1205061560742325686842271306295009864421853470810407128917646906550836
1299166947780238225027896678434891994096573617045867862425540069425166
9397929262471452494540885842272615375526007190433632919637577750217600
5195800693847635789586878489536872122898557806826518192703632099480155
8744555751753127364714212955364940843855866152080121150790750685533444
8925869328385965301327204697069457154695935365857178889486233329246520
2735853188533370948455403336565356988172582528918056635488363743793348
4118455801683318276768346462919956055134700391478768086403226296166415
6066750815371064672310846196424753749055374480531822600271021640098058
4497526023035640038083472053149941172965736785066421400842696497103241
9191821212132069397691439233683747092282677387081322366800869247034915
8684099115309831541206356612318750430546753698323082796645741762080659
3177265685841681837966106144963432544111706941700222657817358351259821
0807691019610522292638797450490192543119006205619065774524161919131875
3398404934397682331029846589331837301580959252282920682086223033258528
0119266496314441316442773003237792274712330696417149945532261035475145
6312906688543454268697884477429817774937101176146516241836166802548152
9633530849084994300676365480610294009469375060984558855804397048591444
9584445079978497045583550685408745163316464118083123079704389849190506
5875864258107384224205911919416741824904527002882639830579500573417114
8703118714283418449915345670291528010448514517605530697144176136858238
4102787659324662689978418319620312262421177391477208004883578333569204
5339359532545648970285585897355057512351295365405028420810227852487766
0357424636667314868027948605244578267362623085297826505711462484659591
4210278122788941448163994973881884622768244851622051817076722169863265
7016543169197426512300417573299044735376725368457927543654128265535818
5804684006936771860502007054724754840080553042495185449526724726134731
8174742180078574693465447136036975884118029408039616746946288540679172
1386012254195038197045384172680063988206563287928395827085109199588394
4829777564715202613287108952616341770715164289948795356485455355314875
4978134009964854498635824847690590033116961303766127923464323129706628
4113074270462020320133683503854253603136367635752126047074253112092334
0283748294945310472741896928727557202761527226828337674139342565265328
3068469997597097750005560889932685025049212884068274139881631540456490
3507758716800740556857240217586854390532281337707074158307562696283169
5568742406052772648585305061135638485196591896864959633556821697543762
1430778665934730450164822432964891270709898076676625671517269062058815
5496663825738292741820822789606844882229833948166709840390242835143068
1376725346012600726926296946867275079434619043999661897961192875051944
2356402644303271737341591281496056168353988188569484045342311424613559
9252723300648816274667235237512343118934421188850850793581638489944875
4475633168921386967557430273795378526254232902488104718193903722066689
4702204258836895840939998453560948869946833852579675161882159410981624
9187418133647269651239806775619479125579574464714278686240537505761042
0426714936608498023827468057598259133100691994190465190653117190892607
7949119217946407355129633864523035673345588033313197080365457184791550
4326548995597058628882868666066180218822486021449999731221641381706534
8017551043840662441282280361664890425737764095632648282525840766904560
8439490325290526337532316509087681336614242398309530806549661879381949
1200339194894940651323988166420800883955549422370967348400726427057011
6508907519615537018626479745638118785617545711340047381076276301495330
9735174180655479112660938034311378532532883533352024934365979129341284
8549709468263290758301930726653377825593143311109638480539408592839889
0779621047984791968687653998747709591278872747587443980677982496827827
2200926449944559380414608770641941810440758269805688038949654616587983
9046605876453418102899071942930217745199761044950431968415034555140448
2092893337865736305283061999007774872692299860827905317169187657886090
8941817057993404890218441559791092676862796597583952483926734883634745
6516870161662406424242412289611180106156823425393921800524834547237792
1991122859591419187749179382334001007812832650671028178139602912091472
0100947878752551263372884222353869490067927664511634758101193875319657
2421214760382847747745717045786104173857479113019085838778901523343430
1300528279703858035981518292960030568261209195094373732545417105638388
7047528950563961029843641360935641632589408137981511693338619797339821
6707610046079800960160248230969430438069566201232136501405495862506152
8258803302290838581247846931572032323360189946943764772672187937682643
1828382603564520699468630216048874528424363593558622333506235945002890
5585816112753417837504559361261308526408280512138731774902002495527387
3458595640516083058305377073253397155262044470542957353836111367752316
9972740292941674204423248113875075631319078272188864053374694213842169
9288629404796353051505607881263662064972312575790195988730411956262273
4372890051656111109411174527796548279047125058199907749806382155937688
5546498822938985408291325129076478386322494781016753491693489288104203
0156102833861438273781609463413353835783407653143214171506558775478202
5245478065730134227747061674424196895261316427410469547462148375628829
9771804186785084546965619150908695874251184435837306590951460980451247
4094113738999278224929833677960110153870961297497055663016373072027507
3475992294379239382442742118615823616131788639255309511718842129850830
7238259729144142251579403883011359083331651858234967221259621812507058
1137594955250227472746743698871319266707692991990844671612287388584575
8462272657333075373557282395161696417519867501268174542932373829414382
4814377139861906716657572945807804820559511881687188075212971832636442
1553367877512747669407901170575098195750845635652173895441798750745238
5445520013357203333237989507439390531291821225525983379090946363020218
5353848854825062897715616963860712382771725621313460549401770413581731
9317633701363322528191275471914434509207118488383668181742633429496118
7009150304916533946476371776643912079834749462739782217150209067019030
2469762151278521956142070806461631373236517853976292092025500288962012
9701413796400380557349492690735351459612086747965477336929587736286356
6014376796403843079686413856344780132826128458918489852804804884418082
1639423974014362903481665458114454366460032490618763039502356402044530
7482102413668951966442213392007574791286838051751506346625693919377402
8351207566626082989049187728783385217852279204577184696585527879044756
2192663992008409302075673925363735628390829817577902153202106409617373
2835984940666521411981838108845154597728951645721318977979074919410131
4836854463961690460703010759681893374121757598816512700076126278916951
0406315857637534787420070222051070891257612361658026806815858499852631
4658780866168007332646768302063916972030648944056281954061906852420030
5346315662189132730906968735318164109451428803660599522024824888671155
4429104721929134248346438705368508648749099178812670565665387191049721
8200423714927401644609434598453925367061322106165330856620211889682340
0575267548610147699368873820958455221157192347968688816085363161586288
0150395949418529489227074410828207169303387818084936204018255222271010
9856534448172074707560192459155994310729495781978785905789400525401228
6751714251118435643718405356302418122547326609330271039796809106493927
2722683035410467632591355279683837705019855234621222858410557119921731
7179698043393177077507556270560478317798444476375602546370333692471142
2081551997369137197516324130274871219986340454824852457011855334267526
4715978310731245663429805221455494156252724028915333354349341217862037
0072603152798707718724912344944771479095207347613854254853115527733010
3034247683586549609372232400715451812973269208105842409055772564580368
1462234493189708138897143299831347617799679712453782310703739151473878
6921191875667003193212818968033226965944592862106074388274169194651622
6763254066507088107103039417886056489376981673415902592519461182364294
5652669372203155504700213598846292758012527715422016629954863130324912
3110296279237238997664168034971412265279319076363261368141455163766565
5983978848938173308266877990196288693229659737995193162118721545528739
4170243669885593888793316744533363119541518404088283815193421234122820
0309503133410507047601599879854725291906652224793197154403317948368373
7322082188577334162385644138070054191353024594391350255453188645479625
2260251762928374330465102361057583514550739443339610216229675461415781
1271970017386114942795014112532806212547758105129720884652631580948066
3368767014731073354071771087661593585681409821296773075919738297344144
5256688770855324570888958320993823432102718224114763732791357568615421
2528496579033350931527769255058456440105521926445053120737562877449981
6364633283581614033017581396735942732769044892036188038675495575180689
0058532927201493923500525845146706982628548257883267398735220457228239
2902071448222198855871028969919358730742778151597576207640239512438602
0203259659625021257834995771008562638611823381331850901468657706401067
6278617583772772895892746039403930337271873850536912957126715066896688
4938808851429436099620129667590792250822753138128498515269029317002631
3632894209579757795932763553116206675348865131732387243874806351331451
2644889967589828812925480076425186586490241111127301357197181381602583
1785069322440079986566353715440884548663931817083957357807990597308390
9488180406093595919090747396090441015051632174968141210076571917748376
7355751000733616922386537429079457803200042337452807566153042929014495
7806296341383835517835997647088513490048569736979652386958459945955920
9070905895689145114141268450546211794502661175016692826025095077077821
1950432617383223562437601776799362796099368975191394965033358507155418
4364568526166742436889203710374953284259271316105378349807407391586338
1796765842525803673720646935124865223848134166380806150570482905989069
6451936440018597120425723007316410009916987524260377362177763430621616
7448849308109299010095179745415642512048220867145868492551324442667771
2786372821133153622430109182439124338021404624222334915355951689081628
8487989988273630445372432174280215755777967021666317047969728172483392
8410156422745072717792693999297403080727703950135815451424940490265361
0582540937311465310494338248437971860693721444460082679800247122948940
5761853892203425608302697052876621377373594394224114707074072902725461
3073585417456914194464876243576823970657031841684675407334663462936739
8362000404140071405427763248013274220268539369886978760700959004868465
0626771363070979821006557285101306601010780633743344773073478653881742
6812307437660666433127753564665786037151929227684404582732832438082128
4121877613204246046490080105473142674926082692215563740548624171703102
7919996942645620955619816454547662045022411449404749349832206807191352
7679867478134582038595704134661779372285349400316315995440936840895725
3343870298671782977037333280680176463950209002394193149911500910527682
1119510999063166150311585582835582607179410052528583611369961303442790
1738117874120612881820620232638498615156564512300477929675636183457681
0504334176954306753804111392855379252924134733948105053202570872818630
7291158911335942014761872664291564036371927602306283840650425441742335
4645499870553187268879264241021473636986254637471597443549434438997300
5174252511087735788639094681209667342815258591992485764048805507132981
4299359911463239919113959926752576359007446572810191805841807342227734
7213977232182317717169164001088261125490933611867805757223910181861685
4910850088527227437421208652485237245624869766224538481929867112945294
5515497030585919307198497105414181636968976131126744027009648667545934
5670599369954645005589216280479763656861333165639073957032720343891754
1526750091501119885687270884819553167693168127289214303137681801644547
7367518353497857924276463354162433601125960252109501612264110346083465
6482355979342740568688492244587454937767521203247038030354911575448312
9527589193989368087632768543876955769488142284431199859570072752139317
6837831770339130423060958999137314684569010422095161967070506420256733
8734461156552761759927271518776600102389447605397895169457088027287362
2512107622409181006670088347473760515628553394356584375627124124445765
1663064085939507947550920463932245202535463634444791755661725962187199
2791865754908578529500128402290350615149373101070094461510116137124237
6142672254173205595920278212932572594714641722497732131638184532655527
9604270541871496236585252458648933254145062642337885651464670604298564
7819684615936632889542997807225422647904006160197519750074605451500602
9180663827149701611098795133663377137843441619405312144529185518013657
5558667615019373029691932076120009255065081583275508499340768797252369
9870235679310268041367457189566414318526790547171699629903630155456450
9004480278905570196832831363071899769915316667920895876857229060091547
2919636381673596673959975710326015571920237348580521128117458610065152
5988838431145118948805521291457756991465775300413847171245779650481758
56395072895337539755822087777506072339445587895905719156736
>

何も準備せずにこういう計算をできるので, Schemeは便利＼(^o^)／

登録: 投稿 (Atom)