Trait nekolib::math::ModAckermann
source · pub trait ModAckermann {
// Required method
fn mod_ackermann(self, b: Self, n: Self) -> Self;
}Expand description
Ackermann 関数。
与えられた $(a, b, n)$ に対して $A(a, b)\bmod n$ を返す。 自然数 $a$, $b$ に対して Péter–Ackermann 関数 $A(a, b)$ は次のように定義される。
- $A(0, b) = b+1$,
- $A(a+1,0) = A(a, 1)$,
- $A(a+1, b+1) = A(a, A(a+1, b))$.
$\gdef{\hyper}{\operatorname{hyper}}$ 以下の性質が知られている。 $$ a\gt 0 \implies \hyper_a(2, b+3)-3. $$ ただし、$\hyper_a$ は $a$ 番目のハイパー演算子である。
Idea
$a\le 4$ までは mod_pow や mod_tetration を用いて簡単に求められる。
mod_tetration と同様に、指数部が十分大きくなると値が一定になるので、それを利用する。
$A(5, b) = \hyper_5(2, b+3)-3 = \underbrace{{}^{{}^{{}^2\cdots} 2} 2}_{b+3\text{ many}} - 3$ となるが、$A(5, 0)$ は現実的な値として求められる。 $$ \begin{aligned} A(5, 0) &= {}^{{}^2 2} 2 - 3 \\ &= {}^4 2 - 3 \\ &= 2^{2^{2^2}} - 3 \\ &= 2^{2^4} - 3 \\ &= 2^{16}-3 = 65533. \end{aligned} $$
一方で、$A(5, 1)$ は次のようになる。 $$ \begin{aligned} A(5, 1) &= {}^{{}^{{}^2 2} 2} 2 - 3 \\ &= {}^{65536} 2 - 3 \\ &= \underbrace{2^{2^{\cdots^2}}}_{65536\text{ many}}-3. \end{aligned} $$
ここで mod_tetration の議論を思い出すと、${}^b a \bmod{n}$ は $b\ge 2\log(n)$
であれば一定値となる。引数の型が u64 である今、$b$ として意味があるのは高々
$2\log(2^{64}) = 128$ 程度であり、$A(5, 1)$ はそれを十分に上回る。
すなわち、$A(5, 1)\bmod n = A(4, 2\log(n))\bmod n$ として計算してしまってよい1。
さらに、$A(6, 0) = A(5, 1)$ などから、$a\ge 6$ についても同様にでき、次のようにできる。
- $A(0, b) \equiv b+1 \pmod{n}$,
- $A(1, b) \equiv b + 2 \pmod{n}$,
- $A(2, b) \equiv 2b + 3 \pmod{n}$,
- $A(3, b) \equiv 2^{b+3} - 3 \pmod{n}$,
- $A(4, b) \equiv {}^{b+3} 2 - 3 \pmod{n}$,
- $A(5, 0) \equiv 65533 \pmod{n}$,
- $A(5, b) \equiv A(4, 2\log(n)) \pmod{n}$ for $b\ge 1$,
- $A(a, b) \equiv A(4, 2\log(n)) \pmod{n}$ for $a\ge 6$.
Complexity
| 入力 | 時間計算量 |
|---|---|
| $a\le 2$ or $(a, b) = (5, 0)$ | $O(1)$ |
| $a=3$ | $O(\log(b))$ |
| otherwise | $O(\sqrt{n})$ |
Examples
use nekolib::math::ModAckermann;
let n = 10_u64.pow(9);
assert_eq!(2_u64.mod_ackermann(5, n), 13);
assert_eq!(3_u64.mod_ackermann(7, n), 1_021);
assert_eq!(4_u64.mod_ackermann(2, n), 719_156_733);
assert_eq!(4_u64.mod_ackermann(3, n), 437_428_733);
assert_eq!(4_u64.mod_ackermann(8, n), 432_948_733);
assert_eq!(9_u64.mod_ackermann(9, n), 432_948_733);32768-bit 整数を受け取るような状況ではよくなさそう。512-word の多倍長整数と思うとそこそこ現実的な気もする？ だとしても $A(5, 2)$ はもう現実的じゃなさそう。 ↩