OcK OcK - 1 month ago 14
C Question

Square root algorithm in C

For practicing reasons I coded the following algorithm in C:

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


int main(){

double x=0;

printf("Enter the number: ");

scanf("%lf", &x);

int i = 0;

double v = 0;
double n=0;
int grenze = 12;
double z = 10;
/*
for(i=1; i<(x/2+1); i++){
v=i;
if((v*v) <= x){
n = i;
}
}

v=n;
*/
for(i=1; i<grenze+1; i++){
z = z * 0.1;

while(v*v<x){
v = v + z;
if(v*v<x){
n = v;
}
}
v=n;
}
printf("%.10f\n", n);



}


This works quite well, but for number greater than a certain value (I do not know when this starts) for example 50.000.000.000 the program freezes.

Is there anything I do not see here?

Answer

For a big enough number v and small enough number z, v = v + z; is a no-op — v doesn't change. That makes your loop run for a long time.

The algorithm is not a good choice — you should look up the Newton-Raphson method. I'm not convinced your algorithm will work well for extreme numbers like 1E-70 (and you've shown it won't work for numbers like 1E+70). Note that doubles have a range up to 1E±300 or more on most machines with IEEE floating point support.

Could you maybe explain why for a certain limit v = v + z is a no-op please?

Floating point numbers have a finite number of decimal digits — around about 16 for double, usually. If you add 1E+16 and 1E-16, then the result is 1E+16; there aren't enough significant digits to store the extra information. You have 5E+10 as the start point; you generate fractions z = 1.0 then 0.1, 0.01, … 0.000 000 000 01 or thereabouts (what's an order of magnitude between friends?). When you go around adding the smallest values, you don't end up changing anything.

The canonical document on the subject is What Every Computer Scientist Should Know About Floating-Point Arithmetic or from the ACM.