Home / Questions / 328715
Accepted
DDR
Asked: 2020-02-12 18:36:04 +0800 CST 2020-02-12 18:36:04 +0800 CST

Avoid number overflow

  • 772

I am doing a basic program that does calculations with very large numbers, what I do is read it as Stringand the idea is that I multiply each digit of the number by a large number (for example 100000).

#include <stdio.h>
#include <string.h>
#include <math.h>



int main( ) {
  char cadena[1000];
  char cadena2[1000];

  scanf( "%s", cadena2 );

  for( unsigned i = 0; i < strlen( cadena2 ); ++i ) {
    cadena[i] = cadena2[i] - '0';
    cadena[i] *= 100000;
    cadena[i] = cadena[i] + '0';
  }

  printf( "%s", cadena);

  return 0;
}

but logically it overflows and at the time of printing, that is, what is expected does not come out.

My question is how can I save a number so large that it should only be read as String?

Thank you!

PS: I had already asked a question associated with this topic . Operation with a numeric value of a digit does not produce the expected result.

c

2 Answers

  1. Best Answer

    If you want to multiply each digit by 100000, then your destination string must have a corresponding size: 1000 * 100000. The result of that is... just over 95M.

    We will use formations... but, in anticipation of size problems, we will create them dynamically (we may have problems with the size limit for the OS stack).

    We have to take into account the size of the types ... a multiplication by 100000 does not fit in a char, since the proper charonly admits in the range 0- 255. So we better use intfor these things.

    And finally, to make our lives easier, we'll use the sprintf( ). This function is similar to printf( ), but instead of writing to a file, it writes to a memory buffer (which we have to manage ourselves). It is exactly what we are looking for:

    #include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main( ) {
  char *resultado = malloc( 1000 * 100000 );
  char *iterator = resultado;
  char entrada[1000];

  scanf( "%s", entrada );

  for( unsigned i = 0; i < strlen( entrada ); ++i ) {
    entrada[i] -= '0';
    iterator += sprintf( iterator, "%d", entrada[i] * 100000 );
  }

  printf( "%s", resultado );

  return 0;
}
    • 2

  2. If you scan a number as a string, you don't get the number itself but its character representation. Namely:

            00   01   02   03  <- offset memoria
123 ->  '1'  '2'  '3' '\0' <- caracteres
       0x30 0x31 0x32 0x00 <- representación hexadecimal

    Thus, the number 123, stored as a string, results in the following number sequence (in hexadecimal): 30313200.

    It's easy to see that, in this case, taking any of those characters and multiplying it by 100000 is not going to give you the expected result.

    If you choose to store a number as a sequence of characters, you will have to implement all the mathematical operations involved, as the standard library has no use for this. You could also use a third party library.

    That is, to add numbers you could do something like:

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* ReverseArray(char const* arr, size_t size)
{
  char* result = (char*)malloc(size * sizeof(char));
  for (size_t i = 0, j=size-1; i < size; ++i, --j)
  {
      result[j] = arr[i];
  }

  return result;
}

char* SumarNumerosGrandes(char const* numero1, char const* numero2)
{
  size_t length1 = strlen(numero1);
  size_t length2 = strlen(numero2);
  if( length2 > length1 )
    return SumarNumerosGrandes(numero2, numero1);

  // Invertimos los números para simplificar las operaciones
  char* sec1 = ReverseArray(numero1, length1);
  char* sec2 = ReverseArray(numero2, length2);
  char* resultado = (char*)malloc((length1 + 3) * sizeof(char));

  size_t i;
  int acarreo = 0;
  for( i=0; i<length1; i++ )
  {
    int suma = (sec1[i] - 0x30) + acarreo;
    if( i < length2 )
      suma += (sec2[i] - 0x30);

    acarreo = 0;
    if( suma >= 10 )
    {
      acarreo = 1;
      suma -= 10;
    }

    resultado[i] = suma + 0x30;
  }

  if( acarreo != 0 )
  {
    resultado[i++] = acarreo + 0x30;
  }

  resultado[i] = '\0'; // Finalizamos el array

  char* toReturn = ReverseArray(resultado, i);

  // Liberamos la memoria dinámica
  free(sec1);
  free(sec2);
  free(resultado);

  return toReturn;
}
    • 2