階差機関のソースを表示

'''階差機関'''（かいさきかん、{{Lang-en-short|difference engine}}）{{efn|直訳的には「差分機関」となることなどからそのように訳されていることもあるが、「差分を得る機械」ではないし、詳細で説明するように高階差分と合計計算を利用する機械であるから、「階差」と意訳するのが適切である。}}は、歴史上の機械式用途固定計算機で、[[多項式]]の[[数表]]を作成するよう設計された。[[対数]]も[[三角関数]]も多項式で[[テイラー展開|近似]]できるため、そのようなマシンはかなりの汎用性があった。

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

== 歴史 ==
{{wikisourcelang|en|Astronomische Nachrichten/Volume 46/On Mr. Babbage's new machine for calculating and printing mathematical and astronomical tables}}
[[ドイツ]]・[[ヘッセン州|ヘッセン]]の軍人で技術者のヨハン・ヘルフリッヒ・フォン・ミュラー ([[:en:Johann Helfrich von Müller|Johann Helfrich von Müller]]) は1786年に出版した本の中で階差機関に類する機械のアイデアを公表しているが、資金が集められず、それ以上実現に向けて進めることができなかった<ref>{{cite book |url= https://books.google.co.jp/books?id=c1QbNtTz4CYC&redir_esc=y&hl=ja |title=Computers: The Life Story of a Technology |accessdate=2007-11-17 |date=2005 |author=Swedin, E.G. & Ferro, D.L. |publisher=Greenwood Press, Westport, CT}}</ref>。

[[ファイル:Babbage difference engine drawing.gif|200px|thumb|right|階差機関（一号機）]]
階差機関は一旦は忘れられ、1822年に[[チャールズ・バベッジ]]によって再発見（再発明）された。彼は6月14日、[[王立天文学会]]に「天文暦と数表の計算への機械の適用に関する覚え書き」と題する論文を提出した<ref>{{cite web | coauthors = John J. O'Connor, Edmund F. Robertson | date = 1998 | url = http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Babbage.html | title = Charles Babbage | work = The MacTutor History of Mathematics archive | publisher = School of Mathematics and Statistics, University of St Andrews, Scotland | accessdate = 2006-06-14}}</ref>。この機械が階差機関一号機である。十進方式で、人の手でクランクを回すことで動作する。1830年の設計では、16桁で6階の階差を計算するものであった。しかし1832年にバペッジと協力者のエンジニア、{{仮リンク|ジョセフ・クレメント|en|Joseph Clement}}との行き違いから計画の進行は頓挫した。[[イギリスの政治|英国政府]]は当初この計画に資金を提供したが、後に予算を大幅にオーバーし、最終的に1842年に資金的なサポートが断たれている。開発に当たっては、当時の金額で17,000ポンド（さらにバベッジの自己資金がほぼ同額）がつぎ込まれた<ref>{{Harvnb|星野|1995|p=23}}</ref>。右図が階差機関一号機である。バベッジはより汎用的な[[解析機関]]の設計に興味を移したが、1847年から1849年にかけて改良した階差機関二号機を設計した（第一階差エンジン・第二階差エンジン、としている文献（新戸『バベッジのコンピュータ』）もあるが、番号付けが「階差」にかかるようにも読めてまぎらわしいので、この記事では「一号機」「二号機」とする。基本設計を大幅に拡大したものであり、同型機の1台目と2台目という意味ではない）。

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

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

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

サイエンス・ミュージアムでの製作に加え、元[[マイクロソフト]]の[[最高技術責任者|CTO]]・[[:en:Nathan Myhrvold|ネイサン・ミルボルド]] の依頼で階差機関二号機の2台めの製作が行われ、2008年5月から2010年末まで[[マウンテンビュー]]の[[コンピュータ歴史博物館]]に展示された<ref name="chm1">{{cite web|url= http://www.computerhistory.org/atmuseum/|title=At the Museum|accessdate=2009-07-28}}</ref><ref name="chm2">{{cite web|url= http://news.cnet.com/8301-13772_3-9915667-52.html|title=Charles Babbage's masterpiece difference engine comes to Silicon Valley|author=Daniel Terdiman|work=[[CNET|CNET News]]|date=April 9, 2008|accessdate=2008-04-28}}</ref><ref name="chm3">{{cite web|url= http://www.computerhistory.org/press/babbage-engine-extension.html|title=The Computer History Museum Extends Its Exhibition of Babbage's Difference Engine No. 2|work=press release|publisher=[[コンピュータ歴史博物館|Computer History Museum]]|date=March 31, 2009|accessdate=2009-11-06}}</ref>。

== 操作 ==
[[ファイル:LondonScienceMuseumsReplicaDifferenceEngine.jpg|thumb|[[サイエンス・ミュージアム]]（ロンドン）にある階差機関のクローズアップ。縦に並んだ歯車がひとつのカラム。6と7の間に金属板の出っ張りがあるが、これは表示している数が9から0になった際に桁上がりが発生したことを伝達するためのものである。数字のあるカラムとカラムの間にある幅の広い歯車が、カラムからカラムへの加算動作を担う部分歯車である。]]
階差機関は、'''1''' から '''N''' まで番号が振られたカラムで構成される。各カラムには十進数の数値を1つ格納できる。階差機関ができることは、''n''&nbsp;+&nbsp;1 番のカラムの値を ''n'' 番のカラムに[[加法|加算]]して ''n'' 番のカラムに新たな値（和）を格納することだけである。カラム ''N'' には[[定数]]のみを格納でき、カラム 1 には現在の[[ループ (プログラミング)|繰り返し]]での計算値が表示されている（それがプリンターで印刷される）。

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

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

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

奇数番目のカラムでは 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|thumb|320px|ロンドンの [[サイエンス・ミュージアム]]にある階差機関。バベッジの設計に基づいて作られた。全カラムの精度（桁数）は同じだが、個々の歯車が表す桁の位置を調整することで収束多項式の高次階差のカラムの表す数値の精度を高めている。なお、バベッジは階差機関を完成させていないため、この階差機関は後世の製作だが、「レプリカ」（復元）にはあたらない。]]
階差機関の[[原理]]は[[差分商]]の[[ニュートン補間]]である。多項式の初期値（とその有限差分）をある値 '''''X''''' について何らかの手段で計算できれば、階差機関を使ってその値を出発点として「有限[[差分法]]」と呼ばれる手法で多項式の値を次々と計算できる。以下では小さな例でその原理を示す。

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

<math>p(x) = 2x^2 - 3x + 2</math>

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

{| class="wikitable"
!<math>x</math>!!<math>p(x) = 2x^2 - 3x + 2</math>!!<math>\text{diff1}(x) = p(x+1) - p(x)</math>!!<math>\text{diff2}(x) = \text{diff1}(x+1) - \text{diff1}(x)</math>
|-
|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> の差分を設定する……といったように続く<ref name="Thelen">{{Cite web| url = http://ed-thelen.org/bab/bab-intro.html| title  = Babbage Difference Engine #2 - How to Initialize the Machine -| accessdate  = 11-1-2009| author = Ed Thelen| date = 2008}}</ref>。

計算対象の関数が次のように表される[[多項式]]だとする。
: <math> f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0 \, </math>
初期値は定数係数 ''a''<sub>0</sub>、''a''<sub>1</sub>、''a''<sub>2</sub>、……、''a<sub>n</sub>'' からのみ計算でき、多項式の値を計算する必要はない。初期値は次のようになる。

* Col <math>1_0</math> = ''a''<sub>0</sub>
* Col <math>2_0</math> = ''a''<sub>1</sub> + ''a''<sub>2</sub> + ''a''<sub>3</sub> + ''a''<sub>4</sub> + ... + ''a<sub>n</sub>''
* Col <math>3_0</math> = 2''a''<sub>2</sub> + 6''a''<sub>3</sub> + 14''a''<sub>4</sub> + 30''a''<sub>5</sub> + ...
* Col <math>4_0</math> = 6''a''<sub>3</sub> + 36''a''<sub>4</sub> + 150''a''<sub>5</sub> + ...
* Col <math>5_0</math> = 24''a''<sub>4</sub> + 240''a''<sub>5</sub> + ...
* Col <math>6_0</math> = 120''a''<sub>5</sub> + ...
* <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次の[[多項式補間]]が見つかる<ref name="Thelen" />。最適な多項式が見つかれば、初期値は上述の方式で計算できる。

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}
=== 出典 ===
{{Reflist|2}}

== 参考文献 ==
* {{cite book|last=Swade|first=Doron|title=Charles Babbage's Difference Engine No. 2 – Technical Description |url= http://ed-thelen.org/bab/bab_tech.html|format=HTML, PDF|accessdate=2001-01-01-2009|series=Science Museum Papers in the History of Technology No 5 |date=1996-09 |publisher=National Museum of Science and Industry|location=London|isbn=|oclc=|doi=}}
*{{cite book | last = Swade | first = Doron | date = 2002 | title = The Difference Engine: Charles Babbage and the Quest to Build the First Computer | publisher = Penguin (reprint) | id = ISBN 0-14-200144-9}}
* {{cite book | last = Swade | first = Doron | date = 2001 | title = The cogwheel brain | publisher = Abacus | isbn = 0-349-11239-8}}
* {{cite video | df=ja | people=Doron Swade, Nathan Myhrvold | url=https://www.youtube.com/watch?v=p1sEowi1Txc |title=Myhrvold & Swade Discuss Babbage's Difference Engine. | medium=lecture: Len Shustek, intro; Doron Swade @7:35, Nathan Myhrvold @36:25; discussion @46:45 | publisher=[[コンピュータ歴史博物館|Computer History Museum]] | date=2008-06-10 | accessdate=2009-11-06 }}
* {{Citation|last=星野|first=力|date=1995年|title=誰がどうやってコンピュータを創ったのか？|publisher=共立出版|isbn=4320027426}}
* {{cite journal|author=Swade, Doron D. |title=Redeeming Charles Babbage's mechanical computer |journal=[[Scientific American]] |issue=268 |year=1993 |page=86-91 }}
* {{cite journal|和書|author=D.D.スウェイド|date=1993年4月号 |journal=[[日経サイエンス]] |title=150年目に完成したバベジの計算機 |page=136-143 }}
* {{cite journal|author=Kim, Eugene Eric |author2=Betty Alexandra Toole |url=http://www.academia.edu/download/35681085/scientificamerican0599-76.pdf |title=Ada and the first computer |format=PDF |journal=SCIENTIFIC AMERICAN-AMERICAN EDITION- |issue=280 |year=1999 |page=76-81}}
* {{cite journal|和書|author=Kim, Eugene Eric |author2=Betty Alexandra Toole |title=19 世紀のプログラマー バイロンの娘エイダ |journal=[[日経サイエンス]] |volume=29 |issue=8 |date=1999年8月号 |page=62-69}}

== 関連項目 ==
* [[チャールズ・バベッジ]]
* [[エイダ・ラブレス]]
* [[ペール・シュウツ]]
* [[マルティン・ヴィーベリ]]
* [[歯車式計算機]]
* [[解析機関]]

==外部リンク==
{{commonscat|Difference engines}}
* [http://www.computerhistory.org/babbage/ The Computer History Museum exhibition on Babbage and the Difference Engine]
* [http://www.sciencemuseum.org.uk/onlinestuff/stories/babbage.aspx ''Babbage''] 
* [http://www.meccano.us/difference_engines/rde_1/ Meccano Difference Engine]
* [http://www.meccano.us/difference_engines/rde_2/index.html Meccano Difference Engine #2]
* [http://acarol.woz.org/ Difference Engine in Lego]
* [http://satyam.com.ar/Babbage/en/index.html Difference Engine workings with animations]
* [http://www.powerhousemuseum.com/collection/database/?irn=150269&img=146773 Difference Engine No1 specimen piece at the Powerhouse Museum, Sydney]
* {{YouTube|KBuJqUfO4-w|Charles Babbage and his Difference Engine #2}}

{{DEFAULTSORT:かいさきかん}}
[[Category:数学に関する記事]]
[[Category:コンピュータ史]]
[[Category:機械式計算機]]
[[Category:歴史上の機器]]
[[Category:チャールズ・バベッジ]]
[[Category:エイダ・ラブレス]]