階差機関

提供: miniwiki
移動先:案内、検索

階差機関（かいさきかん、difference engine）または差分機関（さぶんきかん）は、歴史上の機械式用途固定計算機で、多項式の数表を作成するよう設計された。対数も三角関数も多項式で近似できるため、そのようなマシンはかなりの汎用性があった。

ファイル:Difference engine.JPG
完全動作する階差機関。カリフォルニア州コンピュータ歴史博物館

歴史

ドイツ・ヘッセンの軍人で技術者のJ・H・ミュラー (J. H. Müller) は1786年に出版した本の中で階差機関に類する機械のアイデアを公表しているが、資金が集められず、それ以上実現に向けて進めることができなかった[1]。

ファイル:Babbage difference engine drawing.gif
階差機関（一号機）

階差機関は一旦は忘れられ、1822年にチャールズ・バベッジによって再発見（再発明）された。彼は6月14日、王立天文学会に「天文暦と数表の計算への機械の適用に関する覚え書き」と題する論文を提出した[2]。この機械が階差機関一号機である。十進方式で、人の手でクランクを回すことで動作する。1830年の設計では、16桁で6階の階差を計算するものであった。1832年に、エンジニアJoseph Clementとのいきちがいから計画の進行は頓挫した。英国政府は当初この計画に資金を提供したが、後に予算を大幅にオーバーし、最終的に1842年に資金的なサポートが断たれている。開発に当たっては、当時の金額で17,000ポンド（さらにバベッジの自己資金がほぼ同額）がつぎ込まれた[3]。右図が階差機関一号機である。バベッジはより汎用的な解析機関の設計に興味を移したが、1847年から1849年にかけて改良した階差機関二号機を設計した（第一階差エンジン・第二階差エンジン、としている文献（新戸『バベッジのコンピュータ』）もあるが、番号付けが「階差」にかかるようにも読めてまぎらわしいので、この記事では「一号機」「二号機」とする。基本設計を大幅に拡大したものであり、同型機の1台目と2台目という意味ではない）。

ファイル:Difference engine Scheutz.jpg
シュウツの階差機関三号機

バベッジの階差機関計画に刺激されたスウェーデンの実業家ペール・シュウツは1843年ごろからスウェーデン政府の援助を受けて階差機関の製作を開始し、1853年には実用機が完成した。シュウツの階差機関はイギリスやアメリカにもわずかながら売れている。しかし、バベッジの本来の設計よりも階数を少なくしたため用途が限られ、想定よりも売れず、シュウツは破産している[4]。マルティン・ヴィーベリもスウェーデンでさらに改良した階差機関を製作したが、彼はそれを使って対数表を作ることしか興味がなかった。しかし、そのころには歯車式計算機を使うことで一般の数表も間違いが少なくなってきていたため、彼の商売も行き詰った。

バベッジの本来の計画に基づいて、ロンドンのサイエンス・ミュージアムは実動する階差機関二号機を1989年から1991年にかけて製作した。バベッジ生誕200周年の記念事業の一環である。2000年には、バベッジが設計した数表出力用プリンターも完成している。もともとの設計図を製造に適した図面に書き写す段階でバベッジの設計にいくつかの細かいミスが見つかったため、それらは訂正する必要があった。完成した階差機関とプリンターはどちらも問題なく動作した。階差機関とプリンターは19世紀の技術水準の信頼性や精度に合わせて製作され、バベッジの設計したものは動くのかという長年の議論に終止符を打った。バベッジの階差機関の開発が失敗した理由としては、当時の工作技術力が不足しているという説もあった。しかし、シュウツ親子による階差機関が完成していることもあり、工作技術力というよりは、実際の開発作業を行なった技術者クレメントとの間での確執、すなわち必要とする費用の問題であったという説もある。今日の視点からは、バベッジが当時要求した精度が過剰なものであったという指摘もあるが、そもそも公差という概念ができる前の時代であることを考えると、工作精度といったことより、このような複雑な機械の製作を管理する工学的手法がまだ無かったと言える。

