Проблема:

Выбирая язык, напишите кратчайшую функцию, которая возвращает пол квадратного корня 64-разрядного целого числа без знака.

Тестовые случаи:

Ваша функция должна работать правильно для всех входов, но вот несколько, которые помогают проиллюстрировать идею:

               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

Правила:

1. Вы можете назвать свою функцию как угодно. (Безымянные, анонимные или лямбда-функции в порядке, если они так или иначе могут вызываться.)
2. В этом испытании важнее всего количество символов, но важно и время выполнения. Я уверен, что вы могли бы итеративно сканировать ответ в течение O (√n) времени с очень небольшим количеством символов, но время O (log (n)) было бы действительно лучше (то есть, предполагая, что входное значение n, не битовая длина п).
3. Возможно, вы захотите реализовать функцию с использованием чисто целочисленной и / или логической арифметики. Однако, если вы действительно хотите использовать вычисления с плавающей запятой, это нормально, если вы не вызываете библиотечные функции. Таким образом, просто говорить return (n>0)?(uint32_t)sqrtl(n):-1;в C запрещено, даже если это даст правильный результат. Если вы используете арифметику с плавающей точкой, вы можете использовать *, /, +, -и возведение в степень (например, **или , ^если это встроенный оператор в выбранном вами языке, но только экспоненцирование полномочий не менее 1 ). Это ограничение состоит в том, чтобы предотвратить «мошенничество» путем вызова sqrt()или варианта или повышения значения до степени ½.
4. Если вы используете операции с плавающей точкой (см. # 3), вам не требуется, чтобы возвращаемый тип был целочисленным; только то, что возвращаемое значение является целым числом, например, floor (sqrt (n)), и может содержать любое 32-разрядное значение без знака.
5. Если вы используете C / C ++, вы можете предположить существование беззнаковых 64-битных и 32-битных целочисленных типов, например, uint64_tи uint32_tкак определено в stdint.h. В противном случае просто убедитесь, что ваш целочисленный тип может содержать любое 64-разрядное целое число без знака.
6. Если ваш язык не поддерживает 64-битные целые числа (например, Brainfuck, по-видимому, поддерживает только 8-битные целые числа), приложите все усилия и укажите ограничение в заголовке вашего ответа. Тем не менее, если вы сможете понять, как кодировать 64-разрядное целое число и правильно получить квадратный корень из него, используя 8-разрядную примитивную арифметику, тогда вам больше сил!
7. Веселитесь и будьте креативны!

CJam, 17 (или 10) байт

{_1.5#\/i}

Попробуйте онлайн , проверив контрольные примеры:

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

Он не пройдет последний тестовый случай из-за проблем с округлением, но, поскольку в CJam 18446744073709551615нет Integer (это Big Integer ), мы все еще хороши, верно?

Если нет, следующий (и чуть более длинный) код исправит эти ошибки:

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

Больше не самое короткое решение, но faaast .

Как это устроено

__    " 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. ";

Хаскелл, 28 26

Я считаю, что это самая короткая запись из всех языков, не предназначенных для игры в гольф.

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

Называет функцию sс параметром aи возвращает один минус первое число, квадрат которого больше чем a. Работает невероятно медленно (O (sqrt n), может быть?).

Golfscript, 17 символов

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

Я мог назвать свою функцию так, как мне нравится, но я решил не называть ее вообще. Добавьте два символа к имени, добавьте три к имени и не оставляйте его в стеке, вычтите один символ, если полная программа в порядке.

Эта мерзость выполняется не в логарифмическом времени в значении ввода, а не в O (sqrt n) времени, для получения результата требуется колоссальное линейное количество времени. Это также занимает столько места. Абсолютно ужасно. Но ... это код-гольф.

Алгоритм:

n => [0..n].filter(x => x*x < n+1).length - 1

Pyth , 14 символов

DsbR;fgb*TTL'b

Предоставляет именованную функцию s, которая вычисляет квадратный корень путем фильтрации списка от 0 до n для квадрата, большего, чем вход, а затем печатает последнее такое число. Не использует возведения в степень или плавает.

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

Пример использования:

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]

Сетчатка (не конкурирующая - язык новее, чем вызов), 43

Работая над этим ответом , мне пришло в голову, что аналогичный метод может быть использован для вычисления целых квадратных корней с помощью сетчатки:

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

1+

Это основывается на том факте, что совершенные квадраты могут быть выражены как 1+3+5+7+...и, как следствие, число членов в этом выражении является квадратным корнем.

Попробуйте онлайн. (Добавлена ​​первая строка, позволяющая запускать несколько тестовых случаев.)

Очевидно, что из-за десятичного преобразования в унарное это будет работать только для относительно небольших входных данных.

Perl, 133 символа

Не самый короткий, но использует алгоритм «цифра за цифрой» для обработки ввода любого размера и выполняется за время O (log n). Свободно преобразует между числами, как строки и числа, как числа. Поскольку наибольший возможный продукт на сегодняшний день - это корень с квадратом одной цифры, он должен иметь возможность получить квадратный корень из примерно 120-битных или около того чисел в 64-битной системе.

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}

