1
\$\begingroup\$

I'm writing a (compile-time-)fixed-width unsigned big integer. To implement subtraction, a subtract-with-borrow primitive is required. When efficient platform-specific implementation isn't available (e.g. x86_64's _subborrow_u64 intrinsic), it needs to be implemented in Standard C++.

I've been able to come up with the following implementation:

#include <stdint.h>

inline
auto subtract_with_borrow(
    uint64_t& result,
    uint64_t left, uint64_t right,
    uint64_t borrow /* only 0 or 1 */)
-> uint64_t /* borrow */
{
    result = left - right - borrow;
    return (left < right) | ((left == right) & borrow);
}

However, I suspect it might be suboptimal since it requires roughly twice as many operations as add-with-carry (don't review it):

inline
auto add_with_carry(
    uint64_t& result,
    uint64_t left, uint64_t right,
    uint64_t carry /* only 0 or 1 */)
-> uint64_t /* carry */
{
    result = left + right;
    uint64_t next_carry = result < left;
    result += carry;
    return next_carry;
}

I intuitively expect a certain symmetry to exist here. Can subtract_with_borrow be simplified further? Or is my intuition wrong and this is indeed the optimal implementation?

And no, the compiler optimization doesn't manage to magically transform it into a better version.

\$\endgroup\$
0
2
\$\begingroup\$

Your intuition is correct, but the issue is that your add_with_carry lacks the carry propagation in subtract_with_borrow.

That's a general observation - if the new code looks more complicated than the old code, you should also consider that the old code lacked something.

Consider the call add_with_carray(0,2^64-1,1):

  result=0+(2^64-1); // 2^64-1
  next_carry=(2^64-1)<0; // False
  result+=1; // causing result=0; due to overflow
  return next_carry; // 0

In general you should test such routines for carry=0,1 and left, right close to 0 and 2^64-1

\$\endgroup\$
2
\$\begingroup\$

Prefer to use the C++ <cstdint> header that puts identifiers in the correct namespace, rather than the deprecated C-compatibility header. This is particularly important in header files, as these affect every translation unit that uses them.

    uint64_t carry /* only 0 or 1 */)

I dislike that comment style. Because the comment is almost, but not quite, at the end of line, it's very easy to miss the ) hiding there, and mis-parse.

If carry can only be 0 or 1, does it really make sense to pass as a 64-bit type? Certainly the bitwise arithmetic to create the carry-out is unlikely to create better code than plain logic && and || (any decent compiler can avoid unnecessary jumps because none of the operands have side-effects).

The test cases seem to have missed an important case in add_with_carry() (I know you said not to review that, but it's relevant for the subtract function):

#include <gtest/gtest.h>

TEST(add_with_carry, ci_causes_co)
{
    uint64_t small = 0;
    uint64_t big = ~small;
    uint64_t result;
    EXPECT_EQ(add_with_carry(result, small, big, 0), 0);
    EXPECT_EQ(result, big);
    EXPECT_EQ(add_with_carry(result, small, big, 1), 1);
    EXPECT_EQ(result, 0);
}

The corresponding test of subtraction succeeds:

TEST(subtract_with_borrow, ci_causes_co)
{
    uint64_t small = 0;
    uint64_t big = ~small;
    uint64_t result;
    EXPECT_EQ(subtract_with_borrow(result, 0, 0, 0), 0);
    EXPECT_EQ(result, 0);
    EXPECT_EQ(subtract_with_borrow(result, 0, 0, 1), 1);
    EXPECT_EQ(result, big);
}

So the two functions are not directly comparable. It's a shame you didn't include the tests for review - given that you've missed probably the most important boundary case, then the testing may well be deficient in other ways too.

To make the tests pass, I needed to make the logic of the two functions equivalent to each other:

static
auto subtract_with_borrow(uint64_t& result,
                          uint64_t left, uint64_t right,
                          bool borrow)
{
    result = left - right - borrow;
    return left < right || left == right && borrow;
}

static
auto add_with_carry(uint64_t& result,
                    uint64_t left, uint64_t right,
                    bool carry)
{
    result = left + right + carry;
    return left > ~right || left == ~right && carry;
}

Now that both tests pass, the corresponding assembly outputs look very similar to each other.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ I disagree about <cstdint>. I believe that [u]intN_t should've been fundamental types like int, and the fact that they are implemented as typedefs is a historical mistake. When considered like that, putting them into std doesn't make much sense. \$\endgroup\$ Jun 24 at 11:49
  • \$\begingroup\$ You are correct about my add_with_carry being broken, of course. But I believe an implementation exactly symmetric with subtract_with_borrow would be result = left + right + carry; return result < left || result == left && carry; \$\endgroup\$ Jun 24 at 12:12
  • 1
    \$\begingroup\$ You could do it that way, and change subtract_with_borrow to match. It's arguably better to not use result in computing the return value, though, as that allows more parallelism in a superscalar CPU. \$\endgroup\$ Jun 24 at 12:49
  • \$\begingroup\$ I'm not convinced that optional types could, never mind should, have been fundamental! \$\endgroup\$ Jun 24 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.