なお、ここでは便宜的に「プリンター」と呼んでいるが、実際には印刷用の原版を作る機械である。バベッジの意図としては、数表を出版する際に間違いやすい人手による植字という工程を経ずに大量に印刷したいという考えがあった。そのプリンターが紙にも結果を出力するようになっていたのは、階差機関の性能をチェックする手段という意味があった。

サイエンス・ミュージアムでの製作に加え、Nathan Myhrvold の依頼で階差機関二号機の2台めの製作が行われ、2008年5月から2010年末までマウンテンビューのコンピュータ歴史博物館に展示された[5][6][7]。

操作

ファイル:LondonScienceMuseumsReplicaDifferenceEngine.jpg
サイエンス・ミュージアム（ロンドン）にある階差機関のクローズアップ。縦に並んだ歯車がひとつのカラム。6と7の間に金属板の出っ張りがあるが、これは表示している数が9から0になった際に桁上がりが発生したことを伝達するためのものである。数字のあるカラムとカラムの間にある幅の広い歯車が、カラムからカラムへの加算動作を担う部分歯車である。

階差機関は、1 から N まで番号が振られたカラムで構成される。各カラムには十進数の数値を1つ格納できる。階差機関ができることは、n + 1 番のカラムの値を n 番のカラムに加算して n 番のカラムに新たな値（和）を格納することだけである。カラム N には定数のみを格納でき、カラム 1 には現在の繰り返しでの計算値が表示されている（それがプリンターで印刷される）。

階差機関を使用するには、まず各カラムの初期設定を行う。カラム 1 には計算の開始時点の多項式の値をセットする。カラム 2 には一階階差、すなわち次の関数値と前の関数値の差をセットする。カラム 3 以降も1つ前のカラム（階差）についての階差をセットしていく。最終的に N 次多項式では N+1 カラム目で定数となる。従って、少なくとも元の関数値をN個求めておく必要がある。

タイミング

バベッジの設計では、1回の繰り返し（すなわち、必要なカラム間の加算とキャリー操作）はクランクを4回まわすことでなされる。奇数番目のカラムと偶数番目のカラムは交代で加算を行う。n 番目のカラムの動きは次のようになる。

  1. n + 1 番目のカラムから数値を受け取って加算する（歯車の歯をその桁の数のぶんだけ回してカウントアップする）
  2. キャリー伝播（各桁で桁上がりがあったら、そのぶんだけ上の桁の歯車を回す）
  3. n - 1 番目のカラムに数値を渡して加算させる（現在格納している数のぶんだけ隣のカラムの歯車を回すので、自分自身はカウントダウンすることになる）
  4. リセットして元の値に戻す（加算の際に歯車を回したぶんを戻す）

奇数番目のカラムでは 1,2,3,4 の順に動作し、偶数番目のカラムでは 3,4,1,2 の順に動作する。

ステップ

1回の反復ごとに新たな結果が生成され、それは下の写真に見える右端のハンドルを4回転させることで4つのステップ動作をすることでなされる。各ステップは次のようになっている。

ステップ1
偶数番目の全カラム (2,4,6,8) の内容を奇数番目の全カラム (1,3,5,7) に同時に加算する。内部の機構により、偶数番目のカラムの各桁の歯車が回転し0になるまでカウントダウンする。その歯車が示す値が0になるまでに回転した歯数が偶数カラムと奇数カラムの間に位置する別の部分歯車に転写される。その部分歯車の回転した歯数を値として奇数カラムに伝達され、奇数カラムでカウントアップする方向に歯車が回転する。このとき値が "9" から "0" に変わるとき、キャリーレバーが活性化される。
ステップ2
キャリーレバーが動くと、カラムの背後にある螺旋状のアームにその動きが伝わり、それによって1つ上の桁に1が加算される。この加算によってさらにキャリーが発生することもあるため、アームが螺旋状になっている。同時に部分歯車が元の位置に戻り、それに連動して偶数カラムの各歯車が元の位置に戻される。部分歯車は一方が幅広くなっており、ステップ2ではそれを上下にずらすことで（幅が狭い方とかみ合っている）奇数カラムには動きを伝達しない。
ステップ3
ステップ1と似たような動作をする。ただし、ここでは奇数カラム (3,5,7) から偶数カラム (2,4,6) への加算を行う。また、1番のカラムは部分歯車を通じて印刷機構に値を伝達する。偶数カラムでも値が"9"から"0"に変わるときキャリーレバーを動かす。
ステップ4
ステップ2と似たような動作をする。ただし、キャリー伝播が行われるのは偶数カラム上で、値を戻すのは奇数カラムである。

