Why does Rust's u64.pow expect a u32?

Question

Why is it that Rust's u64 primitive expects a u32 exponent?

error[E0308]: mismatched types
  --> src/protagonists.rs:13:25
   |
13 |         return root.pow(self.secret) % prime;
   |                         ^^^^^^^^^^^ expected u32, found u64
help: you can convert an `u64` to `u32` and panic if the converted value wouldn't fit

https://doc.rust-lang.org/std/primitive.u64.html#pow.v

Answer 1

Why do most operations require operands of the same type?

It's easy for us to see that 2i32 + 2i64 should be 4i64, but to a CPU, 2i32 and 2i64 are completely different and totally unrelated things. + inside a CPU is really just a piece of hardware that typically supports two 32-bit inputs or two 64-bit inputs, but not one 32-bit input and one 64-bit input. So in order to add an i32 to an i64, the shorter number has to be sign-extended to 64 bits before both values can be plugged in to the ALU.

The same is generally true for most integer and floating-point arithmetic operations: A conversion has to be done to do math on mismatched types. In C, the compiler usually promotes both operands to the smallest type that can represent both values; these implicit conversions are called the "integer promotions" or "usual arithmetic conversions" depending on context. In Rust, however, the compiler mostly only knows about same-type operations, so you have to choose what kind of operation you want by deciding how to convert the operands. People who like Rust generally consider this to be a good thing.¹

Why doesn't this apply to u64::pow?

Not all arithmetic operations, even those implemented in hardware, accept arguments of the same type. In hardware (although not in LLVM), shift instructions often ignore the higher bits of the shift argument (this is why in C shifting by more than the size of the integer invokes undefined behavior). LLVM offers powi instructions that raise a floating-point number to an integer power.

These operations are different because the inputs are asymmetric, and designers often take advantage of these asymmetries to make hardware faster and smaller. In the case of u64::pow, though, it's not implemented with a hardware instruction: it's just written in plain Rust. Bearing that in mind, it's clear that requiring the exponent to be a u64 is quite unnecessary: As Schwern's answer points out, u32 is more than capable of containing all the possible powers that a u64 could be raised to with any hope of accuracy, so the extra 32 bits would be just pointless.

OK, why u32?

The last sentence is equally true of u16 or even u8 -- a u64 can't contain pow(2, 255), so using u32 seems nearly as wasteful. However, there are also practical considerations. Many calling conventions pass function arguments in registers, so on a 32-bit (or larger) platform you will not see any advantage from going smaller than that. Many CPUs also do not support native 8-bit or 16-bit arithmetic, so the argument would have to be sign-extended anyway to implement the exponentiation-by-squaring algorithm I linked to earlier. In short, I don't know specifically why u32 was chosen, but things like this may have factored into the decision.

---

¹ C's rules are somewhat encumbered by history and supporting a wide range of historical hardware. Rust only targets LLVM, so the compiler doesn't need to worry about whether the underlying hardware has a primitive 8-bit add instruction or not; it just emits add and lets LLVM worry about whether it will be compiled to a primitive instruction or emulated with 32-bit ones. This is why char + char is int in C, but i8 + i8 is i8 in Rust.

Answer 2

This is an educated guess.

Consider that a u64 raised to a u32 is already more than capable of overflowing any u64. For example, if we take 2 (the smallest possible significant u64) and raise it to merely 2^10 or 1024 we get something rather larger than a u64.

179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216

There's no point in allowing an even larger exponent, it just means a more expensive calculation that is more likely to overflow.

If a u64 cannot safely be downgraded to a u32, it definitely cannot safely be used as an exponent. u128.pow also only takes a u32 exponent for the same reason.

Note: there is overflowing_pow to detect a likely overflow.