Aproximar mis cuadrados

10

Inspirado en este video de tecmath .

Se xpuede encontrar una aproximación de la raíz cuadrada de cualquier número tomando la raíz cuadrada entera s(es decir, el entero más grande de ese tipo s * s ≤ x) y luego calculando s + (x - s^2) / (2 * s). Llamemos a esto aproximación S(x). (Nota: esto es equivalente a aplicar un paso del método Newton-Raphson).

Aunque esto tiene peculiaridad, donde S (n ^ 2 - 1) siempre será √ (n ^ 2), pero en general será muy preciso. En algunos casos más grandes, esto puede tener una precisión> 99.99%.

Entrada y salida

Tomarás un número en cualquier formato conveniente.

Ejemplos

Formato: Entrada -> Salida

2 -> 1.50
5 -> 2.25
15 -> 4.00
19 -> 4.37               // actually 4.37       + 1/200
27 -> 5.20
39 -> 6.25
47 -> 6.91               // actually 6.91       + 1/300
57 -> 7.57               // actually 7.57       + 1/700
2612 -> 51.10            // actually 51.10      + 2/255
643545345 -> 25368.19    // actually 25,368.19  + 250,000,000/45,113,102,859
35235234236 -> 187710.50 // actually 187,710.50 + 500,000,000/77,374,278,481

Especificaciones

  • Su salida debe redondearse al menos a la centésima más cercana (es decir, si la respuesta es 47.2851, puede generar 47.29)

  • Su salida no tiene que tener los siguientes ceros y un punto decimal si la respuesta es un número entero (es decir, 125.00 también puede salir como 125 y 125.0)

  • No tiene que admitir ningún número inferior a 1.

  • No tiene que admitir entradas no enteras. (es decir, 1.52, etc.)

Reglas

Las lagunas estándar están prohibidas.

Este es un código de golf , por lo que la respuesta más corta en bytes gana.

code-golf math approximation Stan Strum
fuente
Sandbox
Stan Strum
3
Nota:s + (x - s^2) / (2 * s) == (x + s^2) / (2 * s)
JungHwan Min
Mis soluciones: Pyth , 25 bytes ; 14 bytes
Stan Strum
¿Debe tener una precisión de al menos 2 dígitos?
Totalmente humano
@totallyhuman Sí. 47.2851 se puede representar como 47.28, pero no más inexacto.
Stan Strum

Respuestas:

2

Jalea ,  8  7 bytes

-1 byte gracias a la fórmula matemática simplificada de Olivier Grégoire : vea su respuesta Java .

÷ƽ+ƽH

Pruébalo en línea!

¿Cómo?

÷ƽ+ƽH - Link: number, n
 ƽ     - integer square root of n  -> s
÷       - divide                    -> n / s
    ƽ  - integer square root of n  -> s
   +    - add                       -> n / s + s
      H - halve                     -> (n / s + s) / 2
Jonathan Allan
fuente
7 bytes: ÷ƽ+ƽHprimera vez que trato de usar Jelly, así que podría estar equivocado. Sin ƽembargo, desearía saber cómo almacenar para no repetirlo. Eso podría salvar otro byte.
Olivier Grégoire
Gracias @ OlivierGrégoire! ƽɓ÷⁹+Hno volvería a calcular la raíz entera, pero también es 7. ɓcomienza una nueva cadena diádica con argumentos intercambiados y luego se ⁹refiere al argumento correcto de esa cadena (es decir, el resultado de ƽ). ƽɓ÷+⁹HTrabajaría aquí también.
Jonathan Allan
4

Haskell , 34 bytes

f x=last[s+x/s|s<-[1..x],s*s<=x]/2

Pruébalo en línea!

Explicación en pseudocódigo imperativo:

results=[]
foreach s in [1..x]:
 if s*s<=x:
  results.append(s+x/s)
return results[end]/2
León
fuente
4

Java (OpenJDK 8) , 32 bytes

n->(n/(n=(int)Math.sqrt(n))+n)/2

Pruébalo en línea!

Explicaciones

El código es equivalente a esto:

double approx_sqrt(double x) {
  double s = (int)Math.sqrt(x);  // assign the root integer to s
  return (x / s + s) / 2
}

