hirax.net::Keywords::「計算順序」のブログ

■エクセルの計算プロセスの詳細　

　Microsoft Excelにおける計算プロセスの詳細

■エクセルにおける循環参照時の計算順序　

　表計算ソフトのエクセルを使えるようになりたいと考えた。そこで、（これまで近づかないようにしていた）エクセルを使ってみることにした。まずは、エクセルの計算順序について調べてみた。もう少し具体的に書くと、計算の順番が「セル配置」に依存するのはどのような場合かを調べてみた。

　まず、最初にわかったのは「循環参照がない場合」には、（各セルの）計算順序は「セル配置」に依存しないということである（エクセルの計算プロセスの詳細）。また、「手動計算」や「反復計算」を行うようなオプション設定にしていたとしても、循環参照さえなければ（各セルの）計算順序は「セル配置」に依存しなかった。

　その一方で、循環参照があると、（各セルの）計算順序は「セル配置」に依存するようになる。具体的には、左上から横1行を計算したあと、その下の1行を計算し、さらにその下の1行を計算する…という具合である。

　だから、「反復計算」を1回だけ「手動計算」で行うような設定にし、
B1に2
A1に=B2
C1も=B2
B2は=B1
B1にA1-C1
という風に入力し、F9を押して手動計算させると、次々と値が変わり、6回周期の動きを示す。しかもA1とC1はいつも同じ値だが、その差分をとっているはずのB1は、ゼロになる瞬間もあるが、2とか-2とかゼロでない値にもなる。

　これは、循環参照が行われている場合に、反復計算オプションを付けた際の「各セルの計算順序」が前述のようだからである。当たり前の話のようだが、少し面白い。

■C++の「i++ と ++i の違い」とExcelの「i++ と ++i の違い」　

　ビール瓶を開けながら「プログラミング言語」の話題をしました。プログラミング…と言っても、思い切り（プログラミング言語的には）低レベルな話ばかりです。ここで言う「低レベル」というのは、ハードウェアに近いとかそういう意味の「低レベル」ではありません。

　たとえば、「C++で書くけど、ほぼFORTRANなんだよね〜」という「一体どんなC++だぁ？」というツッコミをしたくなるコード論であったり、「それって、必ず７文字のインデントを入れてからC++のコードを書くってことですか？」というこれまた低次元な「インデント論」だったりしたのです。

　そんな中、「（C++なら）とりあえず、a++とは書かずに、++aと書きますよね」という話になりました(参考：C++のi++ と ++i の違い)。そして、さらに、「（C++ではなくて）C言語のi++ と ++i の違い」みたいなことをMicrosoft Excelでも気にすることがあるか？という話題になりました。話題が脈絡無くサブルーチンに"GOTO"するのは、それは単にアルコール１００％の酔っぱらいだから、です。

　「C言語のi++ と ++i の違い」みたいなことがMicrosoft Excelでもあるか？気にするか？というと、その答えはもちろん「YES」です。…なぜかといえば、たとえば、A1,B1,C1という３つのセルがあった時、それらの各セルに対して、
A1=B1
B1=B1+1
C1=B1
という式を設定する場合など、（自分自身のセルを参照する）循環参照になっているために、その際の計算順序は単純にZの法則にしたがって左→右・上→下の順番で行われるために、計算結果は
　A1,B1,C1=1,2,2
となるからです。A1とC1は、同じ式がセルに入力されていても、実は違う値（タイミング）のB1を参照するがために、違う値になるのです。…それは少しばかり「（C言語の）++iとi++の違い」に似ています。

　C++という言語名は「C＋＋って、（＋＋Cじゃないから）使う時は（前の値と同じというわけで）Cに過ぎないよね？」といった冗談をよく聞いたような気がします。それぞれの言語が抱える「（ちょっと意外にも感じる）++iとi++の違い」にはどんなものがあるのでしょうか？そしてまた、Microsoft Excel で++aとa++の違いを気にする人は、一体どのくらいいるものでしょうか？

■Microsoft Excelで "=-1^2" が "-1"ではなくて"1"になる「理由」　

