[API Proposal]: Math.MulHigh

[saucecontrol]

Background and motivation

On Arm64, there is already a MultiplyHigh intrinsic that returns only the high part of an integer multiply. On x86/x64, mul and imul calculate the high part and low part at the same time can return the results in 2 registers, however there is no intrinsic that gives access to the high part of the result.

At present, the only way to get the high part of an integer multiply on x86/x64 is to use Math.BigMul and discard the low part of the result. BigMul is not currently optimized, although there is an open proposal for a multiply intrinsic that returns both halves of the result in a tuple #58263

I would like to propose a cross-platform way of accessing this functionality, as Math.MulHigh.

API Proposal

namespace System;

public static class Math
{
    public static int MulHigh(int left, int right);
    public static uint MulHigh(uint left, uint right);

    public static long MulHigh(long left, long right);
    public static ulong MulHigh(ulong left, ulong right);
}

API Usage

ulong hi = Math.MulHigh(a, b);

Alternative Designs

Most C compilers recognize a large multiply followed by a shift right as a smaller multiply high. Something like:

int64 hi = (int64)((int128)int64 * int64) >> 64);
int32 hi = (int32)((int64)int32 * int32 >> 32);

With the new Int128 type coming to .NET, this could be a possibililty.

#58263 proposes a tuple-returning multiply that would return both halves of the result. It would be possible to simply ignore the lower half as long as JIT could optimize this.

Or Math.BigMul could be optimized to use mul/imul and JIT could be made to recognize a discard of the low part parameter of , such that

ulong hi = Math.BigMul(a, b, out _);

would generate optimal code.

Risks

No response

Tagging subscribers to this area: @dotnet/area-system-numerics
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Background and motivation

On Arm64, there is already a MultiplyHigh intrinsic that returns only the high part of an integer multiply. On x86/x64, mul and imul calculate the high part and low part at the same time can return the results in 2 registers, however there is no intrinsic that gives access to the high part of the result.

At present, the only way to get the high part of an integer multiply on x86/x64 is to use Math.BigMul and discard the low part of the result. BigMul is not currently optimized, although there is an open proposal for a multiply intrinsic that returns both halves of the result in a tuple #58263

I would like to propose a cross-platform way of accessing this functionality, as Math.MulHigh.

API Proposal

namespace System;

public static class Math
{
    public static int MulHigh(int left, int right);
    public static uint MulHigh(uint left, uint right);

    public static long MulHigh(long left, long right);
    public static ulong MulHigh(ulong left, ulong right);
}

API Usage

ulong hi = Math.MulHigh(a, b);

Alternative Designs

Most C compilers recognize a large multiply followed by a shift right as a smaller multiply high, e.g. (int64)((int128)int64 * in64) >> 64) or (int32)((int64)int32 * in32 >> 32). With the new Int128 type coming to .NET, this could be a possibililty.

#58263 proposes a tuple-returning multiply that would return both halves of the result. It would be possible to simply ignore the lower half as long as JIT could optimize this.

Or Math.BigMul could be optimized to use mul/imul and JIT could be made to recognize a discard of the low part parameter of , such that

ulong hi = Math.BigMul(a, b, out _);

would generate optimal code.

Risks

No response

Author:	saucecontrol
Assignees:	-
Labels:	api-suggestion, area-System.Numerics, untriaged
Milestone:	-

[Daniel-Svensson]

It sounds like a reasonable suggestion, MultiplyHigh seems a more promising name since there are now an method with that name for arm.

However the BigMul method should hopefully be proper optimized soon, making this less urgent

I wonder if the team would prefer to have the method placed on the types themselvs, such as int.MultiplyHigh.
It would be nice if this woud get an api-review

[tannergooding]

I think it would be better if we could just correctly optimize BigMul where the upper bits aren't used.

If we were to expose MultiplyHigh, then it would need to be directly on the primitive types (all of the ones exposing BigMul at the very least). But, I don't really see the need or benefit when most hardware requires computing both halves anyways and we could ideally just pattern match to get the existing APIs to behave correctly.

[Daniel-Svensson]

Just to mention I have an open PR #115966 that solves the codegen issue for x64 , it was already very good for ARM64.

[tannergooding]

Going to close this for the reasons given above.