Problema:
En el idioma que elija, escriba la función más corta que devuelve el piso de la raíz cuadrada de un entero de 64 bits sin signo.
Casos de prueba:
Su función debe funcionar correctamente para todas las entradas, pero aquí hay algunas que ayudan a ilustrar la idea:
INPUT ⟶ OUTPUT
0 ⟶ 0
1 ⟶ 1
2 ⟶ 1
3 ⟶ 1
4 ⟶ 2
8 ⟶ 2
9 ⟶ 3
15 ⟶ 3
16 ⟶ 4
65535 ⟶ 255
65536 ⟶ 256
18446744073709551615 ⟶ 4294967295
Reglas:
- Puedes nombrar tu función como quieras. (Las funciones sin nombre, anónimas o lambda están bien, siempre que de alguna manera sean invocables).
- El conteo de personajes es lo que más importa en este desafío, pero el tiempo de ejecución también es importante. Estoy seguro de que puede escanear hacia arriba de forma iterativa para obtener la respuesta en el tiempo O (√n) con un recuento de caracteres muy pequeño, pero el tiempo O (log (n)) realmente sería mejor (es decir, suponiendo un valor de entrada de n, no una longitud de bits de n).
- Probablemente deseará implementar la función usando artitmética puramente entera y / o booleana. Sin embargo, si realmente desea utilizar cálculos de punto flotante, entonces está bien siempre que no llame a funciones de biblioteca. Entonces, simplemente decir
return (n>0)?(uint32_t)sqrtl(n):-1;
en C está fuera de los límites aunque produciría el resultado correcto. Si está usando aritmética de punto flotante, es posible utilizar*
,/
,+
,-
, y exponenciación (por ejemplo,**
o^
si es un operador incorporado en el idioma de su elección, pero exponenciación única de poderes no inferior a 1 ). Esta restricción es para evitar "hacer trampa" llamandosqrt()
o una variante o elevando un valor a la ½ potencia. - Si está utilizando operaciones de punto flotante (ver # 3), no es necesario que el tipo de retorno sea entero; solo que el valor de retorno es un número entero, por ejemplo, floor (sqrt (n)), y puede contener cualquier valor de 32 bits sin signo.
- Si está utilizando C / C ++, puede suponer la existencia de tipos enteros de 64 bits y 32 bits sin signo, por ejemplo,
uint64_t
yuint32_t
como se define enstdint.h
. De lo contrario, solo asegúrese de que su tipo entero sea capaz de contener cualquier número entero sin signo de 64 bits. - Si su idioma no es compatible con enteros de 64 bits (por ejemplo, Brainfuck aparentemente solo tiene soporte de enteros de 8 bits), haga lo mejor que pueda con eso y establezca la limitación en su título de respuesta. Dicho esto, si puedes descubrir cómo codificar un número entero de 64 bits y obtener correctamente la raíz cuadrada del mismo usando la aritmética primitiva de 8 bits, ¡entonces tendrás más potencia!
- ¡Diviértete y sé creativo!
code-golf
math
arithmetic
Todd Lehman
fuente
fuente
O(log_2 n) === O(log_4 n)
.log_4(n) = log_2(n) / log_2(2) = log_2(n) / 2
Respuestas:
CJam, 17 (o 10) bytes
Pruébelo en línea verificando los casos de prueba:
No pasará el último caso de prueba debido a problemas de redondeo, pero como
18446744073709551615
no es un número entero en CJam (es un número entero grande ), seguimos siendo buenos, ¿verdad?De lo contrario, el siguiente código (y un poco más largo) corregirá esos errores:
Ya no es la solución más corta, sino faaast .
Cómo funciona
fuente
<.@%~^&1.5
. ¿Puedo publicar esto como una respuesta separada (ya que es básicamente un puerto exacto suyo)?4294967295
y se4294967296
ve muy similar ...Haskell,
2826Creo que esta es la entrada más corta de cualquier idioma que no fue diseñado para jugar al golf.
Nombra una función
s
con parámetroa
y devuelve uno menos el primer número cuyo cuadrado es mayor quea
. Corre increíblemente lento (O (sqrt n), ¿tal vez?).fuente
[...]!!0
) más corto que head?Golfscript, 17 caracteres
Podía nombrar mi función como quisiera, pero decidí no nombrarla en absoluto. Agregue dos caracteres para nombrarlo, agregue tres para nombrarlo y no lo deje en la pila, reste un carácter si proporcionar un programa completo está bien.
Esta abominación no se ejecuta en tiempo logarítmico en el valor de la entrada, no en tiempo O (sqrt n), se necesita una cantidad lineal de tiempo para producir el resultado. También ocupa mucho espacio. Absolutamente horrendo. Pero ... esto es código-golf.
El algoritmo es:
fuente
Pyth , 14 caracteres
Proporciona una función con nombre, s, que calcula la raíz cuadrada filtrando la lista de 0 a n para que el cuadrado sea más grande que la entrada, luego imprime el último número. No utiliza exponenciación ni flota.
Ejemplo de uso:
fuente
Retina (no competitiva - El lenguaje es más nuevo que el desafío), 43
Mientras trabajaba en esta respuesta , se me ocurrió que se puede usar un método similar para calcular raíces cuadradas enteras usando retina:
Esto se basa en el hecho de que los cuadrados perfectos pueden expresarse como
1+3+5+7+...
, y por corolario, que el número de términos en esta expresión es la raíz cuadrada.Pruébalo en línea. (Se agregó la primera línea para permitir la ejecución de múltiples casos de prueba).
Obviamente, debido a la conversión decimal a unaria, esto solo funcionará para entradas relativamente pequeñas.
fuente
Perl, 133 caracteres
No es el más corto de lejos, pero usa un algoritmo de dígito por dígito para manejar cualquier entrada de tamaño, y se ejecuta en tiempo O (log n). Convierte libremente entre números como cadenas y números como números. Dado que el producto más grande posible es la raíz hasta ahora con el cuadrado de un solo dígito, debería ser capaz de sacar la raíz cuadrada de hasta 120 bits más o menos en un sistema de 64 bits.
Descomprimido, es decir:
fuente
if length%2
lugar deif(length)%2
? Eso afeitaría a 1 personaje. Además, ¿funcionaría decir en$y=$z,$d=$_ if
lugar de($y,$d)=($z,$_)if
? Creo que eso afeitaría a 3 personajes más.for
ciclo como:$a<($z=$_*(20*$r+$_))or$y=$z,$d=$_ for(1..9);
%2
), pero las otras son válidas. Los trabajaré.for
no necesita paréntesis; Agregar eso a sus sugerencias me da 6 caracteres en total. ¡Gracias!Matlab (56) / Octava (55)
Resuelve la raíz cuadrada utilizando un método de punto fijo. Converge en un máximo de 36 pasos (para 2 ^ 64-1 como argumento) y luego comprueba si es la más baja de las raíces enteras 'posibles'. Como siempre usa 36 iteraciones, tiene un tiempo de ejecución de O (1) = P
Se supone que el argumento es uint64.
Matlab:
Octava:
fuente
Ruby - 36 caracteres
fuente
while
ciclo termina precisamente cuando g converge al piso (√n), que es el valor deseado. ¿Ves algún caso en el que esto no sea cierto?Pitón (39)
El enfoque recursivo natural. Cuenta las posibles raíces cuadradas hasta que su cuadrado sea demasiado alto, luego desciende por 1. Use Stackless Python si le preocupa exceder la profundidad de la pila.
El
and/or
idioma es equivalente al operador ternario comoEditar: Me puede en lugar de obtener 25 caracteres mediante la explotación de la regla ", es posible utilizar
*
,/
,+
,-
, y exponenciación (por ejemplo,**
o^
si es una exponenciación operador incorporado en el idioma de su elección, pero sólo en las facultades no inferior a 1). " (Editar: Aparentemente, Dennis ya encontró y explotó este truco).Utilizo el operador
//
de división entera de Python 3 para redondear hacia abajo. Desafortunadamente, paso muchos personajes para que el cason=0
no dé una división por 0 error. Si no fuera por eso, podría hacer 18 caracteresLas reglas tampoco decían que la función tenía que nombrarse (dependiendo de cómo interprete "Puede nombrar su función como quiera"), pero si lo hace, son dos caracteres más.
fuente
C99 (58 caracteres)
Este es un ejemplo de una respuesta que no consideraría buena, aunque es interesante para mí desde el punto de vista del código golf porque es muy perverso, y pensé que sería divertido incluirlo en la mezcla:
Original: 64 caracteres
La razón de que este sea terrible es que se ejecuta en tiempo O (√n) en lugar de tiempo O (log (n)). (Donde n es el valor de entrada).
Editar: 63 caracteres
Cambiando
r-1
a--r
y contiguo areturn
:Editar: 62 caracteres
Mover el incremento del ciclo al interior de la parte condicional del ciclo (nota: esto tiene un comportamiento no garantizado porque el orden de las operaciones con respecto al operador de preincremento es específico del compilador):
Editar: 60 caracteres
Agregar un
typedef
para ocultaruint64_t
(crédito al usuario technosaurus por esta sugerencia).Editar: 58 caracteres
Ahora requiere que el segundo parámetro se pase como 0 en la invocación de la función, por ejemplo, en
r(n,0)
lugar de solor(n)
. Ok, por mi vida, en este punto no puedo ver cómo comprimir esto más ... ¿alguien?fuente
uint64_t s(uint64_t n){for(uint64_t r=n;--n>r/n;);return n;}
.--n
cuandon==0
sería –1, y estos son valores sin signo, entonces –1 sería 2⁶⁴ – 1.#define Z uint64_t
... o typedef salvará a un parn/++r/r
tiene un comportamiento indefinido ...Golfscript - 14 caracteres
Encuentre el número más pequeño
i
menor que la entradan
para la cualn < i*i
. Retornoi - 1
.Es decir
[0..n-1].first(i => n < i*i) - 1
Explicación para aquellos que no conocen Golfscript también, para una llamada de muestra con entrada
5
:fuente
1
probablemente toma dos caracteres.Haskell,
147138134128 bytesNo es el código más corto del mundo, pero se ejecuta en O (log n) y en números de tamaño arbitrario:
Esto hace una búsqueda binaria del rango [0..n] para encontrar la mejor aproximación más baja a sqrt (n). Aquí hay una versión sin golf:
Editar: guardó dos bytes reemplazando las cláusulas "de lo contrario" con "0 <1" como una versión más corta de "Verdadero", y algunas más al incluir g * g.
Además, si está satisfecho con O (sqrt (n)) simplemente podría hacer
para 35 personajes, pero ¿qué tan divertido es eso?
Edición 2: me acabo de dar cuenta de que los pares están ordenados por orden de diccionario, en lugar de hacer min2Cycle. mapa fst, solo puedo hacer fst. min2Cycle. En el código de golf, eso se traduce en reemplazar f $ map fst por fst $ f, ahorrando 4 bytes más.
Edición 3: ¡Ahorré seis bytes más gracias a proudhaskeller!
fuente
JavaScript
918886: optimizado para la velocidadJavaScript 46: no optimizado para la velocidad
Aquí hay un JSFiddle: http://jsfiddle.net/rmadhuram/1Lnjuo4k/
fuente
function s(n){for(a=1;++a*a<n;);return a}
C 95
97Editar Typedef, sugerido por @Michaelangelo
Esto debería ser más o menos una implementación sencilla del algoritmo Heron. La única peculiaridad es calcular el desbordamiento de números enteros evitando: a = (m + n) / 2 no funciona para números biiiig.
fuente
C #
646255Dado que este es un código de golf (y soy terrible con las matemáticas), y el tiempo de ejecución es simplemente una sugerencia, he hecho el enfoque ingenuo que se ejecuta en tiempo lineal:
( prueba en dotnetfiddle )
Por supuesto, es terriblemente lento para entradas más grandes.
fuente
return i-1
areturn--i
?i*i<=a
, ¿se garantiza que sea una aritmética de enteros del tipo habitual? (No estoy familiarizado con C #.) Si es así, y si C # permite la conversión de entero implícito a booleano como lo hace C, entonces podría guardar un carácter más al cambiarlo aa/i/i
.Decimal
mayor valor máximo y precisión) para evitar el desbordamiento ya que el resultado de la multiplicación podría potencialmente ir un paso más alláUInt64.MaxValue
. Pero C # no tiene conversiones implícitas a booleanas de todos modos. Sinreturn
embargo, debería poder cambiarlo , gracias. Lo haré cuando regrese a una computadora.Clojure - 51 o 55 bytes
Comprueba todos los números de n a 0, dando el primero donde
x^2 <= n
. El tiempo de ejecución esO(n - sqrt n)
Sin nombre:
Llamado:
Ejemplo:
fuente
Befunge 93: 48 bytes o 38 caracteres
Pruébalo por aquí.
fuente
Cobra - 62
Lote - 74
fuente
Haskell,
535049 caracteres, O (log n)Esta solución implementa el método newton-raphson, aunque busca enteros en lugar de flotantes. wiki: http://en.wikipedia.org/wiki/Newton%27s_method
la complejidad parece ser sobre O (log n), pero ¿hay alguna prueba de ello? por favor responda en los comentarios.
fuente
\g->div(n+g^2)$2*g
ahorra 7 bytes.J (10)
Muy, muy, muy inspirado por la respuesta de @Dennis :
Y un poco más largo, pero con mejor rendimiento (sospecho):
floor(halve under log)
Para ejecutar, se introducen partes sangradas:
fuente
APL - 12 caracteres, 19 bytes
ejemplo de uso:
devuelve 4
Vector de prueba
devoluciones
1 1 1 1 2 2 3 3 4 255 256 4294967296
Probar en línea
Muchas gracias a : usuario "ssdecontrol" por algoritmo
fuente
0
→1
! Usando Dyalog APL , puede configurar⎕DIV←1
(que muchos usan por defecto) para obtener el resultado correcto.C99 (108 caracteres)
Aquí está mi propia solución en C99, que está adaptada de un algoritmo en un artículo de Wikipedia . Estoy seguro de que debe ser posible hacerlo mucho mejor que esto en otros idiomas.
Golfizado:
Parcialmente golfizado:
Sin golf:
fuente
a
, uson
.n
para que, justo antes de regresar, pudiera hacer la afirmación (no mostrada) de que r ^ 2 <= n <(r + 1) ^ 2. Con esa afirmación omitida, ya no es necesario mantenersen
intacto.const
en la versión sin golf.JavaScript
7381 (para cumplir con el requisito de números de 64 bits)n=prompt();g=n/3;do{G=g,g=(n/g+g)/2}while(1E-9<Math.abs(G-g))alert(Math.floor(g))
Implementando el algoritmo de Heron of Alexandria ...
fuente
|0
afectar hasta 32 bits, mientras queMath.floor
es más efectivo en 64 bits ... He actualizado mi código, teniendo que tomar 8 caracteres adicionales para hacerlo ...Powershell (52) Limitado a Int32 (-2,147,483,648 a 2,147,483,647)
Estoy gritando a Powershell en este momento tratando de hacer que el último caso de prueba funcione, pero no importa lo que haga, Powershell termina usando la variable de canalización $ _ como Int32, y no puedo encontrar una forma de evitarlo en este momento.
Así que limitaré mi respuesta por ahora. Si puedo encontrar una mejor manera de manejar uint64s, editaré. (¡El último caso de prueba es demasiado grande para el tipo Int64 normal de Powershell, por cierto!)
Aquí hay algunos casos de prueba (con un poco de salida adicional que solía rastrear el tiempo)
No sé mis O () s, pero esto parece un salto bastante dramático.
fuente
Advertencia: a partir de 2011, R no tenía soporte incorporado para enteros de 64 bits como había supuesto. Estas respuestas pueden ser inválidas en ese tecnicismo, pero de nuevo R ha cambiado mucho en los últimos 3 años.
R, 85
Usando el método de Newton:
que converge cuadráticamente. +2 caracteres para asignar la función a una variable para la evaluación comparativa:
R, 37
Fuerza bruta:
Y el mismo cheque:
R, 30
El truco de exponenciación barato / brillante :
que también es muy rápido (aunque no tan rápido como el incorporado):
fuente
C, 38
Traducción de mi presentación Forth. Lento pero correcto. O (√n). Probado en OS X (64 bits).
fuente
dc, 50 bytes
Espaciado y explicado:
fuente
C,
139137136 bytesMi primer intento en el código de golf. Parece que es el más corto en C que cumple con el requisito "eficiente", ya que se ejecuta en el
O(log n)
tiempo, utilizando solo cambios de suma y bits. Aunque estoy seguro de que aún podría ser más corto ...También debería funcionar bien para valores enteros más grandes siempre que la
a=32
parte se cambie aa=NUMBITS/2
.fuente
(t++)
lugar de solot++
en la tarear
?a--+1
forma de evitar escribira-- != UINT64_C(-1)
. ¿Aprendiste ese truco en alguna parte o lo inventaste tú mismo?C - 50 (61 sin global)
Utiliza variables globales como parámetro y valor de retorno para ahorrar espacio.
Sin versión global:
fuente
C ++ 125
fuente
x+=(d<0)-0.5;
... salva 5 personajes más?main
es una función, pero no se puede llamar desde dentro de un programa comof(y)
sería).while((d=x*x-y)>0.5)
lugar dewhile((d=(x*x-y))>0.5)
. Guarda 2 personajes más. :)