Hate B&D

Linux の文化に疑問を持つようになりました。

理由？そのうち書きます。
ひとことでいうと、彼らが主張する「本当の自由」というものに対して疑問を持ったからかな。

彼らは MS のように、他の文化を力ずくで排斥したりしないと思っていたんだけど どうも違うみたいだね。

わたしはそこには「本当の自由」があると聞いていて、もしそうならなんて魅力的な世界だろうって思っていたんだけど、どうやら思い違いだったようだ。

なんてこった

普段使っているエディタ ( Peggy と サクラエディタ ) の使用を禁止されました。もうダメポ ＿|￣|○il|!

替わりに vim 使えとか。vim はたしかに CUI ターミナルから操作するなら、それに適したエディタだと思うけどとにかく使いにくい。 せめて VNC 入れてくれないかなぁ。

閑話休題

In the Blink of an Eyeを読んでいて思わぬ収穫が。いままで球面収差ってなんだろーって思ってたんだけどそれが理解できた。

進化論の創始者ダーウィンが、進化論で説明するには無理があるとさじを投げた問題が2つある。この本はその1つ。眼の起源についての新しい説を、古生物学者である著者がわかりやすく紹介しているものだ。

「眼」という器官は、光が当たる場所に生活する生物なら大抵は備えている器官だが、その構造は大きく異なる。一見同じに見えても内部は全く違うこともある。これから、眼という器官はただ1つの祖先から進化したものではなく、複数の祖先からそれぞれ独自に進化したものだと考えられる。これほどまで広く収斂進化が起こった器官というのは他にはない。なぜ、「眼」だけが？

という内容が、わかりやすく書かれている。化石とか、大昔の生物に興味があるなら専門知識無しでも楽しめる書籍だとおもう。

[javascript] js にも eval() がある

Javascript にも Python でいう exec に相当するものがあるみたい。

