0

This is a user defined program to print the square root of a number. It is supposed to work for numbers which aren't perfect squares as well. i is incremented by a step of 0.01 each time and the the value of i*i is checked if equal to n. And if equal then the value of i is printed.

#include <stdio.h>

void squareRoot(double);

int main()
{
    double num;
    scanf("%lf", &num);
    squareRoot(num);
    return 0;
}

void squareRoot(double n)
{
    double i;
    for (i = 0; i < n; i += 0.01)
    {
        //printf("%.2lf\n",i*i);
        if (i * i == n)
        {
            printf("%lf\n", i);
            break;
        }
    }
}
anastaciu
  • 23,467
  • 7
  • 28
  • 53
Vinod Antony
  • 35
  • 5
  • 1
    Please see [Is floating point math broken?](http://stackoverflow.com/questions/588004/is-floating-point-math-broken) and [Why Are Floating Point Numbers Inaccurate?](https://stackoverflow.com/questions/21895756/why-are-floating-point-numbers-inaccurate) Aside: it is better not to mix *form* with *functionality*, so the `printf` is better placed in the calling function, and `squareRoot` should `return i;` – Weather Vane Mar 28 '20 at 17:47
  • 2
    Try this `i * i >= n`. – Eraklon Mar 28 '20 at 17:50
  • 2
    A loop using `i += 0.01` cannot find the square root of most numbers. For example, the square root of 2 is about 1.4142. It is neither 1.41 nor 1.42, and `i * i == n` will not be true for any value of `i` in this loop. what value do you want the program to find for numbers whose square root is not a multiple of .01? Should it find 1.41 because it is closer? Should it find 1.41 because it is the greatest candidate not more than the square root? Should it find 1.42 because it is the least candidate not less than the square root? Should it find any number near the square root? – Eric Postpischil Mar 28 '20 at 17:59
  • out of all these very good remarks to compute the square of a large number will need time (when it finish) – bruno Mar 28 '20 at 18:04
  • Even if I type a genuine perfect square like 25, there will be no output. @EricPostpischil – Vinod Antony Mar 28 '20 at 18:05
  • @WeatherVane I'll go through it. I initially made my function return the value of ` i ` . Made it void later just to check the values it was running through if any. – Vinod Antony Mar 28 '20 at 18:07
  • @Yunnosch I understand now, there is some issue with how floating point numbers are stored in the hardware and different standards used. So in the end what is the workaround ? How can I make a user defined function that will return the square root of an input regardless of whether it is a perfect square or not. Is there any other logic that I could follow ? – Vinod Antony Mar 28 '20 at 18:13
  • @Eraklon unfortunately that does not resolve the issue. There is still no output – Vinod Antony Mar 28 '20 at 18:14
  • 1
    @VinodAntony There are other ways. Use a binary search like approach. Keep 2 numbers greatest=n and lowest=0. Find the middle value and update the new values. Go on until abs(i*i - n) < 0.000001 (or whatever is the lowest precision you want). Also include an error for negative numbers – Abhay Aravinda Mar 28 '20 at 18:17
  • 1
    @VinodAntony: We know the program may also fail for 25. That is easily correctable. The problem I pointed out is not. To know how to proceed, we need answers to the questions I asked. Answer them. **To design any program, you should have a specification of what the program’s results should be.** I know that can be hard for a student. And it does not have to be a complete or precise specification to start. But there should be something. In this case, we have no clue what output you want for an input of 2. So **answer the questions** to explain to us what it is desired that the program do. – Eric Postpischil Mar 28 '20 at 18:28
  • @EricPostpischil I understand, I will be more specific next time. My program is simple, you input a single non negative integer and the square root is displayed with max of 2 decimal places eg input : 23 output : 4.79 (the program expects you to input non negative)(I didn't make any provisions to check this as my first priority was to see if my logic worked) – Vinod Antony Mar 29 '20 at 03:49
  • @AbhayAravinda I'll definitely look into it. I'm still new to the Data structure part in C. I'll check it out – Vinod Antony Mar 29 '20 at 03:54

1 Answers1

2

The method you use is, at best, very inaccurate for the reasons explained in the comments, there are several ways to calculate a square root, for this sample I'll use the Babylonian method which in its simplified form is very easy to implement using trivial arithmetic operations:

Running sample

#include <stdio.h>

double squareRoot(double);

int main() {

    double num;

    printf("Enter number: \n");
    scanf("%lf", &num);

    if(num < 0) {
        puts("Negative values not allowed");
        return 1;
    }

    printf("Square root of %.2lf is %lf", num, squareRoot(num));
}

double squareRoot(double num) {

    double sqroot = num / 2, temp = 0;

    while (sqroot != temp) {
        temp = sqroot;
        sqroot = (num / temp + temp) / 2;
    }
    return sqroot;
}
anastaciu
  • 23,467
  • 7
  • 28
  • 53
  • 2
    Do you know whether there is no value such that `(num / temp + temp) / 2` will fluctuate between two adjacent representable floating-point values in successive iterations, causing `sqroot != temp` to never be false? – Eric Postpischil Mar 28 '20 at 18:54
  • @EricPostpischil: I was wondering about that and haven't found a counter example yet... Nor did I find a way to prove it always stops for `num >= 0`. – chqrlie Mar 28 '20 at 19:17
  • @chqrlieforyellowblockquotes: I suspect square root’s derivative (low slope) avoids the problem, but there are two potential rounding errors (in `num/temp` and `+temp`; the `/2` is exact in binary floating-point), so I do not have an immediate proof. I do know the problem does not occur in the first 68 billion signficands. Just have a few quadrillion more to check. – Eric Postpischil Mar 28 '20 at 19:24
  • @EricPostpischil: sqrt's derivative increases when num goes to zero, but I did not find counter examples with a few billion tests there either. – chqrlie Mar 28 '20 at 19:27
  • 1
    @chqrlieforyellowblockquotes: Sorry, thinking in relative terms; it is only the derivative with respect to the significand that matters. If there is no counterexample between 1 and 4, there is none anywhere else; the arithmetic would be invariant upon translation of the exponent. – Eric Postpischil Mar 28 '20 at 19:28
  • @chqrlieforyellowblockquotes: if you want to exhaustively test, I'd start with a `float` version. There are ~4 billion floats, and incrementing an integer bit-pattern gives you the next one. – Peter Cordes Apr 02 '20 at 12:58
  • There are an infinite number of positive integers. Do you mean the set of integers that round to a finite `double`? Most of those round to the same `double` because the gap between representable doubles becomes 1, then 2, then 4, then 8, ... as the exponent field grows. Or more likely you only mean the positive `int` (int32_t) values? That's probably fine, but `double`'s mantissa is 53 bits, larger than the search space you explored, let alone the exponent. That's why I suggested checking all float bit patterns. It would take similar time (or less because float div is faster) – Peter Cordes Apr 03 '20 at 05:30
  • @PeterCordes, yes I mean all positive `int`s, this theme you explore is quite interesting, it might be worth a question of it's own. – anastaciu Apr 03 '20 at 10:56
  • 1
    @anastaciu: One of Bruce Dawson's series of FP articles covered the idea of exhaustively testing every possible float bit-pattern: https://randomascii.wordpress.com/2014/01/27/theres-only-four-billion-floatsso-test-them-all/. I implemented that idea myself as https://godbolt.org/z/uGCLhM. It finishes, and the asm didn't optimize away, so it does apparently converge eventually for all inputs, however slowly. – Peter Cordes Apr 03 '20 at 11:35
  • 1
    Oops, that version on Godbolt had modified loop bounds; the main loop finishes, but gets stuck on Inf / Inf => NaN in the final setup for printf at the end. https://godbolt.org/z/-yoTrM will actually finish. Interesting to run it under `perf stat -I10000 -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,arith.divider_active:u ./a.out` to see it speed up once it gets past the subnormal floats, then speed up (higher IPC) some as it gets closer to 1.0 (?) then slow down again, lower IPC. – Peter Cordes Apr 03 '20 at 11:56