　Microsoft Excelで "=-1^2" が "-1"ではなくて"1"になるのが「なぜだろう？」というtweetを興味深く読み、そこから辿り着いた20年前のメーリングリスト記事が面白かったので、簡単なメモ書きをしてみます。メモ書きなので、面白い記事へのポインタと（その記事に対する）わずかな感想を書いただけの日記記事です。

　まず、この計算順にまつわる問題を考える時には、" Warning: Excel Performs Negation Before Exponentiation"のタイトルにもなっているように、Excelという一種のプログラミング環境上での、"negation"と"subtraction"という異なる2演算子の計算順序の違いを区別する必要があります。つまり、

=-A1^2

=1-A1^2

　次に、20世紀最後の年、つまり西暦2000年1月13日の20:18:46にDoctor Petersonがメールで書いている文面がとても参考になります。それは、"negation"のような単項演算子は”exponent”のような二項演算子に優先して演算されるものだったから、それをただ踏襲すると、こんな計算順序になるよね、というものです。「Lotus 1-2-3との互換性を重視した」わけではないけれど、プログラミング言語の過去経緯を踏まえて考える話だよね、というものです。

　そして何よりも、西暦2005年の12月16日にErikが書いているように、Windowsのメモ帳で "msgbox -2^2"と書いてから、そのファイルをtest.vbsという名前で保存して、もしもダブルクリックしたならば、（マイナス4ではなくて）"4"という答えが書かれたメッセージボックスを私たちは目にするよね。この例でもわかるように、エクセルの「ダメな話」として眺めるのではなくて、コンピューター科学の「興味深い話」として眺めるべき話じゃないか？というコメントが、とても参考になると思います。

So I think this isn't bad math on Excel's part, but good computer science.

■「エクセルの計算順序」から「コンピュータの歴史」を感じよう！　

-2020年になった今、1950-1980の時代を振り返る-

-1^2の計算結果は-1になる！？「エクセルの計算順序」の謎

　オフィス作業の多くがMicrosoft Excel（エクセル）上で行うのが当たり前となっています。そのエクセルでシートを開き、”= 0 - 1^2”, “= -1^2 + 0”という2式をセルに入力すると、どんな計算結果が出力されるでしょうか？

「どちらも-1になるはず」と答える人が多いかもしれませんが、実際に式をセルに入力すると、”=0 - 1^2→ -1”, “=-1^2+0→1”という結果になります（図１(a)）。だからといって、「エクセルの計算バグ！？」と考えてはいけません。なぜなら、これは伝統正しいエクセルの仕様だからです。

同じ“-”でも二項演算子の”-”と単項演算子の”-”がある？

「どちらも-1になるはず」という答は、２式をそれぞれ0 –(1^2)と-(1^2)+0という順番に暗算から得られたはずです。…けれど、エクセルが行う計算順は、それとは違う0 –( 1^2)と(-1)^2+0という順番です。その結果、 -1と1という計算結果をエクセルは得るのです。

「減算よりべき乗の演算の方が優先されるべきだから、エクセルの計算順はやはりおかしくない？」と思う人もいるかもしれません。しかし、エクセルも、2つの値間でべき乗計算を行う”^”は、減算を行う“-”より優先する仕様になっています。

　この2式には、”-” ”^” ”+”という演算子が登場します。そのうちの、”^”と”+”についてはすべて、左右の2値を使い演算を行う2項演算子です。ところが、”-”については、”= 0 - 1^2”では（被演算子が左右にある）2項演算子ですが、“= -1^2 + 0”については、（被演算子が左右の片方にしかない）演算で使う値が一個の単項演算子(Unary operator)として、エクセルの計算が行われます（図１(b)）。

“= -1^2 + 0”の”-”は、”-”の右側にある1を符号反転させる演算子で、エクセルが採用する演算子優先順では、単項演算子は二項演算子に優先します（図１(c)）。その結果として、-1^2+0は (-1)^2+0 として計算されて、1という値が出力されるのです。

コンピュータを広めた表計算ソフトが生まれた時代の計算順を調査しよう！

