Use of pow with Int exp

[NoahTheDuke]

Is it possible to add a version of Int::pow that accepts another Int as the exponent?

let n = Int::from(53174392371729765229371175317439237172976522937117);
let new_n = 8 * Int::from(2).pow(n - 1) + 5;
// instead of
let new_n = 8 * (Int::zero()..n).fold(Int::from(2), |acc, _| acc * 2) + 5;

Thanks!

[rozbb]

The reasoning for not allowing an Int as an exponent is because raising anything to a power that's greater than usize::MAX is simply infeasible.

For example, the above code snippet doesn't compile because the integer literal provided to Int::from exceeds usize::MAX. I changed it to a string and called from_str_radix. After about 10min of runtime, the program still hadn't terminated.

Notably, pow_mod does support Int exponents, because calculating powers with a modulus can be done quite efficiently.

PS: Sorry for taking so long to respond to this

[NoahTheDuke]

No worries on the time! Thanks for responding.

The reason I was asking is because I was trying to optimize an implementation of the Ackermann function, well beyond the basic levels, by directly calculating the values of higher ms. I'd have to find the old Python code I wrote, but it could do something very similar to my desired code above, because it boxes all numbers and has fancy behind-the-scenes work on handling unbounded numbers.

Thanks for all the hard work on this library!

[rozbb]

Ah ok. I'd like to see the code if you ever find it.

[NoahTheDuke]

I seem to have thrown away the Python code, but you can see the Rust code here, very clearly in the ack_with_struct formulation, if paired with the Wiki page.

In a bit of messing around, I tried implementing the values directly instead of recursively, as shown in the Wiki Table of Values, but getting it when m = 3 or m = 4 was difficult without being able to pass in an extremely large number. So I just left it out.

[rozbb]

Ah I see. I'm surprised you were able to compute some of these values at all, although I don't really know what exactly is feasible on a modern computer.

[NoahTheDuke]

Here's the Python code I couldn't make run with ramp, straight from Rosetta Code:

def ack2(M, N):
   return (N + 1)   if M == 0 else (
          (N + 2)   if M == 1 else (
          (2*N + 3) if M == 2 else (
          (8*(2**N - 1) + 5) if M == 3 else (
          ack2(M-1, 1) if N == 0 else ack2(M-1, ack2(M, N-1))))))

You can put M=3 and some very large numbers in for N (up to about 100000), and it'll produce an answer almost immediately. However, it does look like the number I gave above doesn't work with that python snippet. I remember trying it with that or a similarly large number and it being blazing fast. I don't know what I did to make it that fast, however.