知っていたら公開中のツールのコードの冗長性をもっと低くできたかもしれないなぁ
公開中のツールはどれも酷い冗長性だからね(^-^;;

次に作る予定のツールでは、今回知ったことを活かして
DRY Principle と KISS の原則を尊重する方向で作ろうと思う。

Redundancy is evel

Don't Repeat Yourself という原則がある。
DRY Principle というやつだ。

冗長性を取り除く方法がない言語ならまだしも、高い抽象化が可能な言語ならば、 DRY Principle は絶対の原則だ。なぜコードの冗長性が悪いのか。その理由は コードコンプリートと Orthogonality and the DRY Principle ( AndrewHunt と Dave Thomas が受けたインタビュー) に書かれている。

ここではコードコンプリート第二版第二十四章 から一節を引用しよう。

■コードが重複している
　重複したコードがあることは、ほぼ必ずと言ってよいほど、最初の段階で設計が完全に分解されていないことを意味する。コードが重複している場合は、修正を並行作業で行わなければならない。つまり、ある場所を変更したら、必ずもう1つの場所も並行して変更しなければならない。このことは、AndrewHuntとDave Thomasが定めた「DRY（Don't Repeat Yourself）原則」にも違反している（Hunt and Thomas 2000）。これを最も的確に表現しているのはDavid Parnasの「コピーアンドペーストは設計ミスである」だろう（McConnell1998b）。

2箇所重複している ( 同じことが書かれている ) ところがあれば、 将来必ず2箇所修正することになる。100箇所重複していたら、将来必ず 100箇所修正することになるのだ。

え？なんで「必ず」って断言できるかって？
Fred Brooks とコードコンプリートを思い出そう。

現実：コードは最初の開発時に大きく進化する。最初のコーディングで行われる変更の多くは、少なくとも保守段階で行われる変更と同じくらい大がかりなものだ。プロジェクトの規模にもよるが、コーディング、デバッグ、単体テストは、一般的なプロジェクトの作業の30～65%を占める。仮に、コーディングと単体テストが一直線につながっていたとしたら（つまり変更がまったくないとしたら）、プロジェクト全体の20～30%以上を占めることはないはずだ。だが、よく管理されたプロジェクトでさえ、要求の変更は1か月に約1～4%の割合で発生する（Jones 2000）。要求を変更すれば、それに伴ってコードが変更される。そのためにコードが大幅に変更されることもある。

そう、作ったコードは間違いなく変更が加えられるんだ。
1～2箇所の変更ならまだやろうという気にもなるけど、
100箇所も変更するなんて1度たりともやりたくない。
( やったとしてもどっかにミスが残るものです。)

わたしがなるべく冗長性がないようにコードを書く理由はここにある。 作ったコードに後から手を加えることは たいていの場合とてもとても大変な作業だ。その「変更よろしく！」 といわれたときの苦労を少しでも減らしたいからなんだ。
( 焼け石に水の状況も多々あるけど )

可読性が大切(*)なのはいうまでもないことだけど、そのために将来 10倍100倍の苦労をするというトレードオフは、わたしはしたくない。

もし、「DRY Principle なんて知ったことか」とか 「そんなことをしたら可読性が低くなってしまう」と考えている方は もう一度コードコンプリートと Pragmatic Programmer を読んでほしい。 きっと冗長性をなくすことが大切だと気づくはずだ。

それから、わたしに DRY Principle の大切さを理解させてくれたのは havana だ。
わからず屋のわたしに繰り返し DRY Principle の重要性を教えてくれた 親友の havana に心から感謝します。本当にありがとう。

(*):可読性をそれほど損なわない書き方だってあるし、場合によっては 冗長な書き方よりもより簡潔になることだってある。わたしの経験では 可読性論者は特定のキーワード ( goto とか ) に過剰に反応しているだけ の場合が多い。

常識とは18歳までの偏見の寄せ集めである

これはアインシュタインが遺した言葉の一つ。

偏見を持つことは、自ら可能性を狭めてしまうことに繋がる。機会を逃すことに繋がる。

生物学の世界とプログラマの世界を歩いてきたわたしは、
なにかを発想、または創造する人間にとって
身に着けてはならぬもののひとつにこれを挙げる。

「通念は大抵間違っている」

最近読んだ本でこの言葉を見てから、アインシュタインの遺した言葉を思い出した。
そして、自分が当たり前だと思っていることに対して「どうして？」と疑問を投げかけた。
すると驚くほど多くのことが間違っていたことに気付く。

間違っていなくても、
全てに適応できる、銀の弾丸なんてないことに気付く。

最近、再び「常識」とか「定石」とか
「ベストプラクティス」なんて言葉を耳にすることが増えた。

そのたびに改めてこの言葉を胸に刻む。

[Python] 酷いコード

久しぶりに眩暈がするコードを見た。仕事で使うのでなければ、即座に解読を放棄しただろう。それができないからこそ苛立っているわけだが。

問題のコードは Python の標準モジュール logging だ。動作がよくわからないし場合によってはカスタムする必要があるかもしれないので、中をあけてみることになったのだが、これはわたしが「邪悪なオブジェクト指向」と呼んでいる、所謂クラス・継承至上主義のコードだった。何が酷いってたった一つのメソッドを解読するために幾つものクラス、複数のファイルを行き来しなきゃならない。

つまり、goto 文がそこらじゅうに、頻繁に埋め込まれているようなものなのだ。

あなたが経験豊富な C 言語のプログラマなら、goto 文をこれでもかとちりばめたスパゲティを目にしたことがあると思う ( しかもそれを作った担当者はもう現場にいない )。そのときの状況を想像してほしい。Python ではインデントが強制されるので C 言語よりは幾分ましだが、まぁ似たようなものだ。

クラスとか継承を無駄に多用したところで「オブジェクト指向」にはなりえないのだ。

と書きつつ、動的生成コードを書いて顰蹙を買ったわたしがここにいる・・・( ´･ω･`)
(言い訳をさせてもらえば, 先入観を捨ててからコードを見てほしいのだが。)

[python]楽に条件分岐を行う方法

今回は if 文を 使わずに条件に合わせた処理を呼び出す方法。

条件ごとに処理を変えたい場合、一番よく知られているのは if 文だろう。C 言語などならば switch-case を使ったり、ちょっとトリッキーにポインタと配列を組み合わせるかもしれない。

Python では、標準で使える条件分岐は、残念なことに if 文しかない。2～3 個の分岐なら、読むほうも書くほうもちょっと我慢すればいい。しかし、分岐が10個とかあるいはそれ以上になると書くのもイヤだし読むのもイヤだ。

これを解決する方法は、大きく分けて2通りある。条件ごとの処理が全く違う場合と、条件が違っても処理の大部分は同じ場合だ。前者で処理ごとの関数を定義しなければならないのは if 文を使う場合と同じだが、後者の場合は大幅に簡略化できる。

まず、条件ごとの処理が大きく違う場合を考えよう。この場合は、それぞれの条件における処理を関数などに定義しておかなくてはならない。が、このときにちょっと工夫をするだけでかなり楽になるのだ。条件は "hoge", "fuge", "piyo" の3つがあるとしよう。すると、関数の定義は次のようになる。

# -*- coding: UTF-8N -*-
def handle_hoge( arguments ):
    (処理の定義)

def handle_fuge( arguments ):
    (処理の定義)

def handle_piyo( arguments ):
    (処理の定義)

次に定義した関数を呼び出す部分のコードだ。

exec "handle_%s( arguments )" % condition

たった1行だ。とはいっても IOCCC のように邪悪なコードではない。とても単純で簡単なコードだ。恐らく、 exec 構文知っているなら誰でも理解できるレベルだと思う。( とはいってもモジュール丸ごと動的生成するようなコードはとてつもなく邪悪になる( ´･ω･`) )
if 文を使ったよくあるコードと比べてみよう。