Las matemáticas detrás:

s + (x - s²) / (2 * s)  =  (2 * s² + x - s²) / (2 * s)
                        =  (x + s²) / (2 * s)
                        =  (x + s²) / s / 2
                        =  ((x + s²) / s) / 2
                        =  (x / s + s² / s) / 2
                        =  (x / s + s) / 2
Olivier Grégoire
fuente
Esto no parece manejar la especificación: su salida debe redondearse al menos a la centésima más cercana
Ayb4btu
2
Bueno, se redondea a menos que la centésima más cercana, por lo que es totalmente válido.
Olivier Grégoire
Ah, ya veo, mi malentendido.
Ayb4btu
4

Python 2 , 47 ... 36 bytes

-3 bytes gracias a @JungHwanMin
-1 byte gracias a @HyperNeutrino
-2 bytes gracias a @JonathanFrech
-3 bytes gracias a @ OlivierGrégoire

def f(x):s=int(x**.5);print(x/s+s)/2

Pruébalo en línea!

ovs
fuente
-2 bytes: s+(x-s*s)/s/2a(x+s*s)/s/2
JungHwan Min
-2 bytes usando una función
HyperNeutrino
@HyperNeutrino solo me dan -1 bytes
ovs
Oh, perdón
eliminé
¿No puede omitir +.0y reemplazar /s/2con /2./sguardar dos bytes?
Jonathan Frech
3

R, 43 bytes 29 bytes

x=scan()
(x/(s=x^.5%/%1)+s)/2

Gracias a @Giuseppe por la nueva ecuación y ayuda en el golf de 12 bytes con la solución de división entera. Al cambiar la llamada a la función para escanear, jugué otros dos bytes.

Pruébalo en línea!

marca
fuente
1
35 bytes ; de manera más general, puede usar el campo "encabezado" de TIO y poner un f <- para asignar la función. Pero aún así, buena solución, ¡asegúrese de leer Consejos para jugar golf en R cuando tenga la oportunidad!
Giuseppe
1
31 bytes usando la fórmula de Oliver Gregoire
Giuseppe
2

JavaScript (ES7), 22 bytes

x=>(s=x**.5|0)/2+x/s/2

Realmente no necesitamos una variable intermedia, por lo que en realidad se puede reescribir como:

x=>x/(x=x**.5|0)/2+x/2

Casos de prueba

Mostrar fragmento de código

Arnauld
fuente
2

C, 34 bytes

¡Gracias a @Olivier Grégoire!

s;
#define f(x)(x/(s=sqrt(x))+s)/2

Funciona solo con floatentradas.

Pruébalo en línea!

C,  41   39  37 bytes

s;
#define f(x).5/(s=sqrt(x))*(x+s*s)

Pruébalo en línea!

C,  49   47   45  43 bytes

s;float f(x){return.5/(s=sqrt(x))*(x+s*s);}

Pruébalo en línea!

¡Gracias a @JungHwan Min por guardar dos bytes!

Steadybox
fuente
1
47 bytes ; editar: Gracias, pero dale crédito a @JungHwanMin por encontrar eso.
Stan Strum
34 bytes
Olivier Grégoire
2

AWK , 47 44 38 bytes

{s=int($1^.5);printf"%.2f",$1/2/s+s/2}

Pruébalo en línea!

NOTA: El TIO like tiene 2 bytes adicionales para \nque la salida sea más bonita. :)

Se siente como engañar un poco usar sqrt para encontrar la raíz cuadrada, así que aquí hay una versión con algunos bytes más que no lo hace.

{for(;++s*s<=$1;);s--;printf("%.3f\n",s+($1-s*s)/(2*s))}

Pruébalo en línea!

Robert Benson
fuente
1
Bueno, se podría decir que esto es AWKward. Me mostraré afuera. editar: originalmente planeé que la pregunta evitara usar sqrt, pero hay demasiadas respuestas y tendré un agravio si la cambio para que mi idea original funcione.
Stan Strum
Los juegos de palabras 'AWK' son divertidos :)
Robert Benson
en lugar de sqrt($1)que pueda usar$1^.5
Cabbie407
Gracias @ Cabbie407 no sé por qué no pensé en eso.
Robert Benson
1
De nada. Algunas otras cosas: no necesita el \npara obtener la salida, el printf en awk no necesita paréntesis y la fórmula puede acortarse s/2+$1/s/2, lo que da como resultado {s=int($1^.5);printf"%.2f",s/2+$1/s/2}. Lo siento si este comentario parece grosero.
Cabbie407
1

