Check if a number is a perfect square in C

Question

Task:

In an array of N elements (N < 20) of the unsigned long long type find the maximal full square and print its index (starting from zero). If there are no full squares, print -1. If there is more than one maximal square, print the index of the first one.

Input data: standard input stream, where N is written on the first line on the second line the array elements with a space.

Output data: a number in a standard output stream

Code:

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

int main() {
  
    unsigned short int n;
    unsigned long long mass[20];
    unsigned long long max = 0;
    int max_index = -1;
    
    scanf("%hu", &n);

    if (n >= 20) {

      do{
        
        scanf("%hu", &n);
        
      }while(n >= 20);
      
    }

    for (int i = 0; i < n; i++) {
        scanf("%llu", &mass[i]);

        long double root = (long double) sqrt(mass[i]);
        if (root * root == mass[i]) {

            if (mass[i] > max) {
                max = mass[i];
                max_index = i;
            }
        }
    }
    
    printf("%d\n", max_index);
    
    return 0;
}

I have this error while compiling

Error

I tried to use different types of data but it was useless.

Answer 1

At least these issues:

Wrong compiler

Error message indicates OP is using a C++ compiler when a C compiler should be used for C code. Function overloading (part of C++) is not a standard feature of C.

Loss of precision

sqrt(mass[i]) can loses precision. unsigned long long is at least a 64-bit type and converting that to double (to preform the square root) can lose needed precision. Floating point math introduces rounding issues too that can lead to incorrect results for this integer problem. Better to use integer math than floating-point math for an integer problem.

Similar problems with root * root == mass[i]

Consider forming a unsigned long long isqrt_ull(unsigned long long x) to find the square root.

Sample:

// Recursive version.
unsigned long long isqrt_ull(unsigned long long x) {
  if (x < 2) {
    return x;
  }
  unsigned long long s = isqrt_ull(x >> 2) << 1;
  unsigned long long t = s + 1;
  return (t > x / t) ? s : t;
}

Corner case: 0

If the array values are all 0, code reports -1 as mass[i] > max is never true. Better as mass[i] > max || max_index == -1

---

Other minor issues

• No need to test a new candidate for perfect square-ness unless it is greater than the prior max.

• Avoid type proliferation: Use int for reading the array size in this learner's exercise.

• Check return value of scanf() to know if input succeeded.

• isqrt_ull() is not a highly efficient integer square root routine. It is just there as a simple placeholder that does not suffer floating point issues yet handles unsigned long long.

Answer 2

Looks like you are on an older version of the Microsoft compiler. I can't repro your compiler error in the version I have.

But you could and should probably change this:

    long double root = (long double) sqrt(mass[i]);
    if (root * root == mass[i]) {

To this:

    double value = (double)mass[i];
    double root = sqrt(value);
    if (root * root == value) {

The conversion back to long double doesn't buy you anything. And the explicit cast of mass[i] form unsigned long long to double probably fixes your compiler error.

update

It would probably better if you avoided floating point altogether. Some compilers and runtimes have inherent precision issues with their implementation of the sqrt function. Most of the time it works as expected for whole numbers, but why take the chance? Let's introduce a worthy square root algorithm for unsigned long long integers. It's pretty much just a binary search.

unsigned long long squareRoot(unsigned long long value) {

    // To prevent overflow, take advangage of the fact that sizeof(result) <= sizeof(value)/2
    // This likely assumes two's complement machine
    const unsigned long long max_value = (unsigned long long)(-1);
    const unsigned long long max_square_root = max_value >> (4 * sizeof(value));

    unsigned long long low = 0;
    unsigned long long high = (value > max_square_root) ? max_square_root : (value / 2);
    unsigned long long mid = value / 2;

    while (low <= high) {
        mid = (low + high) / 2;
        unsigned long long midSquared = mid * mid;
        if (midSquared == value) {
            return mid;
        }
        if (midSquared < value) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }

    // return the value closest to the actual square root without going over
    if (mid * mid > value) {
        mid--;
    }
    return mid;
}

Then your main loop is simply:

for (int i = 0; i < n; i++) {
    scanf("%llu", &mass[i]);

    unsigned long long root = squareRoot(mass[i]);
    if (root * root == mass[i]) {
        if (mass[i] > max) {
            max = mass[i];
            max_index = i;
        }
    }
}