Using the algorithm at the end of this research paper, I've written an extremely fast 1 Ackermann function in Rust. Can the implementation be made faster?
Thoughts:
- Using a struct makes a lot of sense, but it's weird to have to
Some(Box::new(v2))
. Can this be avoided in some way? - Are for loops the best way of doing the
v
transformations? Would(1..(i + 1)).fold(Record::new(1, 0, None), |v, k| a_use_p(k - 1, 1, v))
be more "Rustic"? It seems slightly faster, but that's hard to tell. - Is there a way to parallelize this? Or any part of it?
Thanks.
extern crate time;
use time::PreciseTime;
fn main() {
let m = 3;
for n in 1..20 {
let s = PreciseTime::now();
let res = fast_ackermann(m, n);
let e = PreciseTime::now();
println!("a_opt(3, {}) -> {} took {}", n, res, s.to(e))
}
}
#[derive(Clone)]
struct Record {
result: u64,
previous_result: u64,
cache: Option<Box<Record>>,
}
impl Record {
fn new(result: u64, previous_result: u64, cache: Option<Box<Record>>) -> Record {
Record { result, previous_result, cache }
}
}
fn fast_ackermann(m: u64, n: u64) -> u64 {
let mut cache = Record::new(1, 0, None);
for m_builder in 0..m {
cache = ack_with_incrementalization(m_builder, 1, cache)
}
for n_builder in 1..(n + 1) {
cache = ack_with_incrementalization(m, n_builder, cache)
}
cache.result
}
fn ack_with_incrementalization(m: u64, n: u64, current_cache: Record) -> Record {
if m == 0 {
Record::new(n + 1, 0, None)
} else if n == 0 {
let mut new_cache = Record::new(1, 0, None);
for m_builder in 0..m {
new_cache = ack_with_incrementalization(m_builder, 1, new_cache);
}
new_cache
} else if n == 1 {
let cache_result = current_cache.result;
let mut new_cache = current_cache;
for n_builder in 2..(cache_result + 1) {
new_cache = ack_with_incrementalization(m - 1, n_builder, new_cache);
}
Record::new(new_cache.result, cache_result, Some(Box::new(new_cache)))
} else {
let cache_result = current_cache.result;
let mut new_cache = *current_cache.cache.unwrap();
for n_builder in (current_cache.previous_result + 1)..(current_cache.result + 1) {
new_cache = ack_with_incrementalization(m - 1, n_builder, new_cache);
}
Record::new(new_cache.result, cache_result, Some(Box::new(new_cache)))
}
}
1 With m
= 3, n
= 20, the code takes 0.95 seconds. With n
= 30 it takes 16 minutes. In the paper, n
= 20 takes 5.05 seconds and n
=30 takes 87 minutes. A version with an intermediate cache (in Rust), n
= 20 took 2.1 seconds and n
= 25 (not 30 like the others) took 39 minutes.
a_opt
— make sure your code compiles ;-) \$\endgroup\$