Распакованный, то есть:

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;
}

Матлаб (56) / Октава (55)

Он работает с квадратным корнем, используя метод с фиксированной точкой. Он сходится максимум за 36 шагов (для аргумента 2 ^ 64-1) и затем проверяет, является ли он нижним из «возможных» целочисленных корней. Поскольку он всегда использует 36 итераций, он имеет время выполнения O (1) = P

Предполагается, что аргумент будет 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

Октав:

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

Рубин - 36 символов

s=->n{g=n;g=(g+n/g)/2 while g*g>n;g}

Python (39)

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

Естественный рекурсивный подход. Подсчитывает потенциальные квадратные корни, пока их квадрат не станет слишком высоким, а затем уменьшится на 1. Используйте Stackless Python, если вы беспокоитесь о превышении глубины стека.

and/orИдиомы эквивалентно тройном оператора как

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

Edit: я могу вместо этого получить 25 символов путем использования правила «вы можете использовать *, /, +, -, и возведение в степень (например, **или , ^если это встроенный оператор в выбранном вами языке, но только экспоненцирование полномочий не менее 1). " (Правка: видимо, Денис уже нашел и использовал этот трюк.)

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

Я использую оператор целочисленного деления //Python 3 для округления вниз. К сожалению, я трачу много символов на случай, n=0чтобы не дать ошибку деления на 0. Если бы не это, я мог бы сделать 18 символов

lambda n:n**1.5//n 

В правилах также не говорилось, что функция должна быть названа (в зависимости от того, как вы интерпретируете «Вы можете назвать свою функцию как угодно»), но если это так, это еще два символа.

C99 (58 знаков)

Это пример ответа, который я бы не посчитал хорошим, хотя он интересен мне с точки зрения гольф-кода, потому что он настолько извращен, и я просто подумал, что было бы интересно добавить в него микс:

Оригинал: 64 символа

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

Причина, по которой этот код ужасен, заключается в том, что он выполняется за время O (√n), а не за O (log (n)). (Где n - входное значение.)

Редактировать: 63 персонажа

Изменение r-1к --rи примыкающий его return:

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

Редактировать: 62 персонажа

Перемещение приращения цикла внутрь условной части цикла (примечание: это имеет негарантированное поведение, поскольку порядок операций относительно оператора preincrement зависит от компилятора):

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

Изменить: 60 символов

Добавление, typedefчтобы скрыть uint64_t(кредит пользователю technosaurus за это предложение).

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

Изменить: 58 символов

Теперь требуется, чтобы второй параметр передавался как 0 при вызове функции, например, r(n,0)вместо just r(n). Хорошо, на данный момент я не могу понять, как это сжимать дальше ... кого-нибудь?

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

Гольфскрипт - 14 символов

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

Найти наименьшее число iменьше, чем вход nдля которого n < i*i. Возвращение i - 1.

Т.е. [0..n-1].first(i => n < i*i) - 1

Объяснение для тех, кто также не знает Golfscript, для примера вызова с вводом 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 

Haskell, 147 138 134 128 байт

Не самый короткий код в мире, но он работает на O (log n) и на числах произвольного размера:

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)

Это выполняет бинарный поиск диапазона [0..n], чтобы найти наилучшее нижнее приближение к sqrt (n). Вот негольфированная версия:

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

Редактировать: Сохранение двух байтов путем замены предложений «иначе» на «0 <1» в качестве более короткой версии «True» и еще нескольких путем вставки g * g.

Кроме того, если вы довольны O (sqrt (n)), вы можете просто сделать

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

для 35 символов, но что это весело?

Редактировать 2: Я только что понял, что, поскольку пары сортируются по порядку словаря, вместо того, чтобы делать min2Cycle. Карта FST, я могу просто сделать FST. min2Cycle. В загаданном коде это означает замену f $ map fst на fst $ f, экономя еще 4 байта.

Редактировать 3: Сохранено еще шесть байтов благодаря гордому хакеллеру!

JavaScript 91 88 86: оптимизирован для скорости

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: не оптимизирован для скорости

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

Вот JSFiddle: http://jsfiddle.net/rmadhuram/1Lnjuo4k/

С 95 97