Raqueta , 92 bytes

Gracias a @JungHwan Min por el consejo en la sección de comentarios

(λ(x)(let([s(integer-sqrt x)])(~r(exact->inexact(/(+ x(* s s))(* 2 s)))#:precision'(= 2))))

Pruébalo en línea!

Sin golf

(define(fun x)
  (let ([square (integer-sqrt x)])
    (~r (exact->inexact (/ (+ x (* square square)) (* 2 square)))
        #:precision'(= 2))))
Rodrigo Ruiz Murguía
fuente
1

PowerShell , 54 bytes

param($x)($x+($s=(1..$x|?{$_*$_-le$x})[-1])*$s)/(2*$s)

Pruébalo en línea! o verificar algunos casos de prueba

Toma entrada $xy luego hace exactamente lo que se solicita. La |?parte encuentra el número entero máximo que, cuando se eleva al cuadrado, es mayor -lque ela entrada $x, luego realizamos los cálculos requeridos. La salida es implícita.

AdmBorkBork
fuente
Guau. Nunca he podido comprender cómo la gente juega golf en Windows Powershell
Stan Strum
@StanStrum No estás solo, jajaja. : D
AdmBorkBork
1

Casco , 9 bytes

½Ṡ§+K/(⌊√

Pruébalo en línea!

Todavía hay algo feo en esta respuesta, pero parece que no puedo encontrar una solución más corta.

Explicación

Estoy implementando un paso del algoritmo de Newton (que de hecho es equivalente al propuesto en esta pregunta)

½Ṡ§+K/(⌊√
  §+K/       A function which takes two numbers s and x, and returns s+x/s
 Ṡ           Call this function with the input as second argument and
      (⌊√    the floor of the square-root of the input as first argument
½            Halve the final result
León
fuente
Creo que quieres una división real, en lugar de÷
H.PWiz
@ H.PWiz whoops, sí, gracias. Eso fue un remanente de un experimento para encontrar otras soluciones
Leo
1

Pyt , 11 10 bytes

←Đ√⌊Đ↔⇹/+₂

Explicación

code                explanation                        stack
←                   get input                          [input]
 Đ                  duplicate ToS                      [input,input]
  √⌊                calculate s                        [input,s]
    Đ               duplicate ToS                      [input,s,s]
     ↔              reverse stack                      [s,s,input]
      ⇹             swap ToS and SoS                   [s,input,s]
       /            divide                             [s,input/s]
        +           add                                [s+input/s]
         ₂          halve                              [(s+input/s)/2]
                    implicit print
mudkip201
fuente
Acabo de ver esto y fue un buen minuto hasta que me di cuenta de que no era Pyth. Gran respuesta.
Stan Strum
Sí, es un pequeño lenguaje en el que he estado pensando durante un tiempo y que decidí hacer.
mudkip201
¿Es ToS el primero de la pila ... y si es así, qué es SoS?
Stan Strum
ToS es el primero de la pila, y SoS es el segundo en la pila
mudkip201
Bien, veré si puedo profundizar en este idioma; ¡Me gusta!
Stan Strum
1

Vía Láctea , 17 14 bytes

-3 bytes usando la fórmula de Olivier Grégoire

^^':2;g:>/+2/!

Pruébalo en línea!

Explicación

code              explanation                   stack layout

^^                clear preinitialized stack    []
  ':              push input and duplicate it   [input, input]
    2;            push 2 and swap ToS and SoS   [input, 2, input]
      g           nth root                      [input, s=floor(sqrt(input))]
       :          duplicate ToS                 [input, s, s]
        >         rotate stack right            [s, input, s]
         /        divide                        [s, input/s]
          +       add                           [s+input/s]
           2/     divide by 2                   [(s+input/s)/2]
             !    output                        => (s+input/s)/2
ovs
fuente
¿No debería ser piso en lugar de techo?
mudkip201
@ mudkip201 Actualizado, gracias
ovs