▷Raíz cuadrada inversa rápida ✔️ Foro Ayuda 【 2024 】

Por fin luego de mucho luchar hemos dado con la contestación de esta preocupación que muchos de nuestros lectores de nuestro espacio han presentado. Si tienes algún dato que compartir no dudes en compartir tu conocimiento.

Solución:

Gelatina, 41 bytes

l2Ḟ©.*×+®µ23 .*×“9®ġ’_Hµ‘_Ḟ×Ḟ2*$$µ²×³3_×H

¡Pruébelo en línea!

Sé que este desafío se diseñó con la esperanza de que los idiomas del golf lo pasaran mal. En cierto modo, lo hacen; Jelly no tiene primitivas para mirar la representación de un número de punto flotante en la memoria. Sin embargo, todavía es posible resolver el desafío resolviendo “manualmente” cómo se vería la representación usando las definiciones básicas de la aritmética de punto flotante y, de hecho, hay cierto interés matemático en hacer las cosas “de la manera difícil”. Jelly es mucho más terso que (digamos) C, que el hecho de que tenga que hacer más trabajo no evita que el programa sea considerablemente más corto.

Explicación

La entrada es un número de punto flotante, como un número. Para ejecutar el algoritmo de raíz cuadrada inversa rápida, necesitamos encontrar cómo se representaría en la memoria. Jelly no tiene una forma de hacer eso mirando el patrón de bits, pero podemos hacerlo aritméticamente.

Primero, tenga en cuenta que la entrada debe ser positiva (o su raíz cuadrada inversa no estaría definida). Como tal, se presenta en la memoria de la siguiente manera, de mayor a menor importancia:

Un bit cero (el bit de signo, cero significa no negativo, por lo que siempre será cero);
El exponente (dividiendo el número por 2 a la potencia del exponente lo escala en el rango de 1 a 2), representado en 8 bits como su valor menos 127;
La mantisa (el resultado de la división anterior), representada en 23 bits al restar 1 y luego multiplicar por 2²³.

Los resultados de cada uno de estos cálculos se pueden representar directamente en Jelly. Como tal, podríamos generar la misma salida que el convertidor de Cfloat-para-int truco de memoria hace así:

Calcular el exponente
Calcular la mantisa
Tome ((exponente + 127) × 2²³) + (mantisa × 2²³ – 1)

Sin embargo, la última expresión que se muestra aquí se simplifica a la siguiente forma bastante más simple:

2²³ × (exponente + mantisa + 126)
alternativamente, 8388608 × (exponente + mantisa) + 1056964608 (el resultado de multiplicar lo anterior)

Llamemos al exponente + mantisa del número de punto flotante de entrada em para abreviar. (El exponente + mantisa de un número de coma flotante lo define de forma única). En otras palabras, después de la // evil floating point bit level hacking comentario, el programa C está trabajando actualmente con i = 8388608 × em + 1056964608.

Los siguientes pasos en el programa C son reducir a la mitad Iy restarlo de 0x5f3759df (que, en decimal, es 1597463007).
I es (8388608 × em + 1056964608); reducir a la mitad da (4194304 × em + 528482304); la resta da (1068980703 – 4194304 × em).

Luego, C convierte este número de nuevo en un número de punto flotante y. Llamemos al exponente + mantisa de yem ‘. Por lo tanto, lo que el programa C está haciendo efectivamente en el pirateo representativo de punto flotante es resolver la siguiente ecuación:

(1068980703 – 4194304 × em) = (8388608 × em ‘ + 1056964608), que se simplifica a:
12016095 = 4194304 × em + 8388608 × em ‘
em ‘ = (12016095 – 4194304 × em) ÷ 8388608 = (12016095 × 2^-23) – em / 2

Ahora, para convertir esto en Jelly. Tenemos una buena definición aritmética de em y de em ‘, para que podamos traducirlo directamente. Primero, aquí se explica cómo calcular em:

l2Ḟ©.*×+®
l2                 Logarithm of the input, base 2
  Ḟ                Round down to the integer below (produces the exponent)
   ©               Store the exponent in a variable
    .*             Take (½ to the power of the exponent)
      ×            Multiply by the original value, by default
       +®          Add the value of the variable (i.e. the exponent)

