nekolib/math/
mod_ackermann.rs

1//! Ackermann 関数。
2
3use super::mod_pow;
4use super::mod_tetration;
5
6use mod_pow::ModPow;
7use mod_tetration::ModTetration;
8
9/// Ackermann 関数。
10///
11/// 与えられた $(a, b, n)$ に対して $A(a, b)\\bmod n$ を返す。
12/// 自然数 $a$, $b$ に対して Péter--Ackermann 関数 $A(a, b)$ は次のように定義される。
13/// - $A(0, b) = b+1$,
14/// - $A(a+1,0) = A(a, 1)$,
15/// - $A(a+1, b+1) = A(a, A(a+1, b))$.
16///
17/// $\\gdef\\hyper{\\operatorname{hyper}}$
18/// 以下の性質が知られている。
19/// $$ a\\gt 0 \\implies \\hyper\_a(2, b+3)-3. $$
20/// ただし、$\\hyper\_a$ は $a$ 番目のハイパー演算子である。
21///
22/// # Idea
23/// $a\\le 4$ までは [`mod_pow`] や [`mod_tetration`] を用いて簡単に求められる。
24/// [`mod_tetration`] と同様に、指数部が十分大きくなると値が一定になるので、それを利用する。
25///
26/// $A(5, b) = \\hyper\_5(2, b+3)-3 = \\underbrace{{}^{{}^{{}^2\\cdots} 2} 2}\_{b+3\\text{ many}} - 3$
27/// となるが、$A(5, 0)$ は現実的な値として求められる。
28/// $$ \\begin{aligned}
29/// A(5, 0) &= {}^{{}^2 2} 2 - 3 \\\\
30/// &= {}^4 2 - 3 \\\\
31/// &= 2^{2^{2^2}} - 3 \\\\
32/// &= 2^{2^4} - 3 \\\\
33/// &= 2^{16}-3 = 65533.
34/// \\end{aligned} $$
35///
36/// 一方で、$A(5, 1)$ は次のようになる。
37/// $$ \\begin{aligned}
38/// A(5, 1) &= {}^{{}^{{}^2 2} 2} 2 - 3 \\\\
39/// &= {}^{65536} 2 - 3 \\\\
40/// &= \\underbrace{2^{2^{\\cdots^2}}}\_{65536\\text{ many}}-3.
41/// \\end{aligned} $$
42///
43/// ここで [`mod_tetration`] の議論を思い出すと、${}^b a \\bmod{n}$ は $b\\ge 2\\log(n)$
44/// であれば一定値となる。引数の型が [`u64`] である今、$b$ として意味があるのは高々
45/// $2\\log(2^{64}) = 128$ 程度であり、$A(5, 1)$ はそれを十分に上回る。
46/// すなわち、$A(5, 1)\\bmod n = A(4, 2\\log(n))\\bmod n$ として計算してしまってよい[^bd]。
47///
48/// さらに、$A(6, 0) = A(5, 1)$ などから、$a\\ge 6$ についても同様にでき、次のようにできる。
49/// - $A(0, b) \\equiv b+1 \\pmod{n}$,
50/// - $A(1, b) \\equiv b + 2 \\pmod{n}$,
51/// - $A(2, b) \\equiv 2b + 3 \\pmod{n}$,
52/// - $A(3, b) \\equiv 2^{b+3} - 3 \\pmod{n}$,
53/// - $A(4, b) \\equiv {}^{b+3} 2 - 3 \\pmod{n}$,
54/// - $A(5, 0) \\equiv 65533 \\pmod{n}$,
55/// - $A(5, b) \\equiv A(4, 2\\log(n)) \\pmod{n}$ for $b\\ge 1$,
56/// - $A(a, b) \\equiv A(4, 2\\log(n)) \\pmod{n}$ for $a\\ge 6$.
57///
58/// [^bd]: 32768-bit 整数を受け取るような状況ではよくなさそう。512-word
59/// の多倍長整数と思うとそこそこ現実的な気もする？ だとしても $A(5, 2)$ はもう現実的じゃなさそう。
60///
61/// [`mod_pow`]: fn.mod_pow.html
62/// [`mod_tetration`]: fn.mod_tetration.html
63///
64/// # Complexity
65/// |入力|時間計算量|
66/// |---|---|
67/// |$a\\le 2$ or $(a, b) = (5, 0)$|$O(1)$|
68/// |$a=3$|$O(\\log(b))$|
69/// |otherwise|$O(\\sqrt{n})$|
70///
71/// # Examples
72/// ```
73/// use nekolib::math::ModAckermann;
74///
75/// let n = 10_u64.pow(9);
76/// assert_eq!(2_u64.mod_ackermann(5, n), 13);
77/// assert_eq!(3_u64.mod_ackermann(7, n), 1_021);
78/// assert_eq!(4_u64.mod_ackermann(2, n), 719_156_733);
79/// assert_eq!(4_u64.mod_ackermann(3, n), 437_428_733);
80/// assert_eq!(4_u64.mod_ackermann(8, n), 432_948_733);
81/// assert_eq!(9_u64.mod_ackermann(9, n), 432_948_733);
82/// ```
83pub trait ModAckermann {
84    fn mod_ackermann(self, b: Self, n: Self) -> Self;
85}
86
87macro_rules! impl_uint {
88    ($t:ty) => {
89        impl ModAckermann for $t {
90            fn mod_ackermann(self, b: Self, n: Self) -> Self {
91                let sub_3 = |z| match n {
92                    1 => 0,
93                    2 => 1 - z,
94                    3 => z,
95                    _ if z >= 3 => z - 3,
96                    _ => z + n - 3,
97                };
98                match (self, b) {
99                    (0, _) => (b + 1) % n,
100                    (1, _) => (b + 2) % n,
101                    (2, _) => (2 * b + 3) % n,
102                    (3, _) => sub_3((2 as $t).mod_pow(b + 3, n)),
103                    (4, _) => sub_3((2 as $t).mod_tetration(b + 3, n)),
104                    (5, 0) => (65533_u128 % n as u128) as $t, // for u8
105                    _ => sub_3((2 as $t).mod_tetration(n, n)),
106                }
107            }
108        }
109    };
110    ( $($t:ty)* ) => { $(impl_uint!($t);)* };
111}
112
113impl_uint!(u8 u16 u32 u64 u128 usize);
114
115#[test]
116fn test() {
117    let n = 14_u64.pow(8);
118    let res: u64 = (0..=7).map(|a| a.mod_ackermann(a, n)).sum();
119    assert_eq!(res % n, 452_774_460);
120}
nekolib/math/mod_ackermann.rs

nekolib/math/
mod_ackermann.rs
