5

Estoy tratando de hacer una función sqrt(); la función que obtuve es muy lenta. ¿Cómo puedo hacerla más rápida?

#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];
}

Hice esta función en base a que, si multiplica todos los números, podrás encontrar la raíz cuadrada.

11
  • Porque no explicas tu algoritmo, para entenderte mejor
    – Japv
    Commented el 31 dic. 2020 a las 20:35
  • 1
    Échale un vistazo a esto, es una implementación de sqrt de fdlibm, viene el código fuente y en comentarios la explicación: netlib.org/fdlibm/e_sqrt.c
    – ordago
    Commented el 31 dic. 2020 a las 20:40
  • gracias por la respuesta.
    – DABL03
    Commented el 31 dic. 2020 a las 21:05
  • Japv--Disculpa por no expricar pero no soy bueno con las explicaciones. Solo esto digo: a es de 9 dimensiones cada una sumando la con cada dimension de b consiga el resultado en menor tiempo posible por ejemplo:
    – DABL03
    Commented el 31 dic. 2020 a las 21:19
  • saca la raiz cuadrada de cuatro:
    – DABL03
    Commented el 31 dic. 2020 a las 21:19

1 respuesta 1

8

Resumen del método original

El método consiste en llevar varios contadores en paralelo en a. El contador a[0] avanza de 1 en 1, mientras que a[1] avanza de 0.1 en 0.1, y así sucesivamente.

En cada iteración se avanza cada contador y luego revisa si el contador a[4] a a[6] ya tienen la raíz deseada, retornandola.

En total, para calcular la raíz de 3 se hicieron más de 1.7 millones de iteraciones.

Nuevo método

Recojo la esencia del método: partiré agregando 1 a la raíz tentativa hasta que su cuadrado supere al parámetro recibido. Descontare 1 y luego repetiré la operación avanzando de 0,1 en 0,1 hasta que el cuadrado supere el parámetro. Restare 0,1 y luego continuare con 0,01 y así sucesivamente.

El cálculo se detiene al encontrar exactamente la raíz o hasta que el factor a sumar sea demasiado pequeño, y por tanto no produzca cambio en la raíz:

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;
}

Demo

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

produce:

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

Versión mejorada

La versión previa sólo funciona para raíces cuadradas de valores sobre 1. Está segunda versión acepta cualquier valor positivo.

La mejora está en el cálculo de la raíz de partida. La idea es probar con valores 1, 10, 100, 1000, etc. hasta encontrar un valor que supere al parámetro. Luego vamos dividiendo sucesivamente por 10 hasta encontrar un valor que sea menor al parámetro.

El valor resultante es la raíz tentativa de partida.

También simplifique la detección de underflow, cuando la suma del factor ya no aporta al cálculo de la raíz. En tal caso, retorna directamente al llamante.

#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;
}

produce:

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
1
  • El alumno ha superado al maestro 😃
    – DABL03
    Commented el 31 dic. 2020 a las 22:30

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.