Home / Questions / 417864
Accepted
Daniel Briceño
Asked: 2022-01-01 12:29:35 +0800 CST 2022-01-01 12:29:35 +0800 CST

How to make a sqrt function in C?

  • 772

I am trying to make a function sqrt(); the function I got is very slow. How can I make it faster?

#include <stdio.h>
#include <math.h>
double root(double x);

int main(){
    printf("%f",root(3));
    printf("\n%f",sqrt(3));
    return 0;
}

double root(double x){
    long double a[9];
    long double b[9]={1.0,0.1,0.01,0.001,0.0001,0.00001,0.000001};
    
    int i=0;
    for(i=0;i<9;i++){
       a[i]=0.0;
    }

    i=-1;
    while(a[i]*a[i]!=x){
        if(i==8)
            i=-1;
        i++;
        a[i]+=b[i];
        if(a[6]*a[6]>x)
            return a[6];
        else if(a[5]*a[5]==x)
            return a[5];
        else if(a[4]*a[4]==x)
            return a[4];
    }
    return a[i];
}

I made this function on the basis that if you multiply all the numbers, you will be able to find the square root.

c

1 Answers

  1. Best Answer

    Summary of the original method

    The method consists of carrying several counters in parallel in a. The counter a[0]advances from 1 to 1, while it a[1]advances from 0.1 to 0.1, and so on.

    In each iteration, each counter is advanced and then it checks if the counter a[4]a a[6]already has the desired root, returning it.

    In total, to calculate the root of 3, more than 1.7 million iterations were made.

    New method

    I collect the essence of the method: I will start by adding 1 to the tentative root until its square exceeds the received parameter. I will deduct 1 and then I will repeat the operation advancing from 0.1 to 0.1 until the square exceeds the parameter. I will subtract 0.1 and then continue with 0.01 and so on.

    The calculation stops when exactly the root is found or until the factor to add is too small, and therefore does not produce a change in the root:

    double root(double x) {
    long double b[9] = {1.0, 0.1, 0.01, 0.001, 0.0001, 0.00001, 0.000001};

    double raiz = 0;
    for (int i = 0; i < 9; i++) {
        double ant = -1;
        while ((raiz * raiz) <= x && raiz != ant) {            
            ant = raiz;
            raiz += b[i];
            }
        raiz -= b[i];
        };
    return raiz;
}

    show

    int main() {
    for (int i=1; i < 20; i++) {
        printf("%d %f\n", i, root(i));
        }
    return 0;
}

    produces:

    1 1.000000
2 1.414213
3 1.732050
4 2.000000
5 2.236067
6 2.449489
7 2.645751
8 2.828427
9 3.000000
10 3.162277
11 3.316624
12 3.464101
13 3.605551
14 3.741657
15 3.872983
16 4.000000
17 4.123105
18 4.242640
19 4.358898

    Improved version

    The previous version only works for square roots of values ​​over 1. This second version accepts any positive value.

    The improvement is in the calculation of the starting root. The idea is to try with values ​​1, 10, 100, 1000, etc. until finding a value that exceeds the parameter. Then we successively divide by 10 until we find a value that is less than the parameter.

    The resulting value is the starting tentative root.

    Also simplify the detection of underflow , when the sum of the factor no longer contributes to the calculation of the root. In such a case, it returns directly to the caller.

    #define cuadrado(x) (x*x)

double root(double x) {
    
    double factor = 1;
    while (cuadrado(factor) < x) factor *= 10;
    while (factor && cuadrado(factor) > x) factor /= 10;
    
    double raiz = factor;
    while (cuadrado(raiz) <= x) {
        while (cuadrado(raiz) <= x) {            
            double ant = raiz;
            raiz += factor;
            if (raiz == ant)
                return raiz;
            }

        
         raiz -= factor;
         factor /= 10;
        }
    
    return raiz;
}

    produces:

    Raíz cuadrada de 0.0000001 es 0.000316
Raíz cuadrada de 0.0000010 es 0.001000
Raíz cuadrada de 0.0000100 es 0.003162
Raíz cuadrada de 0.0001000 es 0.010000
Raíz cuadrada de 0.0010000 es 0.031623
Raíz cuadrada de 0.0100000 es 0.100000
Raíz cuadrada de 0.1000000 es 0.316228
Raíz cuadrada de 1.0000000 es 1.000000
Raíz cuadrada de 10.0000000 es 3.162278
Raíz cuadrada de 100.0000000 es 10.000000
Raíz cuadrada de 1000.0000000 es 31.622777
Raíz cuadrada de 10000.0000000 es 100.000000
Raíz cuadrada de 100000.0000000 es 316.227766
Raíz cuadrada de 1000000.0000000 es 1000.000000
    • 8