Entero raíz cuadrada del entero [cerrado]

12

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:

  1. 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).
  2. 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).
  3. 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" llamando sqrt()o una variante o elevando un valor a la ½ potencia.
  4. 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.
  5. Si está utilizando C / C ++, puede suponer la existencia de tipos enteros de 64 bits y 32 bits sin signo, por ejemplo, uint64_ty uint32_tcomo se define en stdint.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.
  6. 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!
  7. ¡Diviértete y sé creativo!
Todd Lehman
fuente
77
"pero el tiempo O (log₄ (n)) realmente sería mejor". - cuanto mejor? ¿Hay un bono? ¿Es un requisito difícil? ¿Es esencialmente un desafío separado? ¿Es solo una buena idea que realmente no afecta la puntuación?
John Dvorak
3
Normalmente se usa el tamaño de la entrada en lugar del valor de entrada para derivar la complejidad algorítmica. En ese sentido, el algoritmo de incremento y reintento es exponencial en velocidad.
John Dvorak
3
Umm ... O(log_2 n) === O(log_4 n). log_4(n) = log_2(n) / log_2(2) = log_2(n) / 2
John Dvorak
1
¿Cuenta 2/4?
Milo
1
La mayoría de los tipos de datos de punto flotante no tienen la precisión necesaria para esta tarea de todos modos. 53 bits significativos no son suficientes para todo el rango de entrada.
user2357112 es compatible con Monica el

Respuestas:

14

CJam, 17 (o 10) bytes