# よくある if を使ったコード
def hoge_hoge( arguments ):
    (処理の定義)

def fuge_fuge( arguments ):
    (処理の定義)

def piyo_piyo( arguments ):
    (処理の定義)

# 条件に合った関数を呼び出す
if condition == hoge :
    hoge_hoge( arguments )
elif condition == fuge :
    fuge_fuge( arguments )
elif condition == piyo :
    piyo_piyo( arguments )

この場合は条件が3つしかないからあまり効果が実感できない人もいるかもしれない。実感できないなら、場合分けが20通りもあって、さらに増える（つまり、あとで追加するかもしれない）可能性がある場合を考えてみよう。 exec 構文を使ったコードのほうが柔軟性も高いことが理解していただけると思う。

ちなみに、condition が数値である場合にはリストか辞書配列を定義して、数値から名前を引きできるようにしておけばいい。Python ならリストを生成するコードも簡単に書ける。リストも動的に生成するようにしておけば、後で分岐条件が増えたとしてもその処理を行う関数を追加するだけで動作する。

ポイントは関数名のフォーマットに一貫性を持たせること。condition の値が数値やオブジェクトの場合はそれと関数名を結びつけるリストか辞書配列を定義することの2つ。

[ google ] Innovation に繋がる Chaos

Life is Beautiful のエントリ Googleの強さはStructured ChaosにありでFortuneの特集記事 Chaos by Design" が取り上げられている。特集は Google の組織内の様子について触れたものだ。新しいアイディアが出てきたとき、それを扱ったらいいのか。失敗してしまったとき、どう評価したらいいのか。とても参考になる。 ものづくりの場ではかくあってほしいものだ、という念を籠めて特集記事を翻訳してみることにした。数回に分かれると思うが気長に待ってほしい。

Chaos by Design

Google の無秩序の内側にあるもの。
そしてなぜ Google は全てでそうであろうとするのか。

Google のキャンパスで数分間過ごせば、すぐにそれを実感できる。 ここはカオスの先端で時代を動かしている企業だ。Google は創業から8年、 1年の売り上げは 100 億ドル、時価総額 1250 億ドルの企業だ。しかし、その雰囲気は 専門家が分析したような利潤追求企業ではなく、新鮮さが入り混じっている。

