best way to recognize and handle integer overflow in c?

Question

I am so new in C and so far I didn't comprehend how to prevent from integer overflow, I read many articles but still I am not 100% sure! in this case

int ft_sqrt(int nb)
{
    long int    sqrt;
    
    if (nb <= 0)
        return (0);
    if (nb == 1)
        return (1); 
    sqrt = 1;
    while (sqrt * sqrt < nb)
    {
        sqrt++;
    }
    if (sqrt * sqrt == nb)
        return (sqrt);
    else
        return (0);
}

to prevent overflow should I use

long

? what is the best practice to do that?

long is just a short name for long int. On some compilers and systems, long is 32 bits, on others it's 64 bits. To make sure you get the largest integer type, use long long which is guaranteed to be at least 64 bits. If you're dealing with numbers larger than 64-bit integers can handle, then there are "bignum" libraries you can use. — Some programmer dude
– Some programmer dude, Commented Feb 13, 2024 at 16:54
OT: Avoid using the name sqrt, as it is a name of a standard function. — Eugene Sh.
– Eugene Sh., Commented Feb 13, 2024 at 16:55
Since sqrt * sqrt may "overflow", you will need to check that sqrt is less than (or equal) the square root maximum value long int can hold before performing the operation. — Eugene Sh.
– Eugene Sh., Commented Feb 13, 2024 at 16:57
Consider the merits of while (sqrt < nb / sqrt) — that doesn't overflow. Check that the loop breaks or continues correctly on equality (< vs <=). You should be able to do better than incrementing sqrt by one each iteration. Look up Newton-Raphson, for example. — Jonathan Leffler
– Jonathan Leffler, Commented Feb 13, 2024 at 17:01
@Ouroborus: The lowest value to overflow when squared in a 32-bit int is 46,341, not 2^16. — Eric Postpischil
– Eric Postpischil, Commented Feb 13, 2024 at 17:11

Alef Carneiro de Sousa · Accepted Answer · 2025-02-24 14:26:09Z

2

So, first of all, you need to know if you want to detect an overflow or if you could just avoid them.

To just avoid them, if you know how long nb can be, maybe you could see if long or long long is big enough. And, if it isn't, maybe the solution proposed by @Jonathan Leffler of using while (sqrt < nb / sqrt) is the way to making it fit in one of those types.

Now, if you really want/need to check for overflow, then you'll need to check for square_root(MAX_NUMBER_ALLOWED) < sqrt, where MAX_NUMBER_ALLOWED would depend on which type you are using. C/C++ already have constants for that, you can check them here.

edited Feb 24 at 14:26

answered Feb 13, 2024 at 21:39

Alef Carneiro de Sousa

213 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

chux · Accepted Answer · 2024-02-13 21:51:09Z

long is not certainly wider than int and so its use may not widen the computation.

To certainly avoid overflow, don't multiple, but divide.

int ft_sqrt(int nb) {
    int    sqrt;
    if (nb <= 0)
        return (0);
    if (nb == 1)
        return (1); 
    sqrt = 1;
    // while (sqrt * sqrt < nb)
    while (sqrt < nb / sqrt) {
        sqrt++;
    }
    if (sqrt == nb / sqrt)
        return (sqrt);
    else
        return (0);
}

Yes code takes a performance hit - yet OP algorithm has many ways for improvement)

Alternate code:

unsigned bit_width(unsigned x) {
  unsigned width = 0;
  while (x) {
    x /= 2;
    width++;
  }
  return width;
}

unsigned usqrt(unsigned x) {
  if (x == 0) {
    return 0;
  }
  unsigned y = 1u << bit_width(x) / 2;
  unsigned y_previous;
  unsigned diff;
  unsigned diff1count = 0;

  do {
    y_previous = y;
    y = (y + x / y) / 2;
    diff = y_previous < y ? y - y_previous : y_previous - y;
    if (diff == 1)
      diff1count++;
  } while (diff > 1 || (diff == 1 && diff1count <= 1));
  y = (y_previous + y) / 2;
  return y;
}

Collectives™ on Stack Overflow

best way to recognize and handle integer overflow in c?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related