Apple製品が美しい理由。ビル・アトキンソンのアルゴリズムを紐解く

お手持ちのAppleデバイスの「角」をよく見ていただきたい。なんともいえない美しい曲線が使われているだろう。これは「3次ベジェ曲線」で構成されていて、この美しさがAppleデバイスを特別なものにしている。

その原点は、1980年代初頭、Macintoshの前身であるLisaの開発にまで遡る。

人類史上もっとも美しい数式は「オイラーの等式」。では、Apple史上もっとも美しいアルゴリズムは何か

人類史上、もっとも美しい数式は「オイラーの等式」であるといわれる。自然対数、虚数単位、円周率という異なる分野で生まれた定数を、数の中で極めて基本的な0と1を使ってシンプルな等式で結びつけたこの式には、宇宙の深淵をのぞいたかのような神秘さを感じる。

人類史上もっとも美しいと言われるオイラーの等式。異なる分野で確立された定数である自然対数、虚数単位、円周率をシンプルな等式で統合した。

ところで、Appleはこれまでさまざまなハードウェアとソフトウェアを開発してきたが、その中で「もっとも美しいアルゴリズム」は何だろうか。筆者は、ビル・アトキンソンの円描画のアルゴリズムを推したい。

今日のMacの源流にあたるコンピュータは、1983年に発売されたLisa（リサ）だ。このLisaに、現在のmacOSの源流にあたるグラフィカルなユーザインターフェイス（GUI）が初めて搭載された。このGUIを開発したのがビル・アトキンソンだ。

「LisaGraf（のちのQuickDraw）」。多彩なアイデアが詰め込まれたビル・アトキンソンの描画エンジン

ビル・アトキンソンは、GUIを開発する際に、まず矩形や円、直線といった基本図形を描くライブラリ「LisaGraf」を開発した。ダイアログやウインドウを描くとき、いちいちプログラムで指定するのではなく、LisaGrafの関数を呼び出すことで簡単に描画できるようにするためだ。

LisaGrafはその後、QuickDrawと改称され、2005年までMacの描画エンジンとして使われた（その後、Core Graphicsに刷新をされた）。今日のMacの発展があった要因のひとつは、このLisaGrafが高速でダイアログやウインドウを描画できたことが大きい。

ところが、当時のCPUであるモトローラー68000は、今日のMシリーズチップなどとは比較にならないぐらい演算速度が遅く、小数点のある数は扱えず、整数演算の命令しか用意されていなかった。その中で、演算量の多いグラフィックをどうやって高速に描くかが大きな課題になった。

「プログラマーは楽をするためであれば、どんな苦労も厭わない」という、マイクロソフト創業者のビル・ゲイツ氏の名言があるが、ビル・アトキンソンも“楽をする”ために、あらゆるアイデアを総動員した。

円周上のピクセル点灯し、“円を描く”。当時の限られたCPU性能で、対象をどのように求めたのか

当時のLisaのディスプレイ解像度は、720×360ピクセルしかなかった（現在の24インチiMacは4480×2520ピクセル。Lisaの約43倍の広さになる）ため、円を描くというより、円周に沿ってピクセルを点灯させることぐらいしかできなかった。

しかし、この計算を円周すべてに対して行うような面倒なことはしない。なぜなら、円の4分の1を求められれば、あとは座標の符号を変えれば残りの4分の3の座標がわかるからだ。端的に言えば、4分の1だけ計算し、あとは反転コピーすればいい。これで、演算量は4分の1に減る。

当時はディスプレイ解像度が低いため、円を描くといっても、円周上にあるピクセルを点灯させることしかできなかった。図は半径8ピクセルの円。円周上にあるピクセルをどうやって特定するかが問題になった。

そうするには円周上の点をすべて計算で求めるしかない。ただ、1点を計算すれば、残りの3つの点は座標の符号を変えばわかる。計算するのは全体の4分の1で済むのだ。

…といいたいところだが、実は4分の1も計算する必要はない。8分の1だけ求めて、あとはxとyの座標を入れ替えると、隣の8分の1の座標がわかる。つまり、計算は円の8分の1だけ行い、座標を交換、反転することで残りのピクセルの座標を求めていった。

