チクタクの加速度とガウス少年の計算法
eToys の基本的な考え方にチクタクと時計の進む間に、ちょっとづつ量を増やしたり減らしたりして、物理的な振る舞いの真似をするという物があります。一方、物理の時間に習うやつは、ものの座標を時刻の関数で表現して、ある時刻の位置を求めるという物です。
eToys の方式はとても理解しやすく作るのが簡単な一方で、物理の方式は時間を単なる変数として扱うので、深い分析をするのに向いています。では、その二つの表現の間に、果たしてどんな関係があるのかというのが、繰り返しここに書いてきた問題です。
「加速度を持って進む車」を考えます。ステップごとに 1 ずつ速度が増えて行くスクリプトはこんな感じでしょうか。
- [くるまの][そくどに以下を足す][1.0]
- [くるま][を進める][くるまの][そくど]
これを以下のように haskell で再帰的に書く事も出来ます。つまり、最初の位置、時刻 0 の時の位置が 0 で、それから t * 1 ずつ、つまり時刻が増えるたびに 1 ずつ速度が増えて行くわけです。再帰が入ると急に難しく感じられますが、アイデアとしては上の eToys タイルの方法と全く同じです。
- acceleration1 0 = 0
- acceleration1 t = acceleration1 (t - 1) + t * 1
t が 0 から 10 まで動く時、位置は以下のようになります。
- acceleration1 0 = 0
- acceleration1 1 = 0 + 1 = 1
- acceleration1 2 = 1 + 2 = 3
- acceleration1 3 = 3 + 3 = 6
- acceleration1 4 = 6 + 4 = 10 .. (途中省略します)
- acceleration1 10 = 45 + 10 = 55
1 + 2 + 3 + 4 ... と同じですね。一方、数を順序良く足し合わせる方法としては、ガウス少年の有名な方法があります。例えば t = 10 の時の位置を求めるのに、1 + 2 + 3 + ... と足していく代わりに (10+1) + (9+2) + (8+3) + .. と最初と最後のペアから足すわけです。それぞれのペアは全部同じ数なので、掛け算を使って 11 * 5 、つまり、(t + 1) * t / 2 でさくっと求まります。
- acceleration2 t = (t + 1) * t / 2
この関数は、同じ意味なのに再帰がありません。ループ無しで一瞬に答えが求まります。さて、今日の問題は、acceleration1 のような再帰を含む関数から、acceleration2 のような再帰の無い関数を求める一般的な方法があるかという話です。
面積の計算と奇数の数列
もう一つ例を挙げます。一辺の長さが x の正方形の面積はいくつになるでしょうか? 答えはもちろん x の二乗です。
- square2 x = x * x
が、もしも我々が掛け算を知らず、足し算だけでこれを求めるとすれば、このような方法をとるかも知れません。
- square1 0 = 0
- square1 x = square1 (x - 1) + 2 * x - 1
これは正方形のタイルかなんかを並べるとすぐ分かるのですが、まず最初タイルが何にも無ければ勿論面積はゼロです。次に、タイルが一つなら面積も 1 です。さらにタイルを縦横二つずつ並べる為には、あと三つ(2 * 2 - 1) 必要で、縦横三つずつの為にはさらにあと五つ(2 * 3 - 1) 必要になります。なぜなら縦の分三つ並べ、横の分三つならべ、縦と横が重なる部分一つを取り除くからです。こうして足し算を繰り返し使って面積を求める事が出来ます。
- square1 0 = 0
- square1 1 = 0 + 1 = 1
- square1 2 = 1 + 3 = 4
- square1 3 = 4 + 5 = 9
- square1 4 = 9 + 7 = 16
- square1 5 = 16 + 9 = 25
じつはみんな何の気なしにこうした奇数の数列と二乗の関係について知ってるはずなんですが、まあ、深く気にする事なく大人になるわけです。だけどやはりここには何かの意味があるはずなのです。
証明
個々の例について証明してみます。
t >= 0 の 整数 t で、acceleration1 t = acceleration2 t の証明
-- t = 0 のとき acceleration2 t = (t + 1) * t / 2 acceleration2 0 = (0 + 1) * 0 / 2 = 0 -- t > 0 のとき acceleration2 t = (t + 1) * t / 2 acceleration2 t = (t * t + t) / 2 = (t * t - t + 2 * t) / 2 = (t - 1) * t / 2 + t = ((t - 1) + 1) * (t - 1) / 2 + t = acceleration2 (t - 1) + t
x >= 0 の整数 x で、square1 x = square2 x の証明
-- x = 0 のとき square2 0 = 0 * 0 = 0 -- x > 0 のとき square2 x = x * x = x * x - 2 * x + 1 + 2 * x - 1 = (x * x - 2 * x + 1) + 2 * x - 1 = ((x - 1) * (x - 1)) + 2 * x - 1 = square2 (x - 1) + 2 * x - 1
一般解を求める。
という事で、個々の例については再帰関数からそうでない関数に変換可能な事が分かりましたが、全部の再帰関数がそうとは限りません。と言ってもいきなり全部の再帰関数について調べるのは大変なので、とりあえず次の形をした再帰関数について考える事にします。
- f1 0 = 0
- f1 x = f1 (x - 1) + p * x + q
つまり、一つ前との差分が一次関数の形をしている物です。差分が一次式なので、何となく非再帰バージョンは二次関数じゃないかと当てをつけてみます。求めるべき関数は以下の形をしているはずです。
- f2 x = a * x * x + b * x + c
ここで、a、b、c を p と q で表す事が出来たら成功です。途中はしょって要点だけ書きます。
- x = 0 のとき、f2 0 = 0 より
- a * x * x + b * x + c = 0
- c = 0
- x = 1 のとき、f2 1 = 0 + p * x + q より
- a + b = p + q
- f2 x = f2 (x - 1) + p * x + q より
- a = p / 2
- b = p / 2 + q
という事で、
- f2 x = p / 2 * x * x + (p / 2 + q) * x
が求める答えです。
p も q も引数という事にすると、加速度と面積の関数はさらに次のように書く事が出来ます。
f2 x p q = p / 2 * x * x + (p / 2 + q) * x acceleration3 t = f2 t 1 0 square3 x = f2 x 2 (-1)
まとめ
まず最初に、eToys のチクタクによるシミュレーションは、意味的に再帰関数であるという事を説明しました。次に、ある再帰関数は再帰を使わない関数に変換可能である事を示しました。それから、差分が一次関数である再帰関数について、一般解を示しました。
まだ僕の頭の中で熟していないので、どうも説明が難しくなりました。ごめんなさい。ここでやりたかった事は eToys のシミュレーションと高校数学の間に道筋を付ける事です。eToys で加速度のプログラムを書くと、確かに加速度があるように見えるのですが、本当にそれが加速度なのか、どれくらい正しいのかについて考えると結構難しいです。ここで取り上げた方法を使うと、例えば加速度なら eToys の (t + 1) * t / 2 に比べて積分なら t * t / 2 だから、t / 2 の分だけ誤差だなとか、正確に考える事が出来るわけです。
今回は t が整数の場合、つまり非連続の時間についてだけ書きましたが、acceleration1 (t - 1) の -1 が実数の場合について考え始めると、さらに面白くなります。ここが無限と連続の入り口です。
参考
これは以下の日記の続きです。
- フォーマルなタートル幾何学: http://d.hatena.ne.jp/propella/20060326/p2
- 恥ずかしくて人に聞けない位置と時間: http://d.hatena.ne.jp/propella/20050301/p1
あとで絵を描く予定。。。
