Perdida de unidades al hacer varias sumas en C++

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
Post Reply
Lopex
Posts: 1
Joined: 3 years ago
Gender: None specified

Perdida de unidades al hacer varias sumas en C++

Post by Lopex » 3 years ago

Hola,

Ya eh presentado el mismo problema varias veces. El punto es que al ir realizando varias sumas relativamente sencillas pierdo unidades en el resultado. Para esto prepare un código que presenta este caso.

Code: Select all

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int main()
{
    char Numero_str[100];
    int longitud, i;
    long long Numero_int=0;
    
    cin>>Numero_str;
    longitud=strlen(Numero_str);
    for(i=0;i<longitud;i++)
        Numero_int += (Numero_str[i]-48) * pow(10, longitud - 1 - i );
    cout<<Numero_int;
    
    return 0;
}
El proposito del código es sencillo: Introduces un número y lo guardas en una cadena. Despues con un for conviertes esta cadena en un entero. El código sólo lo hice para representar el problema que tengo. En si, no sé si tenga alguna funcionalidad.

Al introducir el número 123456789 deveria guardar la cadena: [1][2][3][4][5][6][7][8][9]
Despues dentro del ciclo for hace la siguiente suma:
100000000
+20000000
+ 3000000
+ 400000
+ 50000
+ 6000
+ 700
+ 80
+ 9
__________
123456789

pero en lugar de eso obtengo como resultado: 123456787

Alguien podria decirme por favor ¿Qué es lo que estoy haciendo mal? y ¿Cómo solucionar este problema?
Saludos a todos y gracias de antemano.



User avatar
jose92
Posts: 24
Joined: 5 years ago
Location: Cienfuegos
Gender: None specified

Re: Perdida de unidades al hacer varias sumas en C++

Post by jose92 » 3 years ago

I think that the problem is that you use the ´pow´ function, this function acts over floating point numbers and this introduce an error, try to do the exponentiation ´by hand´ or ´binary´and you will see what I am saying.

HaZard
Posts: 113
Joined: 4 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: Perdida de unidades al hacer varias sumas en C++

Post by HaZard » 3 years ago

si, coincido con que es el pow, como consejo te digo que si vas a usar pow en vez de hacer:

Code: Select all

Numero_int += (Numero_str[i]-48) * pow(10, longitud - 1 - i );
hagas un redondeo a mano mas o menos asi:

Code: Select all

Numero_int += (Numero_str[i]-48) * (pow(10, longitud - 1 - i ) + 0.5);
la solucion más sencilla que yo haría es evitarlo de esta forma:

Code: Select all

Numero_int = Numero_int * 10 + Numero_str[i] - 48;
lo otro que vi que espero no te pase es que la cadena es de tamaño ¿100?, un entero a lo sumo te aguanta 9 o 10, si te pasas te va a dar los valores mal
teruel

User avatar
isaac
Posts: 83
Joined: 3 years ago
Gender: None specified

Re: Perdida de unidades al hacer varias sumas en C++

Post by isaac » 3 years ago

Dentro de las variables reales en C++ (float, double y long double), existe algo llamado Mantisa que no es mas que la parte decimal de la representacion de un numero. Por ejemplo, la mantisa de 39.4129 es 0.4129. Para esto, se utiliza una cierta cantidad de bits, los cuales determinan la precision con que se efectuan las operaciones. Muchas veces, con las multiples operaciones, se van perdiendo digitos. Otras veces simplemente es cuestion de una interpretacion un poco rara del compilador. Por ejemplo, si se imprime el resultado de calcular pow(5, 2), da como resultado 24, pero si se pone pow(5.0, 2), entonces da 25. El mismo problema del cuadrado de 5 pasa tambien con 11 y con muchos otros. Si quieres utilizar una funcion que eleve a la n, utiliza propiedades de la potencia. Te quedaria algo asi:

long long sq(long long x) {
return x * x;
}

long long pow(long long base, int e) {
if(e == 0)
return 1;
if(e == 1)
return b;
if(e % 2 == 0)
return sq(pow(b, e >> 1));
return b * pow(b, e-1);
}

Eso da en O(log2(e))

User avatar
alurquiza
Posts: 54
Joined: 3 years ago
Gender: Male

Re: Perdida de unidades al hacer varias sumas en C++

Post by alurquiza » 3 years ago

El pow esta hecho para elevar numeros fraccionarios, muchas veces da sus buenos bateos con numeros enteros.

User avatar
isaac
Posts: 83
Joined: 3 years ago
Gender: None specified

Re: Perdida de unidades al hacer varias sumas en C++

Post by isaac » 3 years ago

Un consejo que quisiera darles a modo general es que traten de evitar lo mas que puedan los numeros reales. Siempre que se pueda realizar una operacion con numeros enteros se debe tratar de no involucrar ni el double ni el float ni ningun otro que sea de tipo real porque cuando se van acumulando operaciones pierde un poco la significacion en la representacion numerica. Si el resultado final requiere que sea de tipo real, pero los calculos intermedios se pueden hacer con numeros enteros, entonces hay que maximizar el uso de estas operaciones y solamente hacer los calculos con valores reales cuando sea imprescindible.

Por ejemplo, si se quieren hallar una serie de operaciones referentes a las distancias entre puntos y estos tienen coordenadas enteras, es mejor hacer las transformaciones sin llevar a cabo la radicacion sino hasta que sea totalmente necesario (como a la hora de mostrar un resultado).

Post Reply

Return to “Algorithms”