una - suma de n numeros en dev c++

Función suma con tipo de retorno lo suficientemente grande como para contener el resultado

Question

Es una pregunta de C ++ Primer Capítulo 16.2.3 (pregunta 16.41):

Escriba una versión de suma con un tipo de devolución que garantice que sea lo suficientemente grande como para contener el resultado de la suma.

Estoy seguro de que puede haber alguna función STL bastante oscura que pueda hacer este trabajo, pero en el contexto del capítulo presenta Plantillas de Transformación de Tipo Estándar como remove_reference<T> y make_signed<T> que estoy seguro que pretende para que yo lo use para lograr esto, junto con los tipos de devolución finales. Lo mejor que puedo hacer es:

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

Esto casi responde a la pregunta pero no del todo, no explica el hecho de que podría pasar dos unsigned int que se agregan para salir del rango de valores que puede contener un unsigned int (y por lo tanto vuelve a cero). Por lo que puedo decir, las plantillas de transformación no pueden ayudar con ese problema. ¿Es posible de alguna manera deducir el tipo de retorno como el siguiente tipo integral más grande del tipo integral deducido de los argumentos pasados?

Answer 1

con un tipo de devolución que se garantiza que es lo suficientemente grande como para contener el resultado de la adición.

Su opción más fácil es usar un paquete matemático de precisión arbitrario.

Su opción un poco más difícil es escribir una suma aritmética de precisión arbitraria.

Tengo un código que usa un paquete, pero no puedo encontrarlo en este momento. Se actualizará cuando lo encuentre. Fácil de usar.

Actualización: lo encontré

paquete llamado gmpxx.h. (Creo que boost también tiene una clase adecuada o 2)

Con uint64_t, factorial 93 (¿o quizás 94?) Causa envolvimiento.

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

Con 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 2

Como desea hacer esto en tiempo de compilación, no hay forma de conocer el valor de los argumentos con los que se invocará la función. Por lo tanto, debe protegerse de los excesos que se desbordan en tiempo de compilación, y lo más obvio que se me viene a la mente es utilizar una clase de rasgo de promoción:

#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;
}

Vivir en Coliru

Answer 3

Ampliando la respuesta de @ vsoftco, esta sería una forma más portátil de definir las clases de promote , teniendo también en cuenta el caso en el que ambos argumentos son negativos:

#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;
}

Answer 4

Decidí agregar una forma de elegir el siguiente tipo integral más grande según el tamaño del tipo. Comprueba si el tipo está firmado, y si es así, lo hace sin firmar. De lo contrario, comprueba los tipos sin firmar que comienzan con caracteres unsigned char para encontrar el tipo más pequeño que es más grande que el actual. Falla un static_assert si no hay un tipo más grande. Funciona así:

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
}

El código completo está abajo. No es la cosa más bonita del mundo, pero pensé que era un experimento interesante.

#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);
}