{_1.5#\/i}

Pruébelo en línea verificando los casos de prueba:

[0 1 2 3 4 8 9 15 16 65535 65536 18446744073709551615]{_1.5#\/i}%N*

No pasará el último caso de prueba debido a problemas de redondeo, pero como 18446744073709551615no 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:

{__1.5#\/i_2#@>-}

Ya no es la solución más corta, sino faaast .

Cómo funciona

__    " Duplicate the integer twice. ";
1.5#  " Raise to power 1.5. Note that, since 1.5 > 1, this doesn't break the rules. ";
\     " Swap the result with the original integer. ";
/     " Divide. ";
i     " Cast to integer. ";
_2#   " Push square of a copy. ";
@     " Rotate the orginal integer on top of the stack. ";
>-    " If the square root has been rounded up, subtract 1. ";
Dennis
fuente
¡Jajaja! Uy, está bien, me tienes en un tecnicismo allí. No debería haber dicho poderes fraccionarios. Pero su código de hecho obedece las reglas establecidas, así que lo estoy votando. :)
Todd Lehman
2
¿CJam tiene decimales de precisión arbitraria para cubrir todo el rango de entrada?
isaacg
Además, un buen truco de usar NaN -> 0 en cast to int.
isaacg
Idea ingeniosa, sino que también se puede representar en J exactamente en el mismo recuento de caracteres: <.@%~^&1.5. ¿Puedo publicar esto como una respuesta separada (ya que es básicamente un puerto exacto suyo)?
Sepıʇǝɥʇuʎs
@ ɐɔıʇǝɥʇuʎs: adelante. Pero acabo de descubrir que mi solución puede redondearse incorrectamente para grandes números, incluido el último caso de prueba. En mi defensa, pasó mi inspección solo porque 4294967295y se 4294967296ve muy similar ...
Dennis
10

Haskell, 28 26

Creo que esta es la entrada más corta de cualquier idioma que no fue diseñado para jugar al golf.

s a=[x-1|x<-[0..],x*x>a]!!0

Nombra una función scon parámetro ay devuelve uno menos el primer número cuyo cuadrado es mayor que a. Corre increíblemente lento (O (sqrt n), ¿tal vez?).

Zaq
fuente
1
¿No sería un índice de lista ( [...]!!0) más corto que head?
isaacg
@isaacg Sí, lo haría. Gracias :-)
Zaq
7

Golfscript, 17 caracteres

{).,{.*1$<},,\;(}

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:

n => [0..n].filter(x => x*x < n+1).length - 1
John Dvorak
fuente
¡¡Me encanta!! ¡Buen trabajo! Eso es bellamente perverso.
Todd Lehman
7

Pyth , 14 caracteres

DsbR;fgb*TTL'b

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.

Dsb       def s(b):
R;        return last element of
f         filter(lambda T:
gb*TT                     b>=T*T,
L'b                       range(b+1))

Ejemplo de uso:

python3 pyth.py <<< "DsbR;fgb*TTL'b       \msd[0 1 2 3 4 8 9 15 16 65535 65536"
[0, 1, 1, 1, 2, 2, 3, 3, 4, 255, 256]
isaacg
fuente
7

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:

.+
$*
^
1:
+`(1+):(11\1)
1 $2:
1+:$|:1+

1+

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.

Trauma digital
fuente
44
(El lenguaje es más nuevo que el desafío)
mbomb007
@ mbomb007 Bastante justo: título editado. Esta respuesta definitivamente está en la categoría "porque se puede hacer", y no pretende competir en el desafío de ninguna manera significativa.
Trauma digital
1
Sé a qué te refieres .
mbomb007
6

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.

sub{($_)=@_;$_="0$_"if(length)%2;$a=$r="";while(/(..)/g){
$a.=$1;$y=$d=0;$a<($z=$_*(20*$r+$_))or$y=$z,$d=$_ for 1..9;$r.=$d;$a-=$y}$r}

Descomprimido, es decir:

sub {
  my ($n) = @_;
  $n = "0$n" if length($n) % 2; # Make an even number of digits
  my ($carry, $root);
  while ($n =~ /(..)/g) { # Take digits of $n two at a time
    $carry .= $1;         # Add them to the carry
    my ($product, $digit) = (0, 0);
    # Find the largest next digit that won't overflow, using the formula
    # (10x+y)^2 = 100x^2 + 20xy + y^2 or
    # (10x+y)^2 = 100x^2 + y(20x + y)
    for my $trial_digit (1..9) {
      my $trial_product = $trial_digit * (20 * $root + $trial_digit);
      if ($trial_product <= $carry) {
        ($product, $digit) = ($trial_product, $trial_digit);
      } 
    } 
    $root .= $digit;
    $carry -= $product;
  } 
  return $root;
}
hobbs
fuente
¡Agradable! Me preguntaba cuándo alguien publicaría una respuesta de Perl. Por cierto, ¿funciona decir en if length%2lugar de if(length)%2? Eso afeitaría a 1 personaje. Además, ¿funcionaría decir en $y=$z,$d=$_ iflugar de ($y,$d)=($z,$_)if? Creo que eso afeitaría a 3 personajes más.
Todd Lehman
Y esto se está volviendo un poco perverso, pero creo que puedes reducir 1 más aún reescribiendo el forciclo como:$a<($z=$_*(20*$r+$_))or$y=$z,$d=$_ for(1..9);
Todd Lehman
La primera sugerencia no funciona (intenta tomar la longitud de un hash llamado %2), pero las otras son válidas. Los trabajaré.
hobbs
1
El postfix @ToddLehman forno necesita paréntesis; Agregar eso a sus sugerencias me da 6 caracteres en total. ¡Gracias!
hobbs
5

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:

function x=q(s)
x=1
for i = 1:36
    x = (x+s/x)/2
end
if x*x>s
    x=x-1
end

Octava:

function x=q(s)
x=1
for i = 1:36
    x = (x+s/x)/2
end
if x*x>s
    x-=1
end
falla
fuente
Este es un método nuevo para mí, y resulta ser bastante bueno. +1
seequ
1
Básicamente es en.wikipedia.org/wiki/…, que es uno de los primeros métodos numéricos conocidos que se estima tiene alrededor de 3700 años. Se puede justificar por en.wikipedia.org/wiki/Banach_fixed-point_theorem que tiene una prueba sorprendentemente fácil, es realmente agradable =)
error
5

Ruby - 36 caracteres

s=->n{g=n;g=(g+n/g)/2 while g*g>n;g}
OI
fuente
¡Bien hecho! ¿Cuál es el peor tiempo de ejecución del caso?
Todd Lehman
¿Qué pasa en el caso de que g * g <n y la respuesta aún no esté cerca del valor deseado? ¿No se detendrá el guión?
WallyWest
1
@ToddLehman Sinceramente, no lo sé. : - / Este es el método babilónico . Esto es lo que parece ser una buena prueba de la complejidad promedio . La suposición inicial del número en sí es bastante mala, pero tendría que sentarme y realmente asimilar esa prueba para comprender el peor de los casos. Lo intentaré cuando tenga más tiempo libre. :-)
OI
@WallyWest Entiendo que el whileciclo termina precisamente cuando g converge al piso (√n), que es el valor deseado. ¿Ves algún caso en el que esto no sea cierto?
OI
4

Pitón (39)

f=lambda n,k=0:k*k>n and k-1or f(n,k+1)

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/oridioma es equivalente al operador ternario como

f=lambda n,k=0:k-1 if k*k>n else f(n,k+1)

Editar: 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).

lambda n:n**1.5//max(n,1)

Utilizo el operador //de división entera de Python 3 para redondear hacia abajo. Desafortunadamente, paso muchos personajes para que el caso n=0no dé una división por 0 error. Si no fuera por eso, podría hacer 18 caracteres

lambda n:n**1.5//n 

Las 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.

xnor
fuente
- Gracias, lo aclararé. Solo tiene que ser una función. No tiene que ser nombrado. Entonces, las funciones lambda están bien. Hubiera mencionado esto desde el principio si hubiera pensado en ello. Estaba pensando demasiado en términos de C cuando publiqué la pregunta.
Todd Lehman
4

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

uint64_t r(uint64_t n){uint64_t r=1;for(;n/r/r;r++);return r-1;}

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-1a --ry contiguo a return:

uint64_t r(uint64_t n){uint64_t r=1;for(;n/r/r;r++);return--r;}

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):

uint64_t r(uint64_t n){uint64_t r=0;for(;n/++r/r;);return--r;}

Editar: 60 caracteres

Agregar un typedefpara ocultar uint64_t(crédito al usuario technosaurus por esta sugerencia).

typedef uint64_t Z;Z r(Z n){Z r=0;for(;n/++r/r;);return--r;}

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 solo r(n). Ok, por mi vida, en este punto no puedo ver cómo comprimir esto más ... ¿alguien?

typedef uint64_t Z;Z r(Z n,Z r){for(;n/++r/r;);return--r;}
Todd Lehman
fuente
Si usted está dispuesto a llamarlo C ++ y decremento en lugar de la subasta que sería capaz de afeitarse un par de caracteres: uint64_t s(uint64_t n){for(uint64_t r=n;--n>r/n;);return n;}.
Fors
@Fors - ¡Buen enfoque! Desafortunadamente, ¿eso no causará una división entre cero para la entrada de 1? Además, ¿qué hará para una entrada de 0? Porque --ncuando n==0sería –1, y estos son valores sin signo, entonces –1 sería 2⁶⁴ – 1.
Todd Lehman
1
#define Z uint64_t ... o typedef salvará a un par
technosaurus
@technosaurus - Ah sí, eso ahorra 2. Gracias. :-)
Todd Lehman
1
La expresión n/++r/rtiene un comportamiento indefinido ...
aschepler
4

Golfscript - 14 caracteres

{.,\{\.*<}+?(}

Encuentre el número más pequeño imenor que la entrada npara la cual n < i*i. Retorno i - 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:

.        //Duplicate input.  Stack: 5 5
,        //Get array less than top of stack.  Stack: 5 [0 1 2 3 4]
\        //Switch top two elements of stack.  Stack: [0 1 2 3 4] 5
{\.*<}+  //Create a block (to be explained), and prepend the top of the stack.  
         //Stack: [0 1 2 3 4]{5\.*<}
?        //Find the first element of the array for which the block is true. 
         //So, find the first element of [0 1 2 3 4] for which {5\.*<} evaluates to true.
         //The inner block squares a number and returns true if it is greater than the input.
(        //Decrement by 1 
Ben Reich
fuente
Ooh, son 3 caracteres más cortos que la mejor respuesta anterior de Golfscript. ¡Buen trabajo!
Todd Lehman
Arreglar esto para dar la respuesta correcta para la entrada 1probablemente toma dos caracteres.
Peter Taylor
4

Haskell, 147 138 134 128 bytes

No es el código más corto del mundo, pero se ejecuta en O (log n) y en números de tamaño arbitrario:

h x=div(x+1)2
n%(g,s)|g*g<n=(g+s,h s)|g*g>n=(g-s,h s)|0<1=(g,0)
f(x:r@(y:z:w))|x==z=min x y|0<1=f r
s n=fst$f$iterate(n%)(n,h n)

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:

-- Perform integer division by 2, rounding up
half x = x `div` 2 + x `rem` 2

-- Given a guess and step size, refine the guess by adding 
-- or subtracting the step as needed.  Return the new guess
-- and step size; if we found the square root exactly, set
-- the new step size to 0.
refineGuess n (guess, step)
    | square < n  =  (guess + step, half step)
    | square > n  =  (guess - step, half step)
    | otherwise   =  (guess, 0)
    where square = guess * guess     

-- Begin with the guess sqrt(n) = n and step size (half n),
-- then generate the infinite sequence of refined guesses.
-- 
-- NOTE: The sequence of guesses will do one of two things:
--         - If n has an integral square root m, the guess 
--           sequence will eventually be m,m,m,...
--         - If n does not have an exact integral square root,
--           the guess sequence will eventually alternate
--           L,U,L,U,.. between the integral lower and upper
--           bounds of the true square root.
--        In either case, the sequence will reach periodic
--        behavior in O(log n) iterations.
guesses n = map fst $ iterate (refineGuess n) (n, half n)

-- Find the limiting behavior of the guess sequence and pick out
-- the lower bound (either L or m in the comments above)
isqrt n = min2Cycle (guesses n)
    where min2Cycle (x0:rest@(x1:x2:xs))
            | x0 == x2    =   min x0 x1
            | otherwise   =   min2Cycle rest

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

s n=(head$filter((>n).(^2))[0..])-1

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!

Matt Noonan
fuente
1
puede reemplazar (div x 2 + rem x 2) con div (x + 1) 2, en su función "media"
orgulloso haskeller
De hecho, tengo una solución propia que tiene 49 caracteres y se resuelve en O (log n), pero solo tengo 2 votos a favor ;-(. No entiendo por qué
Haskeller orgulloso
4

JavaScript 91 88 86: optimizado para la velocidad

function s(n){var a=1,b=n;while(Math.abs(a-b)>1){b=n/a;a=(a+b)/2}return Math.floor(a)}

JavaScript 46: no optimizado para la velocidad

function s(n){a=1;while(a*a<=n)a++;return a-1}

Aquí hay un JSFiddle: http://jsfiddle.net/rmadhuram/1Lnjuo4k/

Rajkumar Madhuram
fuente
1
Bienvenido a PPCG! Puede usar <s> 91 </s> <s> 88 </s> para tachar. Intenté hacer la edición pero estabas editando al mismo tiempo, así que te dejaré hacerlo.
Rainbolt
1
O podría hacerlo en 41 caracteres como este:function s(n){for(a=1;++a*a<n;);return a}
Rhubarb Custard
4

C 95 97

Editar 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.

typedef uint64_t Z;
Z q(Z x)
{
   Z n=1,a=x,m=0;
   for(;a-m&&a-n;) n=a,m=x/n,a=m/2+n/2+(m&n&1);
   return a;
}
edc65
fuente
Buen trabajo para evitar el desbordamiento, no solo por hacerlo correctamente, sino también por pensar en ello y probarlo. Definitivamente apreciado.
Todd Lehman
Por cierto, es curioso lo costosa que puede ser la división en algunas CPU. Aunque este algoritmo se ejecuta en aproximadamente la mitad de los pasos que el algoritmo de ábaco, tiene un tiempo de ejecución que es aproximadamente 5 veces más lento que el algoritmo de ábaco cuando lo comparo en mi CPU Core i7, que no le gusta hacer la división. De todos modos, pero el tiempo de ejecución no es importante aquí, solo el tamaño. :) ¡Qué buen trabajo!
Todd Lehman
4

C # 64 62 55

Dado que este es un (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:

decimal f(ulong a){var i=0m;while(++i*i<=a);return--i;}

( prueba en dotnetfiddle )

Por supuesto, es terriblemente lento para entradas más grandes.

Beto
fuente
1
¿Podrías afeitarte a un personaje cambiando return i-1a return--i?
Todd Lehman
En la expresión 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 a a/i/i.
Todd Lehman
1
@ToddLehman Eso en realidad es una aritmética de punto fijo ( Decimalmayor 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. Sin returnembargo, debería poder cambiarlo , gracias. Lo haré cuando regrese a una computadora.
Bob
3

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:

(fn[x](first(filter #(<=(* % %)x)(range x -1 -1))))

Llamado:

(defn f[x](first(filter #(<=(* % %)x)(range x -1 -1))))

Ejemplo:

(map (fn[x](first(filter #(<=(* % %)x)(range x -1 -1)))) (range 50))
=> (0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7)
seequ
fuente
3

Befunge 93: 48 bytes o 38 caracteres

101p&02p>02g01g:*`#v_01g1-.@
        ^  p10+1g10<        

Pruébalo por aquí.

AndoDaan
fuente
1
Ok, eso es genial. ¡Buen trabajo! Ingresé 17, hice clic en Creep y luego en Ejecutar, ¡y apareció 4! :)
Todd Lehman
3

Cobra - 62

do(n as uint64)as uint64
    o=n-n
    while o*o<n,o+=1
    return o

Lote - 74

set a=0
:1
set /ab=%a%*%a%
if %b% LSS %1 set /aa=%a%+1&goto 1
echo %a%
Οurous
fuente
3

Haskell, 53 50 49 caracteres, O (log n)

s n=until((<=n).(^2))(\g->g-1-div(g^2-n-1)(2*g))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.

orgulloso Haskeller
fuente
\g->div(n+g^2)$2*gahorra 7 bytes.
Anders Kaseorg
3

J (10)

Muy, muy, muy inspirado por la respuesta de @Dennis :

<.@%~^&1.5

Y un poco más largo, pero con mejor rendimiento (sospecho):

<.@(-:&.^.)

floor(halve under log)

Para ejecutar, se introducen partes sangradas:

   f=:<.@%~^&1.5
   f 0 8 12 16
0 2 3 4
   g=:<.@(-:&.^.)
   g 0 8 12 16
0 2 3 4
ɐɔıʇǝɥʇuʎs
fuente
¿Cómo ejecutas esto para un entero dado?
Dennis
1
@Dennis Ver respuesta
Sepıʇǝɥʇuʎs
3

APL - 12 caracteres, 19 bytes

{⌊(⍵*1.5)÷⍵}

ejemplo de uso:

{⌊(⍵*1.5)÷⍵}17

devuelve 4

Vector de prueba

{⌊(⍵*1.5)÷⍵}¨0 1 2 3 4 8 9 15 16 65535 65536 18446744073709551615

devoluciones

1 1 1 1 2 2 3 3 4 255 256 4294967296

Probar en línea

Muchas gracias a : usuario "ssdecontrol" por algoritmo

QuantumKarl
fuente
1
Bienvenido a PPCG! Normalmente puntuamos APL como un byte por carácter. A menos que el desafío lo especifique, no hay necesidad de contar en UTF-8. Cualquier codificación existente está bien, y hay una antigua página de códigos APL de antaño que usa un solo byte para cada carácter. El hecho de que APL sea anterior a ASCII es una mala razón para penalizarlo por usar caracteres que no son ASCII. ;) (Dicho esto, este desafío bastante antiguo parece ser
Martin Ender
@MartinEnder Gracias por la cálida bienvenida y consejos :)
QuantumKarl
1
01! Usando Dyalog APL , puede configurar ⎕DIV←1(que muchos usan por defecto) para obtener el resultado correcto.
Adám
2

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:

