Sum function with return type large enough to hold result

Question

It's a question from C++ Primer Chapter 16.2.3 (question 16.41):

Write a version of sum with a return type that is guaranteed to be large enough to hold the result of the addition.

I'm sure there might be some rather obscure STL function that can get this job done, but in the context of the chapter it introduces Standard Type Transformation Templates such as remove_reference<T> and make_signed<T> which I'm sure it intends for me to use to accomplish this, in conjunction with trailing return types. The best I can do is:

template <typename It> auto sum(It first, It second) -> typename make_unsigned<It>::type {
    return first+second;
}

This almost answers the question but not quite, it doesn't account for that fact that I could pass two unsigned ints which add to go outside the range of values that an unsigned int can hold (and so loops back down to zero). As far as I can tell the transformation templates can't help with that issue, is it somehow possible to deduce the return type as the next largest integral type up from the integral type deduced from the passed arguments?

Feeze

unsigned long long int – Assuntaassur

@willywonka_dailyblah Certainly true but that feels very brute-forced. The question might want the function to be used with class types as well. – Feeze

try sizeof? and if that's too short throw an exception. or make a static assertion: #174856 – Assuntaassur

@Feeze How would this work with class types? – Sulfurous

@JamesRoot Huh, I automatically assumed make_unsigned<It>::type would return the class type if It was a class. Actually I realise now I'm wrong about that (having read cppreference), so disregard that comment. I guess maybe this question is integral-type specific. – Feeze

see C++ integer type twice the width of a given type – Buckhound

Answer 1

Since you want to do this at compile time, there is no way of knowing the value of the arguments the function will be invoked with. So you should protect agains overflowing at compile time, and the most obvious thing that comes to my mind is using a promotion trait class:

#include <iostream>
#include <limits>

template<typename T>
struct promote;

template<> // and so on for all types that you want to promote
struct promote<unsigned int> // type to be promoted from
{
    using type = unsigned long int; // type to be promoted to
};

// helper a la C++14
template<typename T>
using promote_t = typename promote<T>::type;

template <typename It> 
auto my_sum(It first, It second) -> promote_t<It>
{
    return static_cast<promote_t<It>>(first) + second; // promotion
}

int main()
{
    unsigned int a = std::numeric_limits<unsigned int>::max();
    unsigned int b = std::numeric_limits<unsigned int>::max();

    auto c = my_sum(a, b); // type is promoted to unsigned long int
    std::cout << "a = " << a << std::endl;
    std::cout << "b = " << b << std::endl;
    std::cout << "a + b = " << c << std::endl;
}

Live on Coliru

Furore

Very nice - if you don't mind, could you explain why the "helper" is needed ? Couldn't you just use promote<T>::type directly ? – Encephalitis

@PaulR Yes, you can. The helper is basically just to "help" you in less typing. Otherwise you have to keep typing typename promote<T>::type all the time (remember the typename since you have a dependent type). And the static_cast<promote_t<It>> will become miserably long: static_cast<typename promote<It>::type>. It becomes really useful when you re-use in other scenarios. – Furore

Although this would have to be written per platform, in case sizeof(unsigned int) == sizeof(unsigned long int). – Sulfurous

@JamesRoot Yes, you can even use some smart meta programming magic to decide which type is large enough etc, and based on that, to specialize accordingly. But of course the core of it will be platform dependent. Related: https://mcmap.net/q/987884/-c-11-way-to-write-template-for-picking-bigger-integer-type/3093378 – Furore

This still doesnt help if he's passed two unsigned longs. – Peso

@Peso That's why I put the comment "// and so on for all types that you want to promote". So you need to specialize the promote for unsigned long and all other types. Of course you'll hit a limit, when you must switch to arbitrary precision arithmetic (e.g. Boost.Multiprecision) – Furore

gotcha.... curious because I tend to imagine the book didnt rely upon boost. the mechanism is good though. – Peso

@Peso I'm pretty sure that the exercise in the book wants something much simpler than this probably... This approach is a bit too sophisticated for an exercise in a (non-template-based) book. – Furore

@Furore For the facilities supplied by the book up to this point, I don't see how it could be done in a simple way. Given the context of the chapter it almost certainly wanted an implementation in terms of type transformation templates (e.g. make_unsigned<T>) but I'm not sure whether the book author considered the sum function could be passed unsigned integral which is really where the bulk of complexity comes from (it also seems to be an unanswerable question - what if I add two large unsigned long longs?) – Feeze