エクセルの演算順序が、一般的な代数式の計算順序と異なる仕様になった理由はわかりません。「エクセルが開発された当時、標準的に使われていたLotus 1-2-3との互換性を考えたのではないか？」とも思いたくなりますが、そうでもありません。

　なぜなら、Lotus 1-2-3では、エクセルと異なる-1^2=1という計算結果になるからです。また、1985年発売のエクセルの開発チームは、Lotus 1-2-3(1983年発売) に先行して1982年発売のMultiPlanも開発しましたが、Multiplanでもやはり-1^2=-1と計算していたからです。

　エクセルやMultiplanが発売当時を調べてみると、面白いことがわかります。表計算ソフトという形態を作り出したVisiCalcも、当時の表計算ソフトの用途と重なるところも多かったデータベースソフトdBaseでも、ビジネスプログラミング言語のCOBOLも、多くのソフトでエクセルと同じ演算結果を出力します（図2、図3）。 　そんな時代背景を踏まえれば、エクセルが「単項演算子―は2項演算子^に優先する」という仕様にしたということも、いたって自然にも思えてきます。

セル間の計算順序には「2つの方法」が使われている

　「セル間の演算を簡単にできる」のが、今ではエクセルに代表される表計算ソフトウェアです。だから、エクセル等が計算を行う際には、セル内の演算順だけでなく、セル間の計算順序もきちんと決まっていて、エクセルでは、2つの異なるセル間の計算方法が使われています。

「依存関係ごとに、値が定まるものから先に」の計算順

通常使われているセル間の計算順は、「セル間の依存関係を（ツリー構造で）辿り、値が定まっている“源流“から計算を順に行っていく」というものです。たとえば、セルB2に”=10-B3”、そしてセルB3に”6”という文字が入力されていたら、まずは「セルB2の前に、セルB3を定義する」という依存関係を持つグループの中で順番を生成した上で、セルB3を表す変数に値6を設定し、そしてB3で10-6という演算を行って、結果の4を格納するのです。もしも、ユーザーがどこかのセルを書き換えた時には、そのセルが属する依存関係のグループ内のみで、上流から下流に向かって計算が行われます。

アルファベット順＋Zの法則（左→右、上→下）の計算順

もうひとつのセル間計算順は、「通常の方法が使えない場合」に使われます。具体的には、自己参照（循環参照）が行われている場合、言い換えれば「依存関係を辿っていくと、いつの間にか自分に辿り着いてしまい、無限ループに陥る場合」に使われます。計算をするのに、自分（自セル）自身の値を入力（右辺値）として使う状況があるの？と感じられるかもしれません。けれど、方程式を解く必要がある場合など、自己を参照するような数式に対する計算ができると便利なことも多いのです。

　たとえば、x ==(2 -3 y) / 4, y == (5 – 6 x) / 7という一次連立方程式を解きたい場合、セルB1とB2をxと yだとした上で、それぞれに =(2 -3*B2)/4と =(5 - 6*B1)/7という式を入れてみます。すると、「循環参照が行われています・・・」という警告が出るので、設定を「反復計算を使う（計算回数はとりあえず100）」と変えて、反復計算を実行させる（F9を押す）と、x(B1)=-0.1, y(B2)=0.8と連立方程式の計算結果が求まります。

　反復計算を行う場合には、循環参照が行われている部分に対し、アルファベット順で前方のシートから、そして同じシート内では左から右へ・上から下への順で（A1からA行を左から右へ、次はB行を左から右へ…と）計算が行われます。そして、最大反復回数に達するか、各セルでの計算結果の変化値が所定の値を下回るまで、この計算が繰り返されるのです。

　循環参照による反復計算は、普通とは言えないかもしれません。とはいえ、方程式を解いたりする場合などには必須になることも多い計算手法です（＊この方法では、必ずしも計算が収束するわけではありません）。

表計算ソフトが生まれた頃は、反復計算方式が使われていた

表計算ソフトが登場したての’80前半、すべての表計算ソフトが、どのような計算であっても、反復計算方式を使っていました。もう少し正確に言えば、シートに含まれるセルに対して（Zの法則など）所定の順番で計算を行い、値が変わらなくなるまでユーザが手動で計算を繰り返していました。