uint64_t s(uint64_t n){uint64_t b=1,r=0;while(n/b/4)b*=4;for(;b;b/=4,r/=2)n>=r+b?r+=b,n-=r,r+=b:0;return r;}

Parcialmente golfizado:

uint64 uint64_sqrt(uint64 n)
{
  uint64 b = 1, r = 0;
  while (b <= n / 4)
    b *= 4;
  for (; b; b /= 4, r /= 2)
    if (n >= r + b)
      { r += b; n -= r; r+= b; }
  return r;
}

Sin golf:

uint64_t uint64_sqrt(uint64_t const n)
{
  uint64_t a, b, r;

  for (b = 1; ((b << 2) != 0) && ((b << 2) <= n); b <<= 2)
    ;

  a = n;
  r = 0;
  for (; b != 0; b >>= 2)
  {
    if (a >= r + b)
    {
      a -= r + b;
      r = (r >> 1) + b;
    }
    else
    {
      r >>= 1;
    }
  }

  // Validate that r² <= n < (r+1)², being careful to avoid integer overflow,
  // which would occur in the case where n==2⁶⁴-1, r==2³²-1, and could also
  // occur in the event that r is incorrect.
  assert(n>0? r<=n/r : r==0);  // Safe way of saying r*r <= n
  assert(n/(r+1) < (r+1));     // Safe way of saying n < (r+1)*(r+1)

  return r;
}
Todd Lehman
fuente
1
Sugerencia: no es necesario a, uso n.
edc65
Ah, sí. Gracias. En mi versión original, estaba manteniendo npara 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 mantenerse nintacto.
Todd Lehman
@ edc65 - Gracias de nuevo por señalarlo. Actualicé mi código para reflejar eso, así como también agregué otros trucos de golf. También se agregaron las afirmaciones originales y se hizo n consten la versión sin golf.
Todd Lehman
2