El valor original multiplicado por ½ a la potencia del exponente es igual al valor original dividido por 2 a la potencia del exponente, es decir, la mantisa, entonces esto es em.

Obtener em ‘ es muy sencillo desde aquí, si lo queremos. Sin embargo, vamos a necesitar convertir el formato exponente + mantisa nuevamente a un número de punto flotante. Esto se puede hacer sin ambigüedades (el exponente es siempre un número entero, la mantisa va de 1 inclusive a 2 exclusivo). Sin embargo, para extraer el exponente, vamos a querer piso y restar 1. Como tal, en realidad es más corto para generar em ‘ -1.

em ‘ = (12016095 × 2^-23) – em / 2, entonces
em ‘-1 = (3627487 × 2^-23) – em / 2

Podemos codificar esta fórmula en Jelly directamente:

µ23 .*×“9®ġ’_H
µ                  set this point as the new default for missing arguments
 23                restart with 23  
    .*             ½ to the power of that (i.e. 2 to the power -23)
      ×            times
       “9®ġ’       3627487 (compressed representation)
            _H     minus half the value as of the last µ command

Por cierto, necesitamos el espacio porque 23. es un único token en Jelly (que se evalúa como 23½).

El siguiente paso es convertir de em’-1 a un número de punto flotante real y. Podemos extraer el exponente usando Ḟ; entonces la mantisa es em’-1 + 1 – el exponente. Para producir el número de punto flotante, queremos calcular mantisa × 2^exponente:

µ‘_Ḟ×Ḟ2*$$
µ                  set this point as the new default for missing arguments
 ‘                 increment (producing em'-1 + 1)
  _Ḟ               subtract the exponent (producing the mantissa)
    ×              multiply by
     Ḟ2*           2 to the power of the exponent
        $$         parse the previous three links as a group

Finalmente, solo necesitamos manejar la línea marcada // 1st iteration. Esto es solo aritmética normal, por lo que se codifica en Jelly con mucha facilidad. La formula es:

y × (1,5 – (x2 × y²)), donde x2 es la mitad de la entrada original; esto es más corto de expresar como
y ÷ 2 × (3 – (x × y²)), donde x es la entrada original.

Y así es como se ve en Jelly:

µ²×³3_×H
µ                  set this point as the new default for missing arguments
 ²                 square
  ×³               multiply (×) by the original input (³)
    3_             subtract (_) from 3
      ×H           multiply by half the value as of the last µ command

Verificación

Ejecutando este programa en la entrada 2 produce la salida 0.7069300386983334. Este es el mismo valor (teniendo en cuenta las diferencias en el flotador astring conversión) según lo producido por esta respuesta de VBA, y no es igual al valor matemáticamente correcto para 2^-0,5.

FORTRAN, 124 113 caracteres

ahorró 11 Bytes gracias a rafa11111

Sé que esta pregunta es bastante antigua, pero merece una respuesta FORTRAN. No puede superar a Perl o Jelly en el golf, pero al menos no es el peor.

character*9 c
equivalence(r,i)
call getarg(1,c)
read(c,*)y
r=y
i=Z'5f3759df'-ishft(i,-1)
print*,r/2*(3-y*r*r)
end

Lo más difícil es introducir argumentos de línea de comandos en FORTAN. Afortunadamente hay getarg() como alias para get_command_argument(). Tenga en cuenta el uso de una declaración de equivalencia para evitar la conversión de tipos. r y i son simplemente los mismos bytes pero se pueden direccionar como tipos de datos diferentes. Dado que los punteros de FORTRAN no se pueden convertir en otros tipos de datos como en C, este es el camino a seguir en FORTRAN.

Perl, 89 85 caracteres

incluye los símbolos necesarios para declarar e implementar una función

editar: programa independiente. recibe el parámetro de entrada como argumento de línea de comando

$_=unpack'f',pack'i',0x5f3759df-unpack('i',pack'f',$n=shift)/2;
print$_*1.5-$n/2*$_**3

Acuérdate de que tienes la capacidad de valorar esta crónica si topaste tu duda en el momento justo.

¡Haz clic para puntuar esta entrada!

(Votos: 0 Promedio: 0)

Raíz cuadrada inversa rápida