Sum function with return type large enough to hold the result

Question

This is a question from C ++ Primer Chapter 16.2.3 (question 16.41):

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

I'm sure there may be some rather obscure STL function that can do the job, but in the context of the chapter, it introduces standard-type conversion patterns such as remove_reference<T> and make_signed<T> , which I'm sure I intend to use for this in combination with returnable 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 does not take into account the fact that I could pass two unsigned int that are added to go beyond the range of values ​​that unsigned int can hold (and therefore fall back to zero). As far as I can tell, conversion patterns cannot help with this problem, is it possible to somehow deduce the return type as the next largest integral type from the integral type deduced from the passed arguments?

Answer 1

Since you want to do this at compile time, there is no way to know the meaning of the arguments with which the function will be called. So you have to protect overflows at compile time, and the most obvious thing that comes to my mind is to use the class of the promotion 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

Answer 2

I decided to add a way to select the next largest integral type based on the size of the type. It checks to see if the type is signed, and if so, makes it unsigned. Otherwise, it checks unsigned char types starting with unsigned char to find the smallest type that is larger than the current one. It does not work static_assert unless a larger type exists. It works as follows:

 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 given below. This is not the most beautiful 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); } 

Answer 3

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

Your simple option is to use an arbitrary mathematical precision package.

Your little difficulty is to write arbitrary arithmetic accuracy.

I have code that uses the package, but I can not find it at the moment. Will be updated when I find it. Easy to use.

Update: found

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

---

With uint64_t, factorial 93 (or maybe 94?) Causes a wrapping.

 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 

Answer 4

Turning around @vsoftco's answer, this will be a more portable way of defining 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; }