減算

バベッジの階差機関では、負の数を10の補数で表現する。そのようにして、減算を負数の加算として計算できる（補数#補数を利用した減算）。これは、現代のコンピュータが負数を2の補数で表現しているのと全く同じである。

階差の手法

ファイル:Babbage Difference Engine.jpg
ロンドンの サイエンス・ミュージアムにある階差機関。バベッジの設計に基づいて作られた。全カラムの精度（桁数）は同じだが、個々の歯車が表す桁の位置を調整することで収束多項式の高次階差のカラムの表す数値の精度を高めている。なお、バベッジは階差機関を完成させていないため、この階差機関は後世の製作だが、「レプリカ」（復元）にはあたらない。

階差機関の原理は差分商のニュートン補間である。多項式の初期値（とその有限差分）をある値 X について何らかの手段で計算できれば、階差機関を使ってその値を出発点として「有限差分法」と呼ばれる手法で多項式の値を次々と計算できる。以下では小さな例でその原理を示す。

次の二次多項式を考える。

[math]p(x) = 2x^2 - 3x + 2[/math]

この多項式の数表を、xの値の増分が1の場合の、p(0), p(1), p(2), p(3), p(4) といった値について作成する。下記の表の作成方法は次の通りである。まず左のカラムは多項式の値が入っている。中央のカラムは左のカラムの上下に隣り合う2つの値の下から上を引いた差分である。そして右のカラムは中央のカラムの上下に隣り合う2つの値の下から上を引いた二階差分である。

x p(x) = 2x2 − 3x + 2 diff1(x) = ( p(x+1) - p(x) ) diff2(x) = ( diff1(x+1) - diff1(x) )
0 2 -1 4
1 1 3 4
2 4 7 4
3 11 11
4 22

右のカラムの値が一定になる。N次多項式では、N階導関数が定数であるのと同様にN階差分は定数になる。この重要な事実により、以下に示すようにこの手法がうまく機能する。

我々はこの表を左から右へ作っていったが、二階差分が求まるp(2)よりも先は右から左に作業して、さらに多項式の計算結果を求めていく事ができる。それによって階差機関は動作する。

p(5) を求めてみよう。それには上の表の一番下の斜めのマスに入っている数値群を使用する。まず、右端のカラムの定数値4を使い、それを下の空いているマスにコピーする。次に隣のカラムの一番下の値11にその4を加え、15を得る。さらに隣のカラムの一番下の値22にその15を加える。従って p(5) は 22+15 = 37 となる。p(6) を計算するには p(5) を求める際に得られた各カラムの最新の値を使い、同様に計算すればよい。つまり、15に4を加えて19、37に19を加えて56となる。これが p(6) の値である。

必要な範囲をxの増分により必要な間隔で続けられ、好きなだけ値を求めることができる。差分機関はただ加算が出来ればよいので、多項式の値が乗算を使用せずに得られる。この例ではループするたびに2つの値を覚えておく必要がある（左のカラムと中央のカラムの一番下の値）。N次多項式の表を作るにはN個の数値を保持する機構が必要である。

