I'm trying to understand how Rust handles int types and when arithmetic overflow occurs.
Here's code to do a powmod
function as an example, to understand when overflow occurs.
fn powmod(b : u128, e : u128, m : u128) -> u128 {
let (mut r, mut b, mut e) = (1, b % m, e);
while e > 0 {
if e & 1 == 1 { r = (r * b) % m }
e >>= 1;
b = (b * b) % m;
}
r
}
fn main() {
let mut b = 329832983;
let mut e = 4843;
let mut m = 498422;
println!("{}", powmod(b,e,m) );
b = 329832983;
e = 4433923223;
m = 583472714045;
println!("{}", powmod(b,e,m) );
b = 3298329804304383423;
e = 4433923224384234;
m = 2372095723823498422;
println!("{}", powmod(b,e,m) );
b = 902892829485298529845229485244241;
e = 543853278717814148138741341734140;
m = 39685272471287524758245784582458245485;
println!("{}", powmod(b,e,m) );
}
This code compiles with no errors, but the last group gives an overflow, though all fit in u128
.
107323
140323345317
1898779714053406193
thread 'main' panicked at 'attempt to multiply with overflow', powmod.rs:8:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Apparently it overflows when the (b * b)
is performed.
I assumed when that is performed the result is stored in a tmp variable
of twice the bit size,
and then brought back down with the (% m
) operation into a u128
size again. Apparently that's not what's happening.
Could someone explain how to do this correctly?
(I'm trying to understand, so don't reference a crate that does this)