コンピューターの考え方

コンピューターの中では、とても単純な部品とやり方が、何重にも積みかさなっています。ここでは4つ取り上げます。どれも、考え方そのものは短い時間で分かるのに、そこに行きつくまでには長い歴史がありました。

論理ゲートと足し算（このサイトの「論理ゲートと足し算」）

ANDは「両方が1のときだけ1」、ORは「どちらかが1なら1」、NOTは「0と1を入れかえる」、XORは「ちがうときだけ1」です。 1ビット（0か1）どうしの足し算は、答えの1の位をXORが、くり上がりをANDが受け持てば作れます。この回路を「半加算器」と呼びます。 このサイトのプログラムで、4つのゲートの表と、半加算器が 0+0、0+1、1+0、1+1 を正しく計算することを確かめました（logic-gates/engine.test.ts）。

さらに前の桁からのくり上がりも足せるようにしたものが「全加算器」です。ちなみに、NAND（ANDの結果を反転するゲート）だけを使っても、ほかのゲートを全部作れることが知られています。

ブールとシャノン

ジョージ・ブールは、1854年の著書『思考の法則の研究』で、論理を0と1の代数として扱いました。 ただし、ブールの時代に電気回路への応用は考えられていません。「ブールが論理回路を作った」のではなく、あとで回路の設計に使われる代数を作ったのです。

クロード・シャノンは、1937年ごろのMITの修士論文で、リレー（電気で動くスイッチ）の回路の設計にブール代数が使えることを示した、とされています。年は資料によって1936〜1938年とゆれます。 日本の中島章も、1935〜36年にスイッチ回路についての論文を書いていて、シャノンの先行研究とする説明もあります。ですから、「シャノンがすべての始まり」とは言えません。

並べ替えレース（このサイトの「並べ替えレース」）

並べ替え（ソート）には、いろいろな方法があります。このサイトでは、バブル・挿入・選択・クイック・マージの5つを、同じ棒の並びで競わせます。 16本の棒で、次のことをこのサイトのプログラムで確かめました（sorting-race/engine.test.ts）。

• 選択は、どんな並びでも比べる回数がちょうど120回（16×15÷2）です。
• マージは、どんな並びでも書きこみがちょうど64回（16×4）です。
• バブルと挿入は、逆順だと比べる回数が120回、すでに並んでいると15回です。
• バブルと挿入の入れかえ回数は、「順番が逆になっている組」の数と同じです。
• ほぼ並んでいるときは、挿入がいちばん少ない手数ですみます。

並びによって得意不得意が変わります。「いつでも一番速い方法」はありません。

歴史から

ジョン・フォン・ノイマンが1945年にEDVACという計算機のために書いた、2つの整列ずみの列をまとめるプログラムが、マージソートの最初期のものとして知られている、とされています。 ただし「マージソートを発明した」と言い切れるわけではありません。

クイックソートは、C・A・R・ホーアが、1959年にモスクワに留学していたとき、機械翻訳のためにロシア語の単語を並べる必要があって考えついたものです。論文は1961年7月号のCommunications of the ACMに載りました。

比べるだけで並べる方法には、どんなに工夫しても超えられない回数の下限があることが、数学で証明されています。 ただし、数字の大きさそのものを使う基数ソートのように、比べない方法はこの限界の外にあります（キーが整数など、条件があるときです）。

シーザー暗号（このサイトの「シーザー暗号」）

文字をすべて同じ数だけずらす暗号です。古代ローマの伝記作家スエトニウスが『ローマ皇帝伝』のカエサルの章で、カエサルが秘密の手紙で文字を3つ後ろにずらして（AをDにして）書いた、と記しています。 スエトニウスが書いたのは、カエサルの死から約150年後です。「シーザー暗号」という名前も、後の時代のものです。

ずらし幅の候補は少ないので、全部試せば破れます。もっと賢いのが頻度分析です。ふつうの文章では、よく出る文字とあまり出ない文字がはっきり分かれます。文字をずらしても、その偏りは形を変えずに横へずれるだけなので、グラフの山の位置から、ずらし幅が分かります。 このサイトのプログラムで、ずらし幅を変えるとグラフの山がそのぶんずれること、そして解き方のプログラムが全問のずらし幅を見つけて、もとの文に戻せることを確かめました（caesar-cipher/engine.test.ts）。

この頻度分析を書き残した最古の例とされるのが、9世紀のバグダードの学者アル＝キンディーの文書です。その写本は長く失われていて、1987年に再発見されたと伝えられます。 なぜ文字の頻度に気づいたのか、細かい経緯は分かっていません。「最古とされる」と言うのが安全です。

半分ずつ数あて（このサイトの「半分ずつ数あて」）

1から100の数を当てるとき、真ん中を聞くと、候補がちょうど半分になります。このサイトのプログラムで、次のことを確かめました（binary-search/engine.test.ts）。

• 1〜100は、どの数でも7回以内に当たります。6回で見分けられるのは63通りまでなので、6回では足りません。
• 1〜1,000,000は、どの数でも20回以内に当たります。
• 1〜100で、1回・2回・3回・4回・5回・6回・7回で当たる数は、順に 1・2・4・8・16・32・37 個です。
• たとえば37なら、予想は 50、25、37 の3回です。

範囲が1万倍になっても、必要な回数は7回から20回に増えるだけです。これが「二分探索」です（データが順番に並んでいることが前提です）。

かんたんなのに、書くのは難しかった

二分探索が最初に発表されたのは1946年とされます。でも、どんな長さのデータでも正しく動く形が最初に発表されたのは、1962年でした。 ジョン・ベントレーは、プログラマに二分探索を書かせたところ、約9割に誤りがあったと報告した、と伝えられています。実験の条件は資料によって説明が異なるので、数字は目安です。

2006年6月には、ジョシュア・ブロックが、Google Research Blogで、有名な本や、Javaの標準ライブラリにあった二分探索にも不具合があったと公表しました。 真ん中を求める「(low + high) / 2」の足し算が、データがとても長い（2の30乗個以上）と、整数の桁あふれを起こすのです。マージソートなどにも、同じ種類の誤りがありえます。 考え方は数分で分かっても、正しく書くのには、60年たってもまちがいが見つかるほどの注意が必要でした。

ちがう4つに共通すること

• 小さな部品の積みかさね：XORとANDだけで足し算ができます。
• 並びによって変わる：並べ替えに「いつも最強」はありません。
• 偏りが手がかりになる：暗号は、文字の頻度で破れます。
• 半分に分ける力：100万個でも20回です。

ここの図は、どれも教育用の簡略化モデルです。実際のコンピューターには、ここで省いている細かな事情がたくさんあります。