« 電子メールの証拠能力 | トップページ | メモリ嫌い »

float 嫌い

フルスクラッチによるグラフィックスプログラミング入門  amazon.co.jp で「フルスクラッチによるグラフィックスプログラミング入門 」という本を見つけて、ある種の感慨を覚えました。というのも、ぼくは若いころ、まさにこのようなグラフィック・ライブラリをゼロから作るような仕事を主にやっていたからです。

 その頃凝っていたのが、いかに浮動小数点を使わずにコードを書くかということ。というのは、その頃の CPU には、浮動小数点計算用のコプロセッサが装備されていなかった(もちろん、そういう計算をやってくれるグラフィック・ボードなんてものは陰も形もなかった!)ので、コードに浮動小数点の計算が入ると、格段にパフォーマンスが落ちるからです。

 その結果、努力の甲斐あって、最終的には、画像の回転、ベジエ曲線や B スプラインの描画など、すべて整数演算だけでやるアルゴリズムを開発しました。と書くと、ちょっとわかっている人だと、「回転なんて、三角関数が必要だから、無理に決まってんじゃん」などと思ってくれるかも知れませんが、それが甘い(^^)。

 そもそも、浮動小数点数などと言っても、実際には、普通の整数と変わらないビット列なのであって、それを計算する側の解釈で小数だとみなしているにすぎません。ですから、少なくとも「無理に決まっている」などということはないのです。また、浮動小数点演算ライブラリというのは、起こりうるあらゆる浮動小数点演算を想定して、その全体に対して最適化されているので、特定の種類の演算については、必ずしも最適とは言えないことがあるのです。

 たとえば、似たような桁数の小数の加減算だけしかやらないとあらかじめわかっていれば、固定小数点で計算した方が遥かに効率がよいでしょう。つまり、12.345 + 67.89 だったら、12345 + 67890 = 80235 とやってから、表示するときに小数点を挿入して 80.235 とやれば、整数だけしか使わないで計算することができます。

 もう一つ、大きなヒントになったのが、直線を描画するための有名な「ブレゼンハムのアルゴリズム」というやつ。これは、コードだけを見てもなんのことだかわかりにくいかも知れませんが、本質的には、有理数の演算を、「固定分母の分数」に直してやっているのです。 

 たとえば、(0, 0) と (4,3) を結ぶ直線を引く場合、x 座標を 1 ずつ増やしながら、対応する y 座標を計算していくことになります。この直線の傾きは 3/4 ですから、x が 1 増加すると、y は 3/4 増加することになります。これを、0.75 ずつの増加とやってしまうと、浮動小数点が必要ですが、3/4 という分数のままで計算すれば、浮動小数点は必要ありません。

 さらに、汎用的な分数演算パッケージだと、3/4 + 3/4 = 6/4 = 3/2 と約分されてしまいそうですが、考えてみると、今後も加算するのは 3/4 ばかりなのですから、こんな約分はしない方が効率的です。したがって、分子だけを加算していって、分子が分母を超えたら、1 繰り上がるという処理をすればよい。これが、ブレゼンハムのアルゴリズムの本質です。

 このことに気づいたとき、この原理がいろんなアルゴリズムに応用できるということに気づきました。ベジエ曲線なんかも、基本的には有理数の演算なので、分数演算に直せます。さらに、ベジエ曲線は、有限次元の多項式ですから、高階の差分をとっていくと、いつか定数項だけになります(離散数学に疎い人は、テイラー展開を思い出そう。本質的には、あれと同じことです。ただ、微分だと、微分方程式の数値解法と同じことになって誤差が出るので、差分で厳密に計算するわけ)。したがって、掛け算も必要なくなります。また、分母は刻み幅を決めているだけですから、2 の n 乗になるように勝手に決めてしまえば、最後に分母で割るところすらもビットシフトに直せます。したがって、最終的には整数の加減算だけで描画できるのです。

 ただ、当時の文献には、ベジエ曲線の差分展開の式などどこにも載っておらず、計算の苦手な私は、この差分展開の式を、計算用紙数枚を費やして、やっとのことで導き出した記憶があります。このアルゴリズムを、当時の 8086 か 80286 ぐらいのマシンで動かしたところ、それまで描画する過程が見えるくらい遅かったベジエ曲線の描画が、一瞬でできるようになり、めちゃめちゃ感動しました。もっとも、同じ分野で仕事をしている同僚がいなかったので、他のプログラマは、私がなんでそんなに興奮しているのか、まったく理解できなかったようですが。。。(^^)

 ここで、「ベジエ曲線は確かに有理数だけで計算できるけど、画像の回転は実数計算が必要じゃないの」と思った人、やっぱり甘いです(^^)。だって、浮動小数点数なんていったって、有効桁数は有限なんだから、厳密な意味で言えば実数ではなく、結局は有理数の近似計算なんですよ。もっとも、e-30 とかになると、分母や分子の桁数が大きくなりすぎて実用的ではありませんが、幸い、画面上のビットマップ座標にも、色空間の座標にも、どうせそんな数字は出てこないのです。ですから、分数でも、少なくとも浮動小数点パッケージと同じぐらいの精度で計算することは十分可能なのです。

 今や、一般のプログラマにはまったく必要なくなってしまった obsolete な技術ですが、物好きな人は、頭の体操として考えてみてはいかがでしょうか(^^)。

|

« 電子メールの証拠能力 | トップページ | メモリ嫌い »

パソコン・インターネット」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/67762/8731572

この記事へのトラックバック一覧です: float 嫌い:

« 電子メールの証拠能力 | トップページ | メモリ嫌い »