Método de Newton por quines recursivos

32

Su tarea es calcular la raíz cuadrada de 2 utilizando el Método de Newton, con un ligero giro. Su programa es calcular una iteración utilizando el Método de Newton y generar el código fuente para la siguiente iteración (que debe ser capaz de hacer lo mismo).

El método de Newton se describe de manera bastante exhaustiva en Wikipedia.

Para calcular la raíz cuadrada 2 utilizando el método de Newton, usted:

  • Definir f(x) = x^2 - 2
  • Definir f'(x) = 2x
  • Definir x[0](la suposición inicial)= 1
  • Definir x[n+1] = x[n] - (f[n] / f'[n])

Cada iteración moverá x [n] más cerca de la raíz cuadrada de dos. Asi que -

  • x[0] = 1
  • x[1] = x[0] - f(x[0])/f'(x[0]) = 1 - (1 ^ 2 - 2) / (2 * 1) = 1.5
  • x[2] = x[1] - f(x[1])/f'(x[1]) = 1.5 - (1.5 ^ 2 - 2) / (2 * 1.5) = 1.416666667
  • x[3] = x[2] - f(x[2])/f'(x[1]) = 1.416666667 - (1.416666667 ^ 2 - 2) / (2 * 1.416666667) = 1.414215686
  • y así

Tu programa:

  • Calcule x[n]dónde nes la cantidad de veces que se ejecutó el programa
  • Envíe el código fuente a un programa válido en el mismo idioma que debe calcular x[n+1]y satisfacer los mismos criterios de esta pregunta.
  • La primera línea del código fuente debe ser el resultado del cálculo, debidamente comentado. Si la fuente requiere algo particular (como un shebang) en la primera línea, el resultado puede colocarse en la segunda línea.

Tenga en cuenta que

  • Su programa debe usar una conjetura inicial de x[0] = 1
  • Se aplican las lagunas estándar
  • Cualquier poder incorporado, raíz cuadrada o funciones xroot están prohibidas
  • Su programa no debe aceptar ninguna entrada. Debe ser completamente autónomo.

Su puntaje es el tamaño de su programa inicial en bytes UTF-8. El puntaje más bajo gana.

code-golf math quine lochok
fuente
¿Tenemos que definir las funciones o podemos simplificar escribiendo x = x-(x*x-2)/(2*x)?
Kyle Kanos
Esa simplificación me parece válida. Siempre y cuando realice el cálculo utilizando el Método de Newton
lochok
¿El programa genera la aproximación o solo el código fuente? ¿Puede tomar como entrada la solución anterior?
Emily
Tiene que generar la aproximación (comentada) en la primera línea, con el código fuente para la siguiente iteración. La aproximación puede estar precedida por un shebang si el idioma lo requiere. El programa (ni el programa que produce) no debe aceptar ninguna entrada.
lochok

Respuestas:

19

Lisp común, 223 95 68 66

(#1=(lambda(x p)(format t"~S~%~S"p`(,x',x,(+(/ p 2)(/ p)))))'#1#1)

Ahora que leí el enunciado del problema con más atención (¡gracias, primo !) Noté que la primera línea debe ser el resultado del cálculo, no que necesita contener el resultado. Por lo tanto, creo que mis intentos anteriores no siguieron las reglas. Este debería.

Ejemplo de uso (SBCL 1.1.15):

$ sbcl --script nq.lisp | tee nq2.lisp
1
((LAMBDA (X P) (FORMAT T "~S~%~S" P `(,X ',X ,(+ (/ P 2) (/ P)))))
 '(LAMBDA (X P) (FORMAT T "~S~%~S" P `(,X ',X ,(+ (/ P 2) (/ P))))) 3/2)
$ sbcl --script nq2.lisp | tee nq3.lisp
3/2
((LAMBDA (X P) (FORMAT T "~S~%~S" P `(,X ',X ,(+ (/ P 2) (/ P)))))
 '(LAMBDA (X P) (FORMAT T "~S~%~S" P `(,X ',X ,(+ (/ P 2) (/ P))))) 17/12)
$ sbcl --script nq3.lisp | tee nq4.lisp
17/12
((LAMBDA (X P) (FORMAT T "~S~%~S" P `(,X ',X ,(+ (/ P 2) (/ P)))))
 '(LAMBDA (X P) (FORMAT T "~S~%~S" P `(,X ',X ,(+ (/ P 2) (/ P))))) 577/408)
$ sbcl --script nq4.lisp | tee nq5.lisp
577/408
((LAMBDA (X P) (FORMAT T "~S~%~S" P `(,X ',X ,(+ (/ P 2) (/ P)))))
 '(LAMBDA (X P) (FORMAT T "~S~%~S" P `(,X ',X ,(+ (/ P 2) (/ P)))))
 665857/470832)
$ sbcl --script nq5.lisp | tee nq6.lisp
665857/470832
((LAMBDA (X P) (FORMAT T "~S~%~S" P `(,X ',X ,(+ (/ P 2) (/ P)))))
 '(LAMBDA (X P) (FORMAT T "~S~%~S" P `(,X ',X ,(+ (/ P 2) (/ P)))))
 886731088897/627013566048)
$
jlahd
fuente
He estado probando principalmente con CCL, pero funciona de manera similar con SBCL y CLISP.
jlahd
1
Esto es más como lo esperaba. +1
primo
17

Python 60 bytes

x=1.
o='x=%s\no=%r;print o%%(x/2+1/x,o)';print o%(x/2+1/x,o)

He simplificado la fórmula ligeramente, usando las siguientes sustituciones:

  x-(x²-2)/(2x)
= (2x²)/(2x)-(x²-2)/(2x)
= (2x²-x²+2)/(2x)
= (x²+2)/(2x)
= (x+2/x)/2
= x/2+1/x

Espero que no sea un problema.

El programa procede de la siguiente manera:

$ python newton-quine.py
x=1.5
o='x=%s\no=%r;print o%%(x/2+1/x,o)';print o%(x/2+1/x,o)

$ python newton-quine.py
x=1.41666666667
o='x=%s\no=%r;print o%%(x/2+1/x,o)';print o%(x/2+1/x,o)

$ python newton-quine.py
x=1.41421568627
o='x=%s\no=%r;print o%%(x/2+1/x,o)';print o%(x/2+1/x,o)

$ python newton-quine.py
x=1.41421356237
o='x=%s\no=%r;print o%%(x/2+1/x,o)';print o%(x/2+1/x,o)

etc.

primo
fuente
No sé si esto es legal o no, pero puede acortar su código inicial a g="x=%s;o=%r;print o%%(x/2+1/x,o)";print g%(1.5,g)50 caracteres.
cjfaure
@Trimsty Creo que es un poco problemático que 1) en realidad no calcule la primera iteración, y que 2) la primera línea no contenga el resultado actual. Según tengo entendido la descripción del problema, tanto el programa original como las generaciones posteriores deberían satisfacer estos criterios.
primo
13

CJam, 20 bytes

1
{\d_2/1@/+p"_~"}_~

Pruébalo en línea.

Salida

$ cjam <(echo -e '1\n{\d_2/1@/+p"_~"}_~'); echo
1.5
{\d_2/1@/+p"_~"}_~
$ cjam <(cjam <(echo -e '1\n{\d_2/1@/+p"_~"}_~')); echo
1.4166666666666665
{\d_2/1@/+p"_~"}_~
$ cjam <(cjam <(cjam <(echo -e '1\n{\d_2/1@/+p"_~"}_~'))); echo
1.4142156862745097
{\d_2/1@/+p"_~"}_~
$ cjam <(cjam <(cjam <(cjam <(echo -e '1\n{\d_2/1@/+p"_~"}_~')))); echo
1.4142135623746899
{\d_2/1@/+p"_~"}_~

Cómo funciona

1       " Push the initial guess.                                                 ";
{       "                                                                         ";
  \d    " Swap the code block with the initial guess and cast to Double.          ";
  _2/   " Duplicate the initial guess and divide the copy by 2.                   ";
  1@/   " Push 1, rotate the initial guess on top and divide.                     ";
  +p    " Add the quotients and print.                                            ";
  "_~"  " Push the string '_~'.                                                   ";
}       "                                                                         ";
_~      " Duplicate the code block (to leave a copy on the stack) and execute it. ";
Dennis
fuente
2
Bueno, eso es impresionante. +1
Kyle Kanos
8

ECMAScript 6, 38 36

(f=x=>"(f="+f+")("+(x/2+1/x)+")")(1)
(f=x=>"(f="+f+")("+(x/2+1/x)+")")(1.5)
(f=x=>"(f="+f+")("+(x/2+1/x)+")")(1.4166666666666665)
(f=x=>"(f="+f+")("+(x/2+1/x)+")")(1.4142156862745097)
(f=x=>"(f="+f+")("+(x/2+1/x)+")")(1.4142135623746899)

JavaScript, 51

(function f(x){return "("+f+")("+(x/2+1/x)+")"})(1)

Esto es lo mismo que el anterior, para navegadores antiguos.

Zaq
fuente
1
A veces me sorprende lo simple que javascript puede hacer las cosas. +1
seequ
Esto parece haber perdido cualquier tipo de salida ( print, putstr, console.log, etc.).
primo
@primo: cuando JavaScript se ejecuta en una consola, el valor devuelto se imprime automáticamente.
Derek 朕 會 功夫
@Derek 朕 會 功夫 Se pueden ejecutar muchos idiomas como REPL; esta es una expresión y no un programa completo. Ver: "Lagunas" estándar que ya no son divertidas .
primo
1
@Derek 朕 會 功夫 La descripción del problema solicita específicamente un programa, en varios lugares. El programa suministrado no hace nada. Testigo: i.stack.imgur.com/Te7Vf.png Lo anterior es una expresión que se evalúa como una expresión. Tiene mérito propio, pero no es un programa.
primo
6

Lua 129

Probablemente demasiado tiempo, pero la quilla de Lua apesta porque la anidada [[ ]]es una característica obsoleta. Pero funciona independientemente:

x=1.0;x=x/2.+1./x;l=[[io.write('x=',x,';x=x/2.+1./x;l=[','[',l,']','];',l)]];io.write('x=',x,';x=x/2.+1./x;l=[','[',l,']','];',l)

Es un poco más agradable ver si agrega nuevas líneas en lugar de dos puntos:

x=1.0
x=x/2.+1./x
l=[[io.write('x=',x,'\nx=x/2.+1./x\nl=[','[',l,']','];',l)]];io.write('x=',x,'\nx=x/2.+1./x\nl=[','[',l,']','];',l)
Kyle Kanos
fuente
4

J - 102 88 bytes

Esto es tan horrible como estoy haciendo quines (probablemente revisaré esto cuando tenga mejores ideas). Las carrozas de J están limitadas a 5 decimales, pero al reemplazar la primera línea con x=:1xella sería una fracción con precisión infinita.

Edit 1: I got better idea. Also added the explanation.

x=:1
((3&{.,[:":(x%2)+1%x"_),:3&}.,],{:,{:)'x=:((3&{.,[:":(x%2)+1%x"_),:3&}.,],{:,{:)'''

Primeras iteraciones:

x=:1.5
((3&{.,[:":(x%2)+1%x"_),:3&}.,],{:,{:)'x=:((3&{.,[:":(x%2)+1%x"_),:3&}.,],{:,{:)'''

x=:1.41667
((3&{.,[:":(x%2)+1%x"_),:3&}.,],{:,{:)'x=:((3&{.,[:":(x%2)+1%x"_),:3&}.,],{:,{:)'''

x=:1.41422
((3&{.,[:":(x%2)+1%x"_),:3&}.,],{:,{:)'x=:((3&{.,[:":(x%2)+1%x"_),:3&}.,],{:,{:)'''

Explicación

((3&{.,[:":(x%2)+1%x"_),:3&}.,],{:,{:)'x=:((3&{.,[:":(x%2)+1%x"_),:3&}.,],{:,{:)'''
((3&{.,[:":(x%2)+1%x"_),:3&}.,],{:,{:) The quine-function
                         3&}.,],{:,{:  Build the second row
                         3&}.          Get everything but the first 3 characters from the string
                             ,]        Get the whole string and concat
                               ,{:     Get the last item (') and concat
                                  ,{:  -||-
 (3&{.,[:":(x%2)+1%x"_)                Build the first row
       [:":(x%2)+1%x"_                 Calculate x/2 + 1/x (stolen from Pythoneer) and stringify
  3&{.                                 Take the first 3 characters from the string (x=:)
      ,                                Concatenate 'x=:' and the result
                       ,:              Concatenate the two rows
seequ
fuente
1
De hecho, me encanta lo simple que es este programa (en serio).
seequ
Si tengo más tiempo, veré si puedo modificar lo anterior para Kona.
Kyle Kanos
@KyleKanos Al menos la cosa de rotación de dígitos era lo suficientemente similar, pero no conozco a Kona. ¡Buena suerte! :)
seequ
1%xes el mismo que %x. En lugar de (x%2)+1%x, puedes hacerlo (%&2+%)x.
Conor O'Brien
3

Rubí, 65

x=1.0
puts"x=#{x/2+1/x}",<<'1'*2,1
puts"x=#{x/2+1/x}",<<'1'*2,1
1

Como sucede con demasiada frecuencia, este es casi un puerto directo de la solución Python.

histocrat
fuente