OcK - 1 year ago 66

C Question

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 Source

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.