ジョセフの日記

Haskellのこととか日常のこととか

前回の巨大数プログラムのイメージ

前回、リスト操作による巨大数(?)を作りましたが、そのイメージについてメモを書こうと思います。

  1. m_0(x) = x+1
  2. m_0 : \mathbb{N} \to \mathbb{N} ; x \mapsto m_0(x)
  3. 関数の集合を特にM_0 = \{F_0 | F_0 : \mathbb{N} \to \mathbb{N}\}とし、次のように定めるM_{n+1}=\{F_{n+1} | F_{n+1} : M_n \to M_n\}
  4. m_{n+1} : M_n \times \mathbb{N} \to M_n \;; \; m_{n+1}(F_n,k) \mapsto F_n^k
  5. 関数m_{n+1}の引数に付いて次の略記を用いるm_{n+1}(F_n F_{n-1} \cdots F_0 (x) ) := m_{n+1} ( F_n \; ,\; F_n F_{n-1} \cdots F_0 (x))

この規則のもとで、Integerリストの要素が関数mの添字を表す。関数を引数に取る場合のカッコは略す。
例としては
 m_0 (x) = f(x)
 m_1^2 m_0 (x) = m_1 (m_1 m_0 (x)) = (m_1 m_0)^{m_1 m_0 (x)} (x)
 m_0 (F_0 (x) ) = f (F_0 (x))
\begin{eqnarray} m_3 m_4 m_3 m_2 m_1 m_0 (x) &=& m_3 ( [m_4 m_3 m_2] m_1 m_0 (x)) \\
&=&  [m_4 m_3 m_2] ^ {m_4 m_3 m_2 m_1 m_0 (x)} m_1 m_0 (x)\end{eqnarray}

ここでリスト操作関数(以下LO関数)というものを
 LO(x) = m(x) m(x-1) \cdots m(0) (x)
とし、LO数を
 LO := LO^{64}(3)
と定義する。64なのはiterate関数の仕様を勘違いしていた名残です。

構成法はほとんど同じなので、勝手にふぃっしゅ関数ver.5と同じぐらいの増加速度だと思っていますが、増加速度を下げる決定的な差があるのかもなど感じています。m_0の作用するタイミングはこちらのほうが早いはずなのでこちらのほうが増加が遅そうではあります。
一応参考にプログラムも載せておきます。
gist.github.com