Getting the high part of signed integer multiplication in C++

Question

How can I manually calculate the high part for a signed multiplication in C++? Like Getting the high part of 64 bit integer multiplication (unsigned only), but how do I calculate carry/borrow?

I do not mean that cast in a larger type (thats simple), but really manual calculation, so it works also with int128_t. My goal is to write a template function that always returns the correct high-part for signed and unsigned arguments (u/int8..128_t):

template <typename Type>
constexpr Type mulh(const Type& op1, const Type& op2) noexcept
{
    if constexpr (std::is_signed_v<Type>)   return ???;
    else                                    return see link;
}

You have to use unsigned arithmetic or compiler intrinsic functions and/or non-standard modes like -fwrapv because signed arithmetic overflow is undefined behavior in C++ and avoiding it is quite inefficient. — Öö Tiib, Aug 06 '19 at 22:01
I've implemented adc/sbb (uint8..128_t) and addh/subh (u/int8..128_t) in my library; these functions could be used. — Gero, Aug 06 '19 at 22:25
You can piece-wise multiply the 64-bit numbers into 4 smaller 32-bit multiplies and related adds and shifts. Slow, but portable and extendable to any size. — Michael Dorgan, Aug 06 '19 at 23:31

score 1 · Answer 1 · answered Aug 06 '19 at 22:42

1

It seems that you are implementing things that are usually available as compiler builtin functions.

Implementing those in standard C++ results with less efficient code. That can be still fun as mental exercise but then why you ask us to spoil it as whole?

answered Aug 06 '19 at 22:42

Öö Tiib

10,809
25
44

I need a compiler-independent function and not builtins/intrinsics. Unfortunately, such things are not in the C/C++-standard, that's my problem. – Gero Aug 06 '19 at 23:10
Typical solution to that is to hide side-by-side platform-dependent solutions (using conditional compiling with preprocessor) behind common platform-independent interface. – Öö Tiib Aug 07 '19 at 08:15

score 0 · Answer 2 · answered Aug 06 '19 at 22:37

0

If you can do signed, then you could convert unsigned to signed x=(x<0)?x*-1:x get the result and then calculate the sign afterwards z=((x<0)!=(y<0))?z*-1:z

This works becuase the magnitude of a signed integer of arbitraty length is always going to fit into an unsigned integer of the same length, and you know that if both numbers are negative or positive the answer will be positive, if only one of them is negative it will be negative.

answered Aug 06 '19 at 22:37

Rob Lambden

2,175
6
15

Sadly, that is not correct. I have a unit test for unsigned integer which runs correctly for all values (uses mulh_unsigned). When I calculate `template constexpr Type mulh_signed (const Type& op1, const Type& op2) noexcept { using unsigned_type = std::make_unsigned_t ; const bool neg1{op1<0}, neg2{op2<0}; const unsigned_type arg1 = neg1 ? op1 * Type{-1} : op1, arg2 = neg2 ? op2 * Type{-1} : op2, res = mulh_unsigned(arg1, arg2); return (neg1 == neg2)? res : res * Type{-1}; }` crash it at op1 = -128 and op2 = 1 with Type=int8_t :-( – Gero Aug 07 '19 at 00:49
@Gero - but how do you fit -128 into an 8 bit signed value? The negative value with largest magnitude an 8 bit signed integer can hold is -127! – Rob Lambden Aug 07 '19 at 07:49
The range of int8_t is -128 ... 127. The issue is likely in something else there. @Gero should debug what the actual issue is. – Öö Tiib Aug 07 '19 at 08:10
@Oo Tib - Doh! I should have finished my coffee first! Thanks for catching my mistake :o) – Rob Lambden Aug 07 '19 at 08:29

Getting the high part of signed integer multiplication in C++

2 Answers2