Something unexpected using wrapping_mul

1

Hi, I rarely use wrapping_mul in my code, but something looks fishy on the following snippet:

Godbolt

pub fn test() {
    let vec: Vec<u64> = vec![
        23, 24, 25, 29, 34, 36, 38, 41, 42, 45, 46, 47, 49, 51, 56, 58, 60, 61, 62, 63, 65, 69, 70,
        72, 74, 78, 79, 82, 84, 85, 86, 87, 89, 90, 94, 95, 99, 101, 102, 103, 104, 106, 112, 113,
        114, 117, 118, 122, 123, 124, 125, 126, 128, 129, 131, 132, 133, 136, 141, 147, 149, 154,
        155, 163, 167, 169, 171, 174, 175, 176, 177, 178, 180, 182, 188, 195, 198, 205, 206, 208,
        209, 210, 214, 215, 216, 217, 219, 220, 221, 222, 223, 224, 225, 230, 245, 246, 255, 256,
        258, 262, 273, 276, 277, 278, 279, 280, 284, 293, 294, 296, 298, 300, 301, 302, 310, 311,
        313, 315, 324, 325, 328, 330, 331, 333, 335, 336, 340, 341, 342, 345, 346, 347, 348, 350,
        351, 354, 356, 357, 358, 363, 366, 367, 368, 369, 370, 373,
    ];

    let mut sum = 1_u64;

    for val in vec {
        if val != 0 {
            let tmp = sum.wrapping_mul(val);

            if tmp != 0 {
                sum = tmp;
            }
        }
    }

    println!("Sum {}", sum);
}

I yields 9223372036854775808, and seems to lock before value 180 is reached with single bits values. Why is that? It looks like saturating instead of wrapping at some points. Makes the same thing with prior versions of rust. So it's my understanding failing me.

Thanks!

2

consider renaming sum to product to avoid confusion.

wrapping_mul works correctly, and definitely does not saturate.

when you reach 180, what happens is multiplying by an odd number gives itself (no change), and multiplying by an even number gives 0 (also no change).

this might help ?

    let mut prod = 1_u64;

    for val in vec {
        if val != 0 {
            let tmp = prod.wrapping_mul(val);
            println!("prev : {prod:#b}");
            println!("next : {tmp:#b}");

            if tmp != 0 {
                prod = tmp;
            }
        }
    }

    println!("Product {prod}");
2 Likes
3

Got it!
Thanks to your input, I spotted that the issue was the biased bits distribution toward the top bits and increasing up to the point only one bit was active, decreasing entropy.

Thanks,

4

The fundamental mathematical fact about modular arithmetic (which is what wrapping_mul does) that helps you better understand what’s happening here is that “wrapping” of intermediate results does not matter.

In other words: the result of doing a bunch of multiplication steps, wrapping around anything above a fixed value m at every step, yields the same result as doing the multiplications normally first (creating arbitrarily large integers) and only wrapping once at the end.

The next thing of note is that the fixed value we are wrapping above for u64 is, of course, a power of 2; specifically 264. If you consider all the numbers as binary numbers, then wrapping (aka taking the remainder of devision; aka the “modulo” operation[1]) with 264 is in turn equivalent to just cutting off anything but the last 64 binary digits.

Now, the number of trailing zero digits of any binary number is exactly the number of times 2 divides this number (or, the exponent n of the largest power of two 2n that is still a divisor of your number).

For your code it’s important to understand “when is the result of doing a wrapping operation equal to zero?” because that’s the condition on your inner if tmp != 0 expression. You can answer this question now: It’s going to be zero precisely in those cases where the last 64 binary digits of the non-wrapped (intermediate) result would be zero, which in turn is the case precisely in those cases where 2 divides your number (the non-wrapped intermediate result) at least 64 times.

With doing more and more multiplications, your number gradually adds more and more factors 2. (You can imagine this easily if you are familiar with prime decompositions; multiplying two numbers represented as a product of powers of prime numbers, like 26⋅34⋅72 × 28⋅53⋅7 just amounts to adding up exponents, yielding 26+8⋅34+0⋅50+3⋅72+1 = 214⋅34⋅53⋅73. Now you can focus just on the exponent on the 2☐ factor and ignore the rest.)

Whenever this exponent – the amount of times that your number can be divided by 2 – would reaches (or exceed) 64, you’d get a result of tmp == 0 after in your wrapped result, and hence your code decides to skip that factor instead and keep your number unchanged. This means that for any input vec that has sufficiently many numbers that are divisible by 2[2] you’ll eventually reach exactly 63, and then keep being stuck there. If you think about all possible concrete number that do have 63 factors 2, i.e. 63 trailing binary zeroes, in the type u64 itself, then there’s only one bit left in front of it, so only a single choice remains, the number 263 = 9223372036854775808 itself, as you already noted.

Here’s a playground showing your original logic, and then afterwards a second loop that will follow exactly the same kind of control flow, but instead operating just on the exponents of the prime factor 2, by adding them, and capping (through skipping of factors) right below 64: Rust Playground

  1. there are some subtle varieties of kinds of remainder operations when negative numbers are involved, but this doesn’t matter in this case, where all numbers are positive ↩︎

  2. and includes sufficiently many number sufficiently late that are divisible by 2 only once, so you’re guaranteed to be able to reach 63 exactly, not get stuck with some lower power of 2 ↩︎

7 Likes
5

i think you meant 63

6

Yes, my finger seems to have missed the 3 key slightly on that one :slight_smile:

It’s fixed now!

1 Like