BigInt Handling

code review
1

A useless computation - unknown terrain:

use num_bigint::BigInt;
use num_traits::*;

fn rosza4(m: BigInt, n: BigInt) -> BigInt {
    let mut stack: Vec<BigInt> = Vec::from([m.clone(), n.clone()]);
    while let Some(n) = stack.pop() {
        if let None = stack.pop() {
            return n;
        } else {
            match (m.to_string().as_str(), n.to_string().as_str()) {
                ("0", _) => stack.push(n + BigInt::from(1)),
                ("1", _) => stack.push(n + BigInt::from(2)),
                ("2", _) => stack.push(BigInt::from(2) * n + BigInt::from(3)),
                ("3", _) => {
                    let n = n.to_u32().unwrap();
                    stack.push(BigInt::from(2).pow(n + 3) - BigInt::from(3));
                }
                (_, "0") => {
                    stack.extend_from_slice(&[m.clone() - BigInt::from(1), BigInt::from(1)])
                }
                _ => stack.extend_from_slice(&[
                    m.clone() - BigInt::from(1),
                    m.clone(),
                    n - BigInt::from(1),
                ]),
            }
        }
    }
    unreachable!();
}

fn main() {
    let result = rosza4(BigInt::from(3), BigInt::from(1_000_000));
    println!("{}",result);
}

The output is impressive and the performance not bad. The code is a port from me of a Python version from Rosetta Code modified and optimized by conqp - slightly modifed (biginted) by me. quinedot helped with the match - which i also modified. All mistakes are mine.

Thanks for any hint.

2
  • It feels unnatural to convert a number to a string and then to a string slice just to match it against UTF-8 strings of digits. Consider using to_bytes_{l,b}e instead and matching those.
  • Since this still appears to be an implementation of the Ackermann- Péter function, you can use a more fitting type, namely BigUint, since you'll never deal with signed numbers.
  • Bug: You throw away m when popping it from the stack, thus always falling back to the initial value of m as passed as the function's parameter. Alternative:
let Some(m) = stack.pop() else {
    return n;
};

match ... {
    ...
}
1 Like
3

Ouch, but assert!(result == BigInt::from(65533)); passes for (3,13).

4

Sure, because with those parameters, there will be only one iteration. Try ackermann_peter(4, 1), which has 4 iterations.

1 Like
5

I see, yes. Thank you very much.

P.S. Great!