Tracking Issue for "widening" multiplication methods

[clarfonthey]

Feature gate: #![feature(bigint_helper_methods)] (for now)

This is a tracking issue for the widening_mul methods on integers.

Public API

impl uN {
    const fn widening_mul(self, rhs: uN) -> (uN, uN);
}
impl iN {
    const fn widening_mul(self, rhs: uN) -> (iN, iN);
}

Steps / History

(Remember to update the S-tracking-* label when checking boxes.)

• Previous tracking issue Tracking Issue for bigint helper methods #85532
• Update for latest API: Widen the result of widening_mul. #156644
• Final commenting period (FCP)

Unresolved Questions

• The return type of this method is the main concern.

[Amanieu]

We discussed this in the @rust-lang/libs-api meeting while discussing rust-lang/libs-team#738. We would like to see widening_mul return a wider integer type instead of a pair of integers, and simply not have these methods available on 128-bit integers. This is what makes the most sense given the method name.

[clarfonthey]

I think that's extremely fair, given the fact that this is technically available via carrying_mul on 128-bit integers anyway, as long as you pass zero for the carry.

[gendx]

Another case where widening multiplication is useful is to implement division by a constant. Typically, something like:

fn div3(x: u32) -> u32 {
    x / 3
}

is replaced by LLVM optimizations by something like:

fn div3(x: u32) -> u32 {
    const MAGIC: u32 = 2863311531;
    const MAGIC_SHIFT: u32 = 33;
    ((x as u64 * MAGIC as u64) >> MAGIC_SHIFT) as u32
}

As you can see, this requires a widening multiplication using u64. With the current function signature returning a pair of values, this can be rewritten without even mentioning u64 (in practice the MAGIC_SHIFT is always >= 32, so we only care about the high word of the widened multiplication).

#![feature(widening_mul)]

fn div3(x: u32) -> u32 {
    const MAGIC: u32 = 2863311531;
    const MAGIC_SHIFT: u32 = 1;
    x.widening_mul(MAGIC).1 >> MAGIC_SHIFT
}

Of course, we don't need to worry about this when the divisor is a compile-time constant. However, the technique is still applicable and useful when the divisor is a runtime constant, i.e. when we know we'll divide many values by the same divisor. This is for example what the libdivide C++ library offers, partially ported to the libdivide crate (where indeed, the mulhi() concept appears).

One practical example where this is useful is when repeatedly indexing in a slice modulo the length of the slice.

fn foo(s: &[T]) {
    for i in ... {
        let value = s[i % s.len()];
        ...
    }
}

In this case, the divisor (hidden in the modulo) is a usize. The problem here is that there is no wider type for usize, i.e. the approach of returning a wider type as outlined in #152016 (comment) wouldn't work.

We would like to see widening_mul return a wider integer type instead of a pair of integers, and simply not have these methods available on 128-bit integers. This is what makes the most sense given the method name.

In this case, we really need a widening multiplication on usize that returns a pair of usize.¹ This is also consistent with the now-stable carrying_mul_add() function returning a pair of integers (but I think usize::widening_mul(_, _) is clearer to use than usize::carrying_mul_add(_, _, 0, 0)).

Also, for types where a wider type exists (e.g. u32 -> u64), obtaining the full multiplication as a wide type can already be achieved with e.g. x as u64 * y as u64, so having u32::widening_mul() -> u64 would be redundant.

Footnotes

1. A "multiply_high" method that returns a single usize would be enough in this specific case, but this can trivially be implemented from a widening_mul by discarding the low word of the resulting pair. ↩

[wr7]

Notably, widening multiplication (returning a tuple) is also useful for multiplying an integer by a know-compile-time non-integer.

An example use case for this would be for estimating the size for radix conversion. If we want to determine how many usize blocks are required to store a decimal number of a certain number of digits, we could do a wide multiply by ceil(log2(10) * 2^k / k) (where k is usize::BITS), take the high result, and add one. You could also add a shift to get slightly more accuracy. If we instead return a double-wide value, this cannot be called on usizes.

Also, in my opinion, the term "widening multiplication" could just as easily imply that it returns a tuple rather than a single, double-width value. I personally would find it unexpected if this method returned a single, double-width number. On most CPU architectures, widening multiplication stores its results in two separate registers, and for bignum or cryptography (where this term is often used), a tuple is typically a more useful result. Most implementations that I could find online for "wide multiplication" return two numbers (such as this C++ proposal).

Also, I feel like most programmers would default to x as LARGER_TYPE * y instead of x.widening_mul(y) unless x is a usize or u128, and this method cannot be implemented for either type unless a pair of numbers is returned.

[bjoernager]

Widened reimplementation: #156644.

[clarfonthey]

Also, for types where a wider type exists (e.g. u32 -> u64), obtaining the full multiplication as a wide type can already be achieved with e.g. x as u64 * y as u64, so having u32::widening_mul() -> u64 would be redundant.

I disagree; we have lots of methods which are technically "redundant" but which exist because the API is nice. I think this is a case where that helps. Additionally, it means that for macro-generated code, you don't necessarily need to have both a type and it's double-width version available to write the code that does a widening multiplication, e.g. if you wanted to implement a fraction-multiply that does a double-wide multiply because it's easier than doing a GCD first.