　「値が変わらなくなるまで再計算を行う」必要がなぜあるかというと、他のセルを参照する計算式が使われている場合、セルの並び順によっては「参照先を辿る回数」の再計算を行わなければ、最源流のセル値が最下流のセルまで反映されないからです（図4）。そのため、初期の表計算ソフトを使う際には、セルの値を見ながらユーザが計算を繰り返さなければならなかったのです（図5）。

　最源流のセルから下流へと「依存関係に沿って計算していく方式」が一般的に用いられるようになってから、各セルに対し1回の計算だけで結果が得られるという、現在の表計算ソフトの形態に落ち着いたのです。

表計算の計算方法を提案する「幻の基本特許」が存在していたが…

「依存関係を踏まえ、上流セルから計算を行う」という表計算ソフトの土台ともなっている演算手法ですが、実は「幻の基本特許」があります。

今の表計算ソフトの原型となったVisiCalcが登場する1979年より10年も前の1969年、LANPARというデータ操作言語が米国人Rene PardoとRemy Landaにより開発されます。LANPARが採用した変数間の演算順序は、automatic forward referencing (natural order calculation)と呼ばれ、「値が定義されているものから先に計算を行う」という表計算の計算順序に関する基本アルゴリズムと言えるものでした。

申請から13年を経て成立した特許で、さらに6年後に訴訟開始

PardoとLandaは、1970年に計算手法に関する特許申請を行いましたが、「技術の内容説明が不足」という理由で申請は却下されます。しかし、彼らは特許成立に向けた活動を続け、「プログラミングに関わる一般知識を持つ通常の人であれば、特許で公開された内容から技術を再現できる」とする一般の3名のプログラミング経験者による宣誓書を提出することで、特許申請から13年を経た1983年、米国特許4,398,249号としてようやく認めさせます（図6）。

そして、すでに表計算ソフトが必需品となっていた1989年、Pardoらは、「1ヶ月以内に少なくとも2名の特許侵害者を訴える」という条件付きで、パテント・トロール企業として有名なRefacに特許権利の5％を譲渡します。Refacは、デジタル時計の表示に関する特許、「時と分表示の間にあるコロンを点滅させる」というフラッシュ・コロン特許で、日本企業を中心に100億円以上の特許使用料を得た企業です。

そんな経緯を受けて、Refacは表計算ソフトを販売していた6社、Lotus(Lotus 1-2-3), Microsoft(Excel), Borland(Quattro), Ashton-Tate(Full Impact), Computer Associates(SuperCalc), Informix(Wingz)に対して、膨大な特許使用料を請求する訴訟を起こします。権利期間17年にわたる特許使用料として、膨大な金額を請求する訴訟です。

「特許内容は十分」と宣誓したプログラミング経験者、実は…

「表計算ソフトの基本特許は、膨大な特許使用料を生み出した」という結末を迎えたかというと…そうではありませんでした。その訴訟の結果は「大どんでん返し」で終わります。

1989年に始まる審判で、「Pardoらの特許申請には不正があり、権利無効である」とLotusが主張したのです。どういうことかというと、「特許内容は十分詳細である」と証言したプログラミング経験者というのが、実はLANPERの開発経験を持つ関係者で、その事実を特許商標局に対して隠していたというのです。「特許申請に対して全く前提知識を持たない人であっても、技術内容を理解できる」という意見を述べる宣誓であるはずが、実はそうではないものを提出していたことを「不正」と判断されたのです。そして、1996年、表計算ソフトの演算手法に関する基本特許とも言える米国特許4,398,249号は、「権利を行使できない幻の特許」と決定されたのでした。

表計算ソフトの演算順…そこには「面白い歴史」が詰まってた

個人でコンピュータを使えるようになった20世紀の後半も、あるいはＰＣがあたりまえの道具になった21世紀の今現在も、その価値や原動力となっているのが表計算ソフトです。そんな表計算ソフトの演算（計算）順を今回は調査してみました。意外なほど、たくさんのエッセンス、とても興味深いコンピュータの歴史がそこには詰まっていました。