130 万平方フィートの本部は2階建てのビルで、なかには陽気なカフェテリアとか ( もちろん無料だ )、うんざりする会議室だとか、自由討論ができるようなホールウェイ とかが入っている。その周りには砂地のバレーボールコートとか、youngsters whizzing by on motorized scooters, and -- there's no better way to put this -- an anything-goes spirit. ( 訳不可能。助けてください。) Google は失敗と成功が共存する場所だ。アイディアは優れた技術屋からすぐに 浮かび上がってきて、そのプロジェクトが絶対にお金になるかどうか考え込む人は 誰もいない。

最先端のマネージメントスタイル

Sheryl Sandberg を取り上げてみよう。Sheryl Sandberg は 37 歳のバイス・ プレシデントで、企業の自動広告システムを担当している。Sandberg は最近数百万ドル の損失を出すことになったミスをコミットしてしまった。「拙い決定だった。 早く動きすぎた。コントロールができない。いくらかお金を浪費してしまった。」 対する彼女の言葉はこれが全てだった。彼女は自分のミスの大きさを理解すると Google の共同創始者で進む方向を決めている Larry Page に報告した。「たいへん拙い ことが起こってしまいました。すみません。。。」と Sandberg は Page に謝罪し、 Page はその謝罪を受け入れた。しかし彼女が去ろうとしたとき、Page は驚くような 言葉を彼女にかけた。「わたしは君のミスをうれしく思う。なぜならば Google は とてもすばやく、そして大胆に動く企業でありたいと思っているからだ。注意深すぎて こまごまとしか動けない企業にしようとは思わない。もしこういったミスが 全くなかったとしたら、それはただ単に十分なリスクを取っていないからに過ぎない。」 ( 訳注: Page の発言が意味することは「Waltzing with Bears ( 邦題: 熊とワルツを )」 に詳しく書かれています )

数百万ドルもの損失を出して賞賛されるなど、ふつうの企業であれば全く考えられない ことだ。これを理解するために、もう一度 Shona Brown という人物について話したいと 思う。Shona Brown は 40 年前は McKinsey のコンサルタントをやっていた人物で、 現在は Google の事業運営担当上級副社長である。これは彼女の名刺に書いてあることだ。 そして彼女は Google の「カオスな」オフィスのチーフでもある。彼女は 1998 年の ベストセラーとなった本 "Competing on the Edge: Strategy as Structured Chaos" の著者だ ( 訳注:邦題にするとしたら「最先端を走る -- 構造化カオスの原理 -- だろうか )。その通りなのか Google にはカオスが満ちている。 彼女に会うことになっている当日のことだ。わたしたち取材班の案内係とわたしは 残念なことに道に迷ってしまった。Google では誰かを探すには正確な案内と 色分けされた地図を解読する能力が必要なのだ。わたしたちは、なんてこった、 間違ったビルのロビーに入ってしまい、未知を引き返したもののまた別のビルに 入ってしまったおかげで、彼女の場所に到着したのは17分も遅れてのことだった。 Google の建物は確かにカオスに満ちている。