バベッジの階差機関二号機は1991年に完成したが、8個の数値を31桁保持することが出来るようになっており、7次多項式の数表を作成する能力がある。ショイツの作った最も大規模なものでも 4つの15桁の数値までしか保持できなかった。

初期値

各カラムの初期値は、N次多項式の場合数表上の先頭N個の値を別の手段で計算し、そこからバックトラッキングのように通常の階差機関の動作とは逆向きに階差を計算していく。

カラム [math]1_0[/math] には、対象となる関数の始点の値 [math]f(0)[/math] を設定する。カラム [math]2_0[/math] には [math]f(1)[/math] と [math]f(0)[/math] の差分を設定する……といったように続く[8]。

計算対象の関数が次のように表される多項式だとする。

[math] f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0 \, [/math]

初期値は定数係数 a0、a1、a2、……、an からのみ計算でき、多項式の値を計算する必要はない。初期値は次のようになる。

  • Col [math]1_0[/math] = a0
  • Col [math]2_0[/math] = a1 + a2 + a3 + a4 + ... + an
  • Col [math]3_0[/math] = 2a2 + 6a3 + 14a4 + 30a5 + ...
  • Col [math]4_0[/math] = 6a3 + 36a4 + 150a5 + ...
  • Col [math]5_0[/math] = 24a4 + 240a5 + ...
  • Col [math]6_0[/math] = 120a5 + ...
  • [math]...[/math]

導関数の使用

多項式ではないが無限回微分可能な関数の場合、それをテイラー級数のような冪級数で表せる。その初期値は任意の精度で計算できる。正しく初期値を設定すれば、階差機関は最初のN個については正確な結果を返し、それ以降についてはその関数の近似値を生成することになる。

テイラー級数は、関数をその導関数の和で表現したものである。多くの関数において、導関数が高次になるほど級数全体に与える影響は些細になっていく。正弦関数は、0における導関数の値が常に0または[math]+/-1[/math]となる。計算の始点を0とすると単純化したマクローリン級数は次のようになる。

[math] \sum_{n=0}^{\infin} \frac{f^{(n)}(0)}{n!} (x)^{n} [/math]

多項式関数で係数から初期値を計算した方法がここでも適用できる。この式を多項式に展開したときの係数は次のようになる。

[math] a_n \equiv \frac{f^{(n)}(0)}{n!} [/math]

曲線あてはめ

これまで説明した方法の問題点は、始点から離れるに従って誤差が蓄積していき、真の関数から発散していくという点である。誤差の最大値を一定にする解決策として曲線あてはめがある。計算したい範囲について少なくとも等間隔のN箇所の値を求める。ガウスの消去法のように曲線あてはめの技法を使うことで、関数のN-1次の多項式補間が見つかる[8]。最適な多項式が見つかれば、初期値は上述の方式で計算できる。

脚注・出典

  1. ↑ Swedin, E.G. & Ferro, D.L. (2005). Computers: The Life Story of a Technology. Greenwood Press, Westport, CT. Retrieved on 2007-11-17. 
  2. ↑ “Charles Babbage”. The MacTutor History of Mathematics archive. School of Mathematics and Statistics, University of St Andrews, Scotland (1998年). . 2006閲覧.
  3. ↑ 星野 1995, p. 23
  4. ↑ 星野 1995, p. 25
  5. ↑ “At the Museum”. . 2009閲覧.
  6. ↑ Daniel Terdiman (2008年4月9日). “Charles Babbage's masterpiece difference engine comes to Silicon Valley”. CNET News. . 2008閲覧.
  7. ↑ “The Computer History Museum Extends Its Exhibition of Babbage's Difference Engine No. 2”. press release. Computer History Museum (2009年3月31日). . 2009閲覧.
  8. ↑ 8.0 8.1 Ed Thelen (2008年). “Babbage Difference Engine #2 - How to Initialize the Machine -”. . 11-1-2009閲覧.

参考文献

関連項目

外部リンク



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=階差機関&oldid=113361」から取得