さらによく考えると、全体の4分の1も計算しなくて済むことがわかる。円の8分の1のピクセルを求めれば、座標を入れ替えることで残りが求められる。計算するのは円全体の8分の1でよくなる。

“始まりの点”はすぐ決まる。以降は右隣か右下か、判別の繰り返し

問題は、円の8分の1に当たるピクセルの座標をどのように求めるかである。出発点を、時計でいう「12時」にすることは誰も異論がないはずだ。x=0、y=半径なので簡単に求められる。次に、右隣のx=1のときの座標はどうすれば求められるのだろうか。

このとき、可能性があるのは、水平に1つ移動した座標か、あるいは右下に移動した座標のいずれかしかない。右にひとつ移動し、2つ下がったところの座標はあり得ないのだ。求めようとしている座標は、円の8分の1内のどこかなので、傾きが-1/2を超えることは絶対にない。右隣か右下かを判別すれば、次の座標が決まる。あとはこれを繰り返していけばいい。

12時のピクセルは（1、半径）なのですぐに求められる。そして、その右隣は水平移動した右隣か、その下のピクセルしかない。どちらであるかを判別する方法があれば、円周上のピクセルが次々にわかる。

ちょっとした計算でも、当時のコンピュータには“酷”だった。高速化

どちらが“正解”なのか。その判別方法は、それぞれの点と仮想の円周との距離を求め、小さいほうを選択すればいい（ここから先の解説にはいくつか数式が登場するが、難しいことはしていない。中学で教わる数学の範囲内だ）。

ピタゴラスの定理を使って、点1、点2のそれぞれの距離を求めると下の式のようになる。平方根などが登場して複雑に見えるが、やっていることは点1、点2の原点からの距離を求め、そこから半径を引いているだけだ。ただし、この平方根を含む計算をさせるのは当時のコンピュータには酷な話だった。計算はできるが、時間がかかってしまう。ここをどう高速化するかが問題となった。

2つの点のどちらが近いかを判別する値。三平方の定理を使って、原点からの距離を求めて半径分を引いているにすぎない。2つの値のうち、小さいほうが正解となる。しかし、この程度の計算でも当時のコンピュータには荷が重かった。

演算の高速化の原理は、昔も今も基本的には変わらない。
（1）小数点のある実数をできるだけ扱わず、整数だけで済ます。
（2）掛け算、割り算という時間のかかる計算をできるだけ使わず、足し算と引き算で済ませる。
（3）特に、ループ（繰り返し）の中には複雑な計算を入れない。

この考え方は現在でも有効だ。掛け算、割り算に時間がかかるといっても、今の高速チップではマイクロ秒単位での違いでしかない。ただ、その代わりに機械学習やビッグデータを扱うことが多くなり、ループの繰り返し回数や扱うデータ数が飛躍的に大きくなっている。少しの差が積もり積もって大きな違いになるわけだ。

負荷軽減のため限りなくシンプルに。掛け算を排除したプログラム

まず、前述のL1、L2の式には平方根というややこしいものがあるので、これを外してしまおう。その理屈は、幾何学や統計学の教科書を読んでご理解いただきたい。ポイントは、２つの値の大小を知りたいだけ、ということ。大小の関係さえ変わらなければ、正確な値を求める必要はない。

演算の面倒な平方根を避けるため、2つの値をこうに定義する。大小を比べるだけであればこれで問題ない。

しかし、これでも2乗というややこしい計算が出てくる。

ここで重要になるのが、「xを1つ増やすとこの値はどれだけ増えるか」という考え方だ。たとえば、掛け算九九の三の段を表示するプログラムをつくるとき、多くの人は素直に「3×X」というプログラムを書くと思う。しかし、高速化のためには掛け算をできるだけ排除したい。

九九の三の段は「xを1つ増やすと答えは3ずつ増える」という性質に着目し、「y=y+3」というプログラムを書く。こうすると、高速の足し算だけで演算ができる。

このテクニックを使えば、L1の「xを1つ増やすとL1はどれだけ増えるか」を求めるのは簡単だ。xのときの値と「x+1」のときの値を引き算すれば、xが1増えるとL1は「2x+1」だけ増えるとわかる。そこでこの2乗を含んだ計算をバカ正直に行うのではなく、xを1増やすたびに、2x+1を加える計算をしていく。