Brown は無秩序であること(訳注: 原文はmade a career of arguing that anarchy isn't such a bad thing ) はそれほど悪くないと考えている。 これは Google の創業者である Page と Brin、CEO の Schmidt が彼女を 雇った理由でもある。技術者が主役となっている企業における経営学の専門家として、 彼女は Google は「究極のペトリ皿」だと思っている。彼女の仕事は何でもありだが 理論的だ。さらに人材管理では、Brown は 25人の戦略コンサルタントの SWAT チームを 運営した。コンサルタントたちは一度に10以上ものプロジェクトを担当していた -- ここで地域販売員の削減を行い、市場のサイズを見積もったのだ。

会社のゴールは必要とされるマネージメントの量を正確に決定すること -- そしてそれより少し少ない量を使うこと -- と Brown はいう。これは彼女が スタンフォード大学の経営学の教授とともに記した本で提唱した Goldilocksian 法 そのものだ。成功への道というのは「とても早くて、あいまいな状況」のなかで生まれる と彼女は語った。そのためには過剰な構造化は避けなければならないし、 全く構造化がない状態でもダメなのだという。言い換えれば、熱過ぎず冷た過ぎない 環境を作らなければならないのだ。「わたしがオフィスに入って快適だと感じて、 あるスタッフに緊張のかけらも感じられないようなら、そのスタッフは解雇 ( 訳注: 原文はthen we've taken it too far ) します。」

ビジネスに Googley 法 でアプローチ

Google には快適さのための風変わりな切り札がある。Google の8000人を超える 従業員の一人を抜けてしまわないように ( 首にならないように？) 常に才気を 維持していなければならない。ミーティングは大抵は正時に始まるが、入ったばかりの Google 社員は少人数用の会議室を前にして戸惑うことが多い。彼らは hallway の ホワイトボードに落書き、ジョークまで書くことがある。たとえば、企業向けの オンライン広告プログラムを腹黒く改良したりするのだ。(「まぶだに AdSense 」 なんてのもあった。)

有名人を目撃することも珍しくない。2～3年ほど前、わたしは日当たりのよい中庭で Page と Brin とゲストとして招待されたコメディアンの Chris Tucker と昼食を食べた。 わたしが Brown と面会した日は George Soros が Google で講義を行っていたし、 Google のアドバイザーである Al Gore は頻繁に姿を見ることができる。 ( 訳注: George Soros は投資家、政治家、慈善活動家として有名なようです。 Al Gore は判りませんでした。検索したら米国副大統領が引っかかりましたが・・・)

このような一風変わった文化を育てるには莫大な費用がかかる。Google は確実にこの方法を 取ってきたのだ。株式公開されてから2年で、Google の株価は4倍になった。莫大な費用がかかるが 収益が高い方法なのだ。だからこそGoogle は巨大なデータセンターを世界中の市場とオフィスに 建設しているにもかかわらず、四半期ごとに現金にして $800 million もの利益を上げているのだ。 現在 Google は Yahoo や Microsoft といった著名な競争相手の一歩上を歩いている。 そして Google のシェアや deals won, buzz (訳注: 適切な日本語訳を思いつきませんでした。 へるぷみー) は、News Corp や Viacom、 WPP といった大手広告代理店に近づきつつある。

Google の中を動かす仕組みが早くなれば、自然にもっと熱くなる。 ( 訳注: 直訳は「Google の検索エンジンが早く動けば、自然と熱を帯びる」。恐らく、企業内に機敏さと柔軟さがあれば 競争力は自然に高まるのだ、ということの喩えだと思います。) これによって多くの失敗に 光明を投じることができる。Google が "Googley approach" と呼んでいる方法だ。( Googley とはどうあるべきかはうんざりするほど語られている。) Google の中を覗いてみると、 stellar financial result から予想されるほどには効率的ではない。 Google の新しいサービスは、検索サービスほど広まってはいない。評論家は「Don't be evil ( 邪悪になるな )」という独善的なモットーに対して嘲笑を向けている。たとえば Google Book Search で著作権がある本まで対象にすると決定したが、これは evil ではないのかということだ。 さらに、高騰している株価。2004 年 8 月 に 85 ドルだったものが、去年の1月には 475 ドルだ。 およそ一年で 400 ドル近く上昇している。UBS のアナリストである Benjamin Schachter は 次のように述べている。「あなたたちのやろうとしていることはもうたくさんだ。 いくつやったら気が済むんだ？」

投資家が関心を持っているのは、Google は 2 つ目のブレイクを考え出せるのかどうかだ。 広告事業つきの検索エンジンの成長は困難であることを示唆するものは何もない。 しかしGoogle が新しい形の広告事業に傾倒していっていることは明らかだし、 開発方法もスパゲティ化していることは明らかだ。その理由は、ひとつは、Google が 全ての技術者に勤務時間の 20% を自分独自のアイディア研究に充てさせている ( 訳注: Google の 20% ルールとして広く知られていることを差しているのでしょう ) ことにある。 技術市場でも、そうでない市場でも、ビジネスの第二幕で成功を収めるのは極めて稀だ。 成功した例を挙げるなら Windows から Office と続いた Microsoft、 メモリーチップの製造ラインを切り捨ててマイクロプロセッサに切り替えた Intel だろうか。 それと、Apple も苦難の十年を経てiPOD で大きな復活をしている。

わたしが一文字変数を嫌う理由

GUI が一般ユーザへのユーザインターフェイスなら、ソースコードはプログラマに「何をやっているのか」を教えるためのユーザインターフェイスといえる。

いいユーザインターフェイスがどういうものか、ということについては Don't Make Me Think! に書かれているけど、その表題が示すとおりだ。

「さて、これは何をやっているんだろうな」とか「この変数には何が入っているんだろうな」って思われるようじゃダメなんだ。ここで考えてみてほしいんだけど、一文字変数とか一文字関数を Glance View しただけでそれらが何をやっているのか、何を保持しているのかわかるだろうか？

ReturnNotNone = lambda a, b: a or b 程度なら、関数の名前とあわせて None ではないほうの値を返すんだなと想像できると思う。でも、10行100行それ以上にわたって使われていたら？関数名まで一文字名だったら？きっと厄介な問題になるだろう。

書いた本人はいいかもしれない ( きっとあとで苦労するだろう ) けど、共同作業しているプログラマは頭を悩ませてしまう。悩んでいる間に1日2日と時間が過ぎていく。わかりやすい名前がつけてあればこんな無駄な時間は過ごさなくてすむはずなのに。

「さてこれは何をやっているんだろう？」と頭を悩ませるケースと、Glance View だけで理解してすぐにその先に取り掛かれるケース。どっちが生産的だと思う？

既に解決したはずの問題に頭を悩ませるか、未解決で誰も挑戦していない問題に取り組むか。どっちがエキサイティング？

ちょっと考えれば一文字名は使わないほうがいい事に気付くはずだ。

[Django/Python] 気に食わない

何が気に食わないって、まずは眩暈がするほど可読性が低い admin ページのテンプレ。そしてだるいテンプレの記述ルール。なんで endfor とか endblock なんだ^*？Python なんだからインデントで片付ければいいじゃないか。または %} でスコープエンドにするとか。まぁ、4294967296歩譲ってこれはいいとしよう。

チュートリアルには開発中はコードを修正すると自動でリロードが行われると書いてあるが、実際には行われないことが多々ある。そのときは開発サーバを手動で停止してから runserver しなきゃならない。このとき、とてもとてもとても親切なことに何も指定しなくても文法チェックをしてくださるらしく、ファイルが増えるにしたがって起動するまでの時間が延びていく。率直に言って邪魔なだけだ。効率のいい開発を妨げているとしか思えない。

動作が遅いプログラムはそれだけで存在価値がないと思っているわたしにとって一番気に食わないのは、この自動チェックだ。とりあえず動かしてみて、エラーが返ってきたり、動作がおかしかったらデバッガとかチェッカ走らせればいいだけじゃないのかな。無駄なことするよりさっさと起動してほしい。

今のところは、わたしにとっては Django は最も使いたくない Python Extension だ。

(*): 突っ込まれそうなので補足。
{% ～: %} か {{ ～ }} を使って下のように書けばいいよねということ。

{% if hoge:
    <ul>
        {% for fuge in [ piyo for piyo in piyopiyo ]:
            <li>{{ waha }}</li>
        %}
    </ul>
%}

尻尾の % はなくてもいいかもしれない。そうすれば 1キーですむし。{% %} ～ {% %} みたいに何回もカタカタタイプしなきゃならないのはすごくイヤだ。

[Django/Python] 文字化けをなくす方法

僅差で nakagami さんに先を越されてしまったけど、半日悪戦苦闘したのを投げてしまうのもしょんぼりなので書いておく。

Django を Windows にインストールしてチュートリアルを進めると、いろいろ試してみましょうって書いてあるものだから日本語を使う人もいると思うんだ。わたしもその一人なんだけどね。でも、初期設定のままで日本語を使うと下のようにコンテンツが何も映らないか、文字化けするんだよね。

解決方法

Django は UTF-8 を使うことを前提に作られています。Python コードは Python ランタイムが解釈して実行するので文字コードが何であろうと関係ないのですが、htm ファイルは UTF-8 で保存しましょう。ただし、UTF-8 にもいくつか規格が存在します。ハズレだとやっぱりコンテンツが見えません。Peggy だと UTF-8 では NG で UTF-8N で保存する必要がありました。

それと、サイトの設定も必要です。サイトの設定は setting.py で行います。 setting.py に LANGUAGE_CODE という項目があります。デフォルトでは 'us-en' かなにか、日本以外が指定されています。これを 'ja' (← アルファベットは全部小文字。シングルクォーテーションで囲む ) に変更して保存しましょう。全ての設定が終われば↓のようにちゃんと見えるようになります。

まとめ

• htm ファイルは UTF-8 で保存
• setting.py の LANGUAGE_CODE = 'ja'
• DB が MySQL とかの場合はそっちの設定もチェック

( ´-ω-`).oO(ﾅﾝｶﾁｮｳｼﾜﾙｰ

先週1週間は昼間に起きて活動。数年間ずっと夜活動していたのでかなりつらかった。夜に寝てもほっとんど疲れが取れないんだよね。3連休の3日目になって（*既に夜型に切り替わってます ) やっと疲れが取れた感じがする。

「プログラムは夜できる」

ナンカに書いてあったんだけど、わたしにとってはこれは真実だ。
夜の方が閃くことが多いし集中できる。

今週からも昼間動かなきゃならないわけだけど、さてどうなるか。

ま、いつも自分に有利な状況で動けるとは限らないから、自分に不利な状況でどこまでできるかやれるだけやってみようと思う。

[Python] Miller-Rabin Pseudoprime Test

The module file is here.

def modular_exponentiation( base, exponent, modulus ):
        """
        caluclating ( base ** exponent ) % modulus via the Right to Left Binary Algorithm.
        detail of "modular exponentiation", see follow URL.
        http://en.wikipedia.org/wiki/Modular_exponentiation
        """
        remainder = 1
        
        while( exponent > 0 ):
                if( (exponent & 1) > 0 ):
                        remainder = ( remainder * base ) % modulus
                
                exponent >>= 1
                base = ( base * base ) % modulus
                
        return remainder


def miller_rabin( almost_prime, base_list ):
        # base_list should contain some primes
        
        remainder= 1
        
        for base in base_list:
                exponent = almost_prime - 1
                while( exponent > 0 ):
                        # exponent were odd number and ( base ^ exponent ) ≡ 1 mod modulus,
                        # then continue the loop. Because almost_prime has a probability that it is a prime.
                        # The case when ( base ^ exponent ) ≡ -1 mod modulus means passing Miller-Rabin witness with the base then testing with next base.
                        # However ( base ^ exponent ) is not congruent, then immediately almost_prime is identified as pseudoprime: return False.
                        remainder = modular_exponentiation( base, exponent, almost_prime )
                        
                        if remainder == ( almost_prime -1 ):
                                break
                        if( remainder != 1 ) and ( remainder != (almost_prime -1 ) ):
                                return False
                        if( exponent % 2 ):
                                break
                        exponent  >>= 1

        prime = almost_prime
        return prime

Miller-Rabin witness
Define sequence r(n) = b ^ {(m-1)/2n} % m
When an integer m is a prime and also b ( b < m ) is a prime then:

a(1) ≡ 1		a(1) ≡ 1
a(2) ≡ 1		・
・	OR	・
・		a(n-1) ≡ 1
a(n) ≡ 1		a(n) ≡ -1

Miller-Rabin witness is application of this feature. Function modular_exponentiation() calculates value of a(n). Function miller_rabin() evaluates sequence a(n). If a(n) !≡ ( 1| -1 ) then m is not prime. Otherwise m has passed Miller-Rabin pseudoprime test with the base. However, with another bases, it might be failed. Therefore it is necessary to test with more than one primes.

Overview of Miller Rabin Pseudoprime test, see Wikipedia: Miller-Rabin primality test.