数学的プログラミングのすすめ（初心者向け）

概要

元々「数学が得意な人向けのプログラミング入門」として書いていたものですが、内容が膨らみすぎたので、一部を削って改再編したものです。
数学的な話はそれほど扱っていないので、言うほど数学的な内容ではないかも知れません。

プログラミングに数学力が必要な理由

「$ 1 \leqq a \leqq b $ のとき、$ a $ 年から $ b $ 年までの間に、うるう年はいくつありますか？」

うるう年とは、以下のルールに基づいて決められる年のことです。

1. 西暦年が4で割り切れる年はうるう年。
2. ただし、西暦年が100で割り切れる年はうるう年ではない。
3. ただし、西暦年が400で割り切れる年はうるう年。

この質問を聞いたとき、数学力のなかった私は「一つずつ年を数え上げよう」と思いました。
そこで下のようなプログラムコードを作って計算しようとしましたが、実行速度が遅すぎて使い物になりませんでした。

    (* written in OCaml *)
    (* URL: http://ocaml.jp/ *)
    let rec range a b =
        if a > b then []
        else a :: range (a+1) b;;
     
    let (a, b) = Scanf.scanf "%d %d\n" (fun a b -> (a, b)) in
    let years = range a b in
    let uruu = List.filter (fun x -> 
    						((x mod 4) == 0)
    						&& ((x mod 100) > 0)
    						|| ((x mod 400) == 0)) years in
    print_int (List.length uruu);
    print_newline()

パッと見て、多分何が書いてあるのかさっぱりわからないと思います。
このコードの意味を理解する必要はありませんが、この方法だと合計 $ b - a $ 回の計算が必要になる事に注意してください。
通常はこれでも良いのですが、扱う数字が大きい場合や組み込み機器の場合、計算に非常に時間がかかってしまいます。

この計算は、以下の方法でずっと速く行う事が出来ます。

    # written in Ruby 2.x
    # URL:https://www.ruby-lang.org/ja/
    (a,b) = gets.chomp.split(" ").map {|n| n.to_i}
    
    a -= 1
    (auruu, buruu) = [a,b].map { |x| x / 4 - (x / 100).to_i + (x / 400).to_i }
     
    print (buruu - auruu).to_s, "\n"

このプログラムコードは上の物とは全くアプローチが違い、ある数式によりうるう年の数を導き出しています。
3行目をご覧いただければ何となく分かるかもしれませんが、このコードは、以下の数式をもとに記述されています。

f(x)=\frac{x}{4}-\left\lfloor \frac{x}{100}\right\rfloor+\left\lfloor \frac{x}{400}\right\rfloor

ここで、記号$ \lfloor \rfloor $はガウス記号(小数点以下切り捨て)をあらわします。
この式を用いると、除算を利用して、 $ 1～x $ 年の間のうるう年の数を算出する事が出来ます。
b-aこの年を全検索する方法に比べ、この計算式を使用すればたった一回の計算でうるう年の数を算出する事が出来ます。
たったこれだけのコードで、わかりやすく、しかも動作が速い処理が書けてしまうのです。

実装例：フィボナッチ数列

それでは、実際にプログラミング言語で数学関数を記述する例を紹介します。
使用する言語はどれでも良いのですが、ここでは試しに、数学的な記法に近いとされている**関数型言語Haskell**を用いて、フィボナッチ数列を表す関数を記述してみます。
フィボナッチ数列とは、下記の定義に基づく数列のことです。

F_n=
\begin{cases}
0 &(n=0) \\
1 &(n=1) \\
F_{n-1}+F_{n-2} &(n \geq 2)
\end{cases}

この数式をHaskellの構文を用いて記述すると、以下のようになります。

    fib :: Integer -> Integer
    fib n
        | n == 0    = 0
        | n == 1    = 1
        | n >= 2    = fib (n-1) + fib (n-2)

これはパターンマッチという構文で、nの値により結果を分岐させる動作を行います。 =が２つ連続しているのは右側の=と区別するためです。

5行目の後半に、関数名と同じ文字列が表れていることに注目してください。
これは再帰呼び出しといい、「指定された引数を伴ってもう一度この関数を評価する」という動作をします。
試しにfib 3を評価した場合、条件判断によりfib 2 + fib 1が導出され、最終的な答えは2となります。  
このように、自分自身を呼び出す関数のことを再帰関数と呼びます。

再帰関数の仕組みは非常に強力です。
以下のように、漸化式的な発想でアニメーションのような処理を作ることも出来ます（普通はしないけど･･･）¹。

    update n x y = do
                   -- （描画処理など）
                   update (n+1) (x+vx) (y+vy)
                   where
                       r = n * pi/180.0
                       vx = sin r
                       vy = cos r

最後に

今後は、ユークリッドの互除法などのアルゴリズムを中心に勉強していくと捗ると思います。
プログラミングに数学力を生かせていないという方は、よければご参考にしてみてください。

1. （'21 11/25追記）実際にHaskellのコードを書くときは、このような再帰の構文を書かずにStateモナドを使った方が良いです。　この記述はあくまで例示だと思ってください。 ↩