@Feeze Then probably promotion type traits like the one in the answer is the way to go. And yes, in general you cannot do this and stay in the C++ fundamental type system. Eventually you need to switch to arbitrary precision arithmetic, as you mentioned in the unsigned long long comment. – Furore

Answer 2

Expanding upon @vsoftco's answer, this would be a more portable way to define the promote classes, also taking into account the case where both arguments are negative:

#include <cstdint>
#include <type_traits>
#include <limits>

template<std::size_t, bool> struct promote;

template<> struct promote<sizeof(std::uint8_t ), false> { using type = std::uint16_t; };
template<> struct promote<sizeof(std::uint16_t), false> { using type = std::uint32_t; };
template<> struct promote<sizeof(std::uint32_t), false> { using type = std::uint64_t; };

template<> struct promote<sizeof(std::int8_t ), true> { using type = std::int16_t; };
template<> struct promote<sizeof(std::int16_t), true> { using type = std::int32_t; };
template<> struct promote<sizeof(std::int32_t), true> { using type = std::int64_t; };

template<typename T> using promote_t = typename promote<sizeof(T), std::is_signed<T>::value>::type;

template <typename T>
promote_t<T> my_sum(T first, T second)
{
    return static_cast<promote_t<T>>(first) + second; // promotion
}

void test()
{
    using namespace std;
    auto a = numeric_limits<int>::min();
    cout << a << " + " << a << " = " << my_sum(a, a) << endl;

    auto b = numeric_limits<unsigned int>::max();
    cout << b << " + " << b << " = " << my_sum(b, b) << endl;
}

Tumescent

Answer 3

I decided to add a way to pick the next largest integral type based on the size of the type. It checks if the type is signed, and if so, makes it unsigned. Otherwise, it checks the unsigned types beginning with unsigned char to find the smallest type that is larger than the current one. It fails a static_assert if there is no larger type. It works like this:

int main()
{
    int a = 0, b = 0;
    sum(a, b); //return type is unsigned int
    unsigned int c = 0, d = 0;
    sum(c, d); //return type is unsigned long long on my platform
    unsigned long long e = 0, f = 0;
    sum(e, f); //error
}

The full code is below. It's not the prettiest thing in the world, but I thought it was an interesting experiment.

#include <type_traits>
#include <tuple>
#include <cstddef>

typedef std::tuple<unsigned char, unsigned short, unsigned int, unsigned long, unsigned long long> type_list;

template <typename, std::size_t>
struct get_larger_type;

template <bool B_, std::size_t S_, typename T_, typename... Ts_>
struct picker
{
    typedef T_ type;
};

template <std::size_t S_, typename T_, typename... Ts_>
struct picker<false, S_, T_, Ts_...>
{
    typedef typename get_larger_type<std::tuple<Ts_...>, S_>::type type;
};

template <typename T_, typename... Ts_, std::size_t S_>
struct get_larger_type<std::tuple<T_, Ts_...>, S_>
{
    typedef typename picker<(sizeof(T_) > S_), S_, T_, Ts_...>::type type;
};
template <std::size_t S_>
struct get_larger_type<std::tuple<>, S_>
{
    //Or if you want to use a multiprecision library, edit this to use that.
    static_assert(S_ != S_, "Foolish mortal you tread on the domain of gods!");
    typedef void type;
};

template <bool, typename T_>
struct pick_promotion
{
    typedef typename std::make_unsigned<T_>::type type;
};

template <typename T_>
struct pick_promotion<true, T_>
{
    typedef typename get_larger_type<type_list, sizeof(T_)>::type type;
};

template <typename T_>
typename pick_promotion<std::is_unsigned<T_>::value, T_>::type sum(T_ a, T_ b)
{
    return static_cast<T_>(a) + static_cast<T_>(b);
}

Sulfurous

Answer 4

with a return type that is guaranteed to be large enough to hold the result of the addition.

Your easy option is to use an arbitrary precision math package.

Your slightly harder option is to write an arbitrary precision arithmetic add.

I have some code that uses a package, but I can't find it at the moment. Will update when I find it. Easy to use.

Update: found it

package called gmpxx.h. (I think boost also has a suitable class or 2)

---

With uint64_t, factorial 93 (or maybe 94?) causes wrap around.

93!  
  1,156,772,507,081,641,574,759,205,162,306,240,436,214,753,229,576,413,535,186,142,281,213,246,807,