Редактировать Typedef, предложенный @Michaelangelo

Это должно быть более или менее простой реализацией алгоритма Герона. Единственная изюминка - вычисление среднего значения во избежание переполнения целых чисел: a = (m + n) / 2 не работает для двухзначных чисел.

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;
}

C # 64 62 55

Так как это код-гольф (а я плохо разбираюсь в математике), а время выполнения - всего лишь совет, я сделал наивный подход, который работает в линейном времени:

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

( тест на dotnetfiddle )

Конечно, это ужасно медленно для больших входов.

Clojure - 51 или 55 байтов

Проверяет все числа от n до 0, давая первое где x^2 <= n. Время выполненияO(n - sqrt n)

Без имени:

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

Названный:

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

Пример:

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

Befunge 93 - 48 байт или 38 символов

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

Попробуйте это здесь.

Кобра - 62

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

Партия - 74

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

Haskell, 53 50 49 символов, O (log n)

s n=until((<=n).(^2))(\g->g-1-div(g^2-n-1)(2*g))n

Это решение реализует метод Ньютона-Рафсона, хотя он ищет целые числа, а не числа с плавающей точкой. вики: http://en.wikipedia.org/wiki/Newton%27s_method

сложность, кажется, о O (log n), но есть ли доказательства этого? Пожалуйста, ответьте в комментариях.

J (10)

Очень, очень, очень вдохновленный ответом @Dennis :

<.@%~^&1.5

И немного дольше, но с лучшей производительностью (я подозреваю):

<.@(-:&.^.)

floor(halve under log)

Для выполнения вводятся отступные части:

   f=:<.@%~^&1.5
   f 0 8 12 16
0 2 3 4
   g=:<.@(-:&.^.)
   g 0 8 12 16
0 2 3 4

APL - 12 символов, 19 байтов

{⌊(⍵*1.5)÷⍵}

пример использования:

{⌊(⍵*1.5)÷⍵}17

возвращает 4

Тестовый вектор

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

возвращается

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

Попробуйте онлайн

Большое спасибо : пользователь "ssdecontrol" за алгоритм

C99 (108 символов)

Вот мое собственное решение в C99, которое адаптировано из алгоритма в статье в Википедии . Я уверен, что это может быть возможно сделать намного лучше, чем это на других языках.

Golfed:

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;}

Частично гольф

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;
}

Ungolfed:

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;
}

JavaScript 73 81 (для соответствия требованиям 64-битных чисел)

n=prompt();g=n/3;do{G=g,g=(n/g+g)/2}while(1E-9<Math.abs(G-g))alert(Math.floor(g))

Реализация алгоритма Герона Александрийского ...

Powershell (52), ограниченный Int32 (от -2 147 483 648 до 2 147 483 647)

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

Я сейчас кричу о Powershell, пытаясь заставить работать последний тестовый пример, но независимо от того, что я делаю, Powershell использует переменную конвейера $ _ в качестве Int32, и сейчас я не могу найти способ обойти это.

Так что я пока ограничу свой ответ. Если я найду лучший способ обработки uint64s, я буду редактировать. (Кстати, последний тестовый пример слишком велик для обычного типа Powershell Int64!)

Вот несколько тестовых случаев (с дополнительным выводом, который я использовал для отслеживания времени)

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

Я не знаю своих O (), но это кажется довольно драматичным скачком.

Предостережение: с 2011 года R не имел встроенной поддержки 64-битных целых чисел, как я предполагал. Эти ответы могут быть недействительными по этой технической причине, но опять же R сильно изменился за последние 3 года.

R 85

Используя метод Ньютона:

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

который сходится квадратично. +2 символа для назначения функции переменной для бенчмаркинга:

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

Р, 37

Грубая сила:

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

И тот же чек:

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

Р, 30

Дешево / блестящий экспоненцирование трюк :

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

что также происходит очень быстро (хотя и не так быстро, как встроенный):

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

С, 38

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

Перевод моего четвертого представления. Медленно, но верно. O (√n). Протестировано на OS X (64 бит).

постоянный ток, 50 байтов

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

Разместил и объяснил:

               # 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

C 139 137 136 байт

Моя первая попытка в коде гольф. Похоже, что это самый короткий C, который соответствует «эффективному» требованию, поскольку он выполняется во O(log n)времени, используя только сложение и сдвиги битов. Хотя я уверен, что это может быть еще короче ...

Он должен прекрасно работать и для больших целочисленных значений, пока a=32деталь изменяется на 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;}

C - 50 (61 без глобального)

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

Он использует глобальные переменные в качестве параметра и возвращаемого значения для экономии места.

Нет глобальной версии:

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

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;
}