数のお話

少し前にTwitterで話を振ったので、
補足としての記事を書こうと思います。

Lispでの数表現

理想的で(かつ一般的な)Lispの処理系は、
ここで記述するような数表現をサポートしているはずです。

数の表現は処理系自体の実装を困難にしたり、
ハードウェアのスペックを要求することもあるので、
処理系の制限を受けることもありますので注意してください。

数のクラス

自然数、整数、有理数無理数、実数、複素数・・・
数学の基礎を学んだ人ならご存知の通り、数にはクラスがあります。
Lispは歴史的背景から数学的な数表現を極力サポートしようと、
言語仕様に取り入れています。

  • 整数 - 0, -1, 100 etc.
  • 有理数 - 1/3, 0.5, -0.0001 etc.
  • 実数 - 3.141592... ,
  • 複素数 - a+bi

正確数と非正確数

計算機で無限の精度を表現することは不可能なので、
殆どの処理系が計算の途中で実装制限の精度が要求された時、
無理数に評価された時と言い換えることも出来る)
処理系が持つ浮動小数表現を用いて、
非正確な数(inexact-number)に変換されます。

逆に、そうでない場合は処理系は持ちうる精度を持って、
正確数であり続けようとします。
SchemeでもCommon Lispでも有理数がサポートされているため、
小数や除算の結果も基本的には正確数です。

(/ 1 3) ==> 1/3

Common Lispでは多倍長整数(bignum)がサポートされているため、
メモリが許す限りの精度で有理数を保存することは分けない事です。

numericalなベクタ

とは言っても、精度よりも速度が要求されることもあります。

そういった時、Common Lispであればfixnum宣言をすることで、
型チェックやbignumへの拡張を抑えて高速化できます。

Schemeであれば、srfi-4でhomogeneous numerical vectorがサポートされているので、
メモリ領域の節約や高速な演算が可能になると思われます。

他にも、処理系毎に基底となる数表現をサポートしているはずなので、
そちらを利用していくことになります。

Lispの最適化思想

いきなりハードウェア精度の数表現を使用する言語では、
以下のケースがしばしば発生しています。

  1. とりあえずFP32で計算を始める
  2. おかしい、計算結果が合わない・・・
  3. FP32では精度が不足していた、FP64で再実装
  1. とりあえずS32で計算を始める
  2. おかしい、計算結果が合わない・・・
  3. 桁溢れしていた、U32またはS64で再実装

まず、計算結果が正当かどうか確認することが困難ですが、
さらに精度誤差や桁溢れが原因だと識別することは熟練者の感頼りになります。
実装された計算プログラムが高速で動いても、
プログラムの検証に何倍も時間がかかってしまうでしょう。

Lispでは逆手順を踏みます。

  1. とりあえず計算を始める
  2. 計算量が増えてきたら、時間がかかるようになってきた
  3. 繰り返しなど頻繁に使用される箇所で桁や精度が要求されない箇所に(declare fixnum)を挿入
  4. 速度が十分になるまでチューニングを続ける

計算状況から計算誤差・桁溢れが発生している箇所を発見する事と、
実行時間が長い箇所を発見する事とどちらがより困難か、
語るまでも無いでしょう。