« カリー化について調べてみました。 | トップページ | どうやら腸炎になってしまったようです。 »

2008年11月27日 (木)

SICP本を読み進めています(現在1.3.1章)

前回の勉強会の時から、続けてSICP本を読み進めています。

1.2.5章 最大公約数
「ユークリッドのアルゴリズムを使って2数の最大公約数を求めてみる事を考える。」
ということです。
これは、r = (a mod b)とした場合に、aとbの公約数はbとrの公約数と同じになるという
性質を利用したものです。(modは割った余り)
で、これをプログラムにしてみると、実行ステップ数が対数的に増加しますよ。と
言うことが言いたいみたいです。

1.2.6章 素数性のテスト
「素数を調べるアルゴリズムで、オーダがO(√n)で増加するケースとO(log N)で増加するケースの
2パターンで考えてみる」と言うことです。
まず1つ目は、力任せに2から順番に割ってみて、割り切れるかどうかをテストする。
もう1つは、Fermatテストというnが素数かつ、a < n が成立する時にa ^ nを計算し、
a ^ nをnで割った余りがaになるとnは素数の「可能性が高い」という性質で算出する」方法を
使っています。

確かにa = 2 n = 3の場合、2^3=8 % 3 = 2になりますね。

|

« カリー化について調べてみました。 | トップページ | どうやら腸炎になってしまったようです。 »

OSS活動」カテゴリの記事

コメント

こんにちは。お久しぶりです。
Sun Certified Programmer for the Java 2 Platform 1.4 (SJC-P) に受かりました。来年は新試験になったらしい情報セキュリティスペシャリスト試験を受けたいと思います。TOEIC も何となく受けたのですがまだ結果がわかんないんですよね-。

投稿: p2 | 2008年12月 2日 (火) 00時46分

p2さん
おひさしぶりです。
Javaの道をがんばってらっしゃいますね。
私は少し触る程度になってしまいました。
Javaの試験も受けようと思った時期も
ありましたが、回避してましたね。
新試験になるといきなり一番上のランクに
なりますし、獲得すれば必ずプラスになりますよ!
私はアナログ放送と同時にActiveじゃ無くなる
LPIとJava試験それから、データベース試験に
挑戦しようかなと思ってます。
どれからかはわかりませんが。

投稿: T-1000 | 2008年12月 2日 (火) 22時44分

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/50625/43249218

この記事へのトラックバック一覧です: SICP本を読み進めています(現在1.3.1章):

« カリー化について調べてみました。 | トップページ | どうやら腸炎になってしまったようです。 »