JavaScript 73 81 (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 ...

WallyWest
fuente
¡Agradable! ¿Funciona esto para todas las entradas enteras de 64 bits sin signo?
Todd Lehman
Por más que lo intente, esto solo parece funcionar hasta 32 bits ... Para mi decepción ...
WallyWest
Seguramente el último | 0 trunca cualquier valor a 32 bits. ¿Usa Math.floor en su lugar?
edc65
@ edc65 Tienes razón en realidad, parece |0afectar hasta 32 bits, mientras que Math.floores más efectivo en 64 bits ... He actualizado mi código, teniendo que tomar 8 caracteres adicionales para hacerlo ...
WallyWest
@ edc65 Acabo de pensar ... ¿~~ x funcionaría en 64 bits?
WallyWest
2

Powershell (52) Limitado a Int32 (-2,147,483,648 a 2,147,483,647)

function f($n){($n/2)..0|%{if($_*$_-le$n){$_;exit}}}

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)

f 17
4
Elapsed Time: 0.0060006 seconds

f 65
8
Elapsed Time: 0.0050005 seconds

f 65540
256
Elapsed Time: 1.7931793 seconds

f 256554
506
Elapsed Time: 14.7395391 seconds

No sé mis O () s, pero esto parece un salto bastante dramático.

fuandon
fuente
2

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:

function(n){s=F
x=n
y=(1/2)*(x+n/x)
while(abs(x-y)>=1){x=y
y=(1/2)*(x+n/x)}
trunc(y)}

que converge cuadráticamente. +2 caracteres para asignar la función a una variable para la evaluación comparativa:

microbenchmark(q(113424534523616))
# Unit: microseconds
#                expr    min      lq median      uq    max neval
#  q(113424534523616) 24.489 25.9935 28.162 29.5755 46.192   100

R, 37

Fuerza bruta:

function(n){t=0
while(t^2<n) t=t+1
t}

Y el mismo cheque:

microbenchmark::microbenchmark(q(113424534523616),times=1)
# Unit: seconds
#                 expr      min       lq   median       uq      max neval
#   q(113424534523616) 4.578494 4.578494 4.578494 4.578494 4.578494     1

R, 30

El truco de exponenciación barato / brillante :

function(n) trunc(n^(1.5)/n)

que también es muy rápido (aunque no tan rápido como el incorporado):

microbenchmark(q(113424534523616),sqrt(113424534523616))
# Unit: nanoseconds
#                   expr min    lq median    uq  max neval
#     z(113424534523616) 468 622.5  676.5 714.5 4067   100
#  sqrt(113424534523616)  93 101.0  119.0 160.5 2863   100
Shadowtalker
fuente
2