121,467,315,215,203,289,516,844,845,303,838,996,289,387,078,090,752,000,000,000,000,000,000,000

---

With mpz_class,

1000!  
402,387,260,077,093,773,543,702,433,923,003,985,719,374,864,210,714,632,543,799,910,429,938,512,398,
629,020,592,044,208,486,969,404,800,479,988,610,197,196,058,631,666,872,994,808,558,901,323,829,669,
944,590,997,424,504,087,073,759,918,823,627,727,188,732,519,779,505,950,995,276,120,874,975,462,497,
043,601,418,278,094,646,496,291,056,393,887,437,886,487,337,119,181,045,825,783,647,849,977,012,476,
632,889,835,955,735,432,513,185,323,958,463,075,557,409,114,262,417,474,349,347,553,428,646,576,611,
667,797,396,668,820,291,207,379,143,853,719,588,249,808,126,867,838,374,559,731,746,136,085,379,534,
524,221,586,593,201,928,090,878,297,308,431,392,844,403,281,231,558,611,036,976,801,357,304,216,168,
747,609,675,871,348,312,025,478,589,320,767,169,132,448,426,236,131,412,508,780,208,000,261,683,151,
027,341,827,977,704,784,635,868,170,164,365,024,153,691,398,281,264,810,213,092,761,244,896,359,928,
705,114,964,975,419,909,342,221,566,832,572,080,821,333,186,116,811,553,615,836,546,984,046,708,975,
602,900,950,537,616,475,847,728,421,889,679,646,244,945,160,765,353,408,198,901,385,442,487,984,959,
953,319,101,723,355,556,602,139,450,399,736,280,750,137,837,615,307,127,761,926,849,034,352,625,200,
015,888,535,147,331,611,702,103,968,175,921,510,907,788,019,393,178,114,194,545,257,223,865,541,461,
062,892,187,960,223,838,971,476,088,506,276,862,967,146,674,697,562,911,234,082,439,208,160,153,780,
889,893,964,518,263,243,671,616,762,179,168,909,779,911,903,754,031,274,622,289,988,005,195,444,414,
282,012,187,361,745,992,642,956,581,746,628,302,955,570,299,024,324,153,181,617,210,465,832,036,786,
906,117,260,158,783,520,751,516,284,225,540,265,170,483,304,226,143,974,286,933,061,690,897,968,482,
590,125,458,327,168,226,458,066,526,769,958,652,682,272,807,075,781,391,858,178,889,652,208,164,348,
344,825,993,266,043,367,660,176,999,612,831,860,788,386,150,279,465,955,131,156,552,036,093,988,180,
612,138,558,600,301,435,694,527,224,206,344,631,797,460,594,682,573,103,790,084,024,432,438,465,657,
245,014,402,821,885,252,470,935,190,620,929,023,136,493,273,497,565,513,958,720,559,654,228,749,774,
011,413,346,962,715,422,845,862,377,387,538,230,483,865,688,976,461,927,383,814,900,140,767,310,446,
640,259,899,490,222,221,765,904,339,901,886,018,566,526,485,061,799,702,356,193,897,017,860,040,811,
889,729,918,311,021,171,229,845,901,641,921,068,884,387,121,855,646,124,960,798,722,908,519,296,819,
372,388,642,614,839,657,382,291,123,125,024,186,649,353,143,970,137,428,531,926,649,875,337,218,940,
694,281,434,118,520,158,014,123,344,828,015,051,399,694,290,153,483,077,644,569,099,073,152,433,278,
288,269,864,602,789,864,321,139,083,506,217,095,002,597,389,863,554,277,196,742,822,248,757,586,765,
752,344,220,207,573,630,569,498,825,087,968,928,162,753,848,863,396,909,959,826,280,956,121,450,994,
871,701,244,516,461,260,379,029,309,120,889,086,942,028,510,640,182,154,399,457,156,805,941,872,748,
998,094,254,742,173,582,401,063,677,404,595,741,785,160,829,230,135,358,081,840,096,996,372,524,230,
560,855,903,700,624,271,243,416,909,004,153,690,105,933,983,835,777,939,410,970,027,753,472,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000

Benumb

Answer 5

This is how i did it, used decltype to get the type of the resultant

template <typename T>
auto sum(T a, T b) -> decltype(a + b)
{
    return a + b;
}

Helicopter