C, 38

f(n){int m;while(++m*m<=n);return--m;}

Traducción de mi presentación Forth. Lento pero correcto. O (√n). Probado en OS X (64 bits).

Piedra de Darren
fuente
2

dc, 50 bytes

dc -e"?dsist[lt2/dstd*li<B]dsBx[lt1+dstd*li!<A]dsAxlt1-f"

Espaciado y explicado:

               # The idea here is to start with the input and reduce it quickly until it is
               # less than what we want, then increment it until it's just right
?              # Take input from stdin
d si st        # Duplicate input, store in `i' and in `t'
[              # Begin macro definition (when I write in dc, "macro"=="function")
 lt            # Load t, our test term
 2/            # Divide t by two
 d st          # Store a copy of this new term in `t'
 d*            # Duplicate and multiply (square)
 li<B          # Load i; if i<(t^2), execute B
] d sB x       # Duplicate, store function as `B', and execute
               # Loop ends when t^2 is less than i
[              # Begin macro definition
 lt            # Load t, our test term
 1+            # Increment
 d st          # Store a copy of this new term in `t'
 d*            # Duplicate and multiply (square)
 li!<A         # Load i; if i>=(t^2), execute A
] d sA x       # Duplicate, store function as `A', and execute
               # Loop ends when t^2 == i+1
lt 1- f        # Load t, decrement, and dump stack
Joe
fuente
Parece que el último caso de prueba falla. Intentaré arreglarlo.
Joe
Resuelto. Ahora acepta entradas muy grandes; casualmente, la solución me permitió eliminar algunos códigos feos al principio.
Joe
2

C, 139 137 136 bytes

Mi 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=32parte se cambie a a=NUMBITS/2.

typedef uint64_t x;x f(x o){x a=32,t=0,r=0,y=0,z;for(;a--+1;){z=(x)3<<2*a;y*=2;t++<r?y++,r-=t++:t--;t*=2;r*=4;r+=(o&z)>>2*a;}return y;}
Chris
fuente
¡Buen trabajo! No lo he ejecutado para probar, pero el código parece interesante. ¿Hay alguna razón por la que escribiste en (t++)lugar de solo t++en la tarea r?
Todd Lehman el
1
@ToddLehman Nope, simplemente extrañé sacarlos. ¡Buena atrapada!
Chris
Por cierto, me encanta la a--+1forma de evitar escribir a-- != UINT64_C(-1). ¿Aprendiste ese truco en alguna parte o lo inventaste tú mismo?
Todd Lehman el
1
@ToddLehman ¡Gracias! Lo descubrí yo mismo.
Chris
1

C - 50 (61 sin global)

typedef uint64_t T;T n,i;f(){while(++i*i<=n);--i;}

Utiliza variables globales como parámetro y valor de retorno para ahorrar espacio.

Sin versión global:

typedef uint64_t T;T f(T n){T i=0;while(++i*i<=n);return--i;}
mantale
fuente
1
No creo que usar variables globales sea legal. Al menos diga cuánto tiempo sería legítimamente y proporcione una versión legítima
orgulloso Haskeller
@proud haskeller ¿Por qué se prohibirían las variables globales?
mantale
@mantal porque debe proporcionar un programa / método ejecutable.
Marciano.Andrade
@ Marciano.Andrade se da el código es ejecutable.
mantale
1

C ++ 125

int main()
{
uint64_t y;cin>>y;
double x=y/2,d,z;
while((d=(x*x-y))>0.5)
{
d<0?x+=0.5:x-=0.5;
}
cout<<(uint64_t)x;
}
bacchusbeale
fuente
¡Agradable! ¿Qué tal x+=(d<0)-0.5;... salva 5 personajes más?
Todd Lehman
Por cierto, esto no es (pero debería ser) en forma de una función, como se menciona en la declaración del problema. (Bueno, técnicamente, sí, maines una función, pero no se puede llamar desde dentro de un programa como f(y)sería).
Todd Lehman
Creo que puedes omitir el par de paréntesis más interno y escribir en while((d=x*x-y)>0.5)lugar de while((d=(x*x-y))>0.5). Guarda 2 personajes más. :)
Todd Lehman
Cada 0.5 se puede cambiar a .5
Yytsi