12
\$\begingroup\$

Problem:

In your choice of language, write the shortest function that returns the floor of the square root of an unsigned 64-bit integer.

Test cases:

Your function must work correctly for all inputs, but here are a few which help illustrate the 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

Rules:

  1. You can name your function anything you like. (Unnamed, anonymous, or lambda functions are fine, as long as they are somehow callable.)
  2. Character count is what matters most in this challenge, but runtime is also important. I'm sure you could scan upwards iteratively for the answer in O(√n) time with a very small character count, but O(log(n)) time would really be better (that is, assuming an input value of n, not a bit-length of n).
  3. You will probably want to implement the function using purely integer and/or boolean artithmetic. However, if you really want to use floating-point calculations, then that is fine so long as you call no library functions. So, simply saying return (n>0)?(uint32_t)sqrtl(n):-1; in C is off limits even though it would produce the correct result. If you're using floating-point arithmetic, you may use *, /, +, -, and exponentiation (e.g., ** or ^ if it's a built-in operator in your language of choice, but only exponentiation of powers not less than 1). This restriction is to prevent "cheating" by calling sqrt() or a variant or raising a value to the ½ power.
  4. If you're using floating-point operations (see #3), you aren't required that the return type be integer; only that that the return value is an integer, e.g., floor(sqrt(n)), and be able to hold any unsigned 32-bit value.
  5. If you're using C/C++, you may assume the existence of unsigned 64-bit and 32-bit integer types, e.g., uint64_t and uint32_t as defined in stdint.h. Otherwise, just make sure your integer type is capable of holding any 64-bit unsigned integer.
  6. If your langauge does not support 64-bit integers (for example, Brainfuck apparently only has 8-bit integer support), then do your best with that and state the limitation in your answer title. That said, if you can figure out how to encode a 64-bit integer and correctly obtain the square root of it using 8-bit primitive arithmetic, then more power to you!
  7. Have fun and get creative!
\$\endgroup\$

closed as unclear what you're asking by Wheat Wizard, Laikoni, user202729, Asone Tuhid, Mego Jul 16 '18 at 4:14

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 7
    \$\begingroup\$ "but O(log₄(n)) time would really be better." - how much better? Is there a bonus? Is that a hard requirement? Is it essentially a separate challenge? Is that just a nice idea that doesn't really affect the scoring? \$\endgroup\$ – John Dvorak Jul 26 '14 at 20:34
  • 3
    \$\begingroup\$ Normally one uses the size of the input rather than the input value to derive algorithmic complexity. In that sense the increment-and-retry algorithm is exponential in speed. \$\endgroup\$ – John Dvorak Jul 26 '14 at 20:50
  • 3
    \$\begingroup\$ Umm... O(log_2 n) === O(log_4 n). log_4(n) = log_2(n) / log_2(2) = log_2(n) / 2 \$\endgroup\$ – John Dvorak Jul 26 '14 at 20:50
  • 1
    \$\begingroup\$ Does 2/4 count? \$\endgroup\$ – Milo Jul 27 '14 at 1:02
  • 1
    \$\begingroup\$ Most floating-point data types don't have the precision needed for this task anyway. 53 significant bits isn't enough for the whole input range. \$\endgroup\$ – user2357112 supports Monica Jul 27 '14 at 2:32

40 Answers 40

14
\$\begingroup\$

CJam, 17 (or 10) bytes

{_1.5#\/i}

Try it online by verifying the test cases:

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

It won't pass the last test case because of rounding issues, but since 18446744073709551615 isn't an Integer in CJam (it's a Big Integer), we're still good, right?

If not, the following (and slightly longer) code will correct those errors:

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

Not the shortest solution anymore, but faaast.

How it works

__    " 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. ";
\$\endgroup\$
  • \$\begingroup\$ Hahaha! oops, ok, you got me on a technicality there. I should have said no fractional powers. But your code does indeed obey the stated rules, so I'm upvoting it. :) \$\endgroup\$ – Todd Lehman Jul 27 '14 at 0:30
  • 2
    \$\begingroup\$ Does CJam have arbitrary-precision decimals, to cover the whole input range? \$\endgroup\$ – isaacg Jul 27 '14 at 3:16
  • \$\begingroup\$ Also, nice hack of using NaN -> 0 on cast to int. \$\endgroup\$ – isaacg Jul 27 '14 at 3:28
  • \$\begingroup\$ Neat idea, it can also be represented in J in the exact same character count: <.@%~^&1.5. Can I post this as an separate answer (since it's basically an exact port of yours)? \$\endgroup\$ – ɐɔıʇǝɥʇuʎs Sep 1 '14 at 19:49
  • \$\begingroup\$ @ɐɔıʇǝɥʇuʎs: Go ahead. But I just figured out that my solution may round incorrectly for big numbers, including the last test case. In my defense, it passed my inspection only because 4294967295 and 4294967296 look very similar... \$\endgroup\$ – Dennis Sep 1 '14 at 20:10
10
\$\begingroup\$

Haskell, 28 26

I believe that this is the shortest entry from any language that wasn't designed for golfing.

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

It names a function s with parameter a and returns one minus the first number whose square is greater than a. Runs incredibly slowly (O(sqrt n), maybe?).

\$\endgroup\$
  • 1
    \$\begingroup\$ Wouldn't a list index ([...]!!0) be shorter than head? \$\endgroup\$ – isaacg Jul 28 '14 at 6:39
  • \$\begingroup\$ @isaacg Yes, it would. Thanks :-) \$\endgroup\$ – Zaq Jul 28 '14 at 15:35
7
\$\begingroup\$

Golfscript, 17 characters

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

I could name my function any way I liked, but I decided not to name it at all. Add two characters to name it, add three to name it and not leave it on the stack, subtract one character if providing a full program is OK.

This abomination runs not in logaritmic time in the value of the input, not in O(sqrt n) time, it takes a whooping linear amount of time to produce the result. It also takes that much space. Absolutely horrendous. But... this is code-golf.

The algorithm is:

n => [0..n].filter(x => x*x < n+1).length - 1
\$\endgroup\$
  • \$\begingroup\$ I love it!! Nice work! That is beautifully perverse. \$\endgroup\$ – Todd Lehman Jul 26 '14 at 21:10
7
\$\begingroup\$

Pyth, 14 characters

DsbR;fgb*TTL'b

Provides a named function, s, which calculates the square root by filtering the list from 0 to n for the square being larger than the input, then prints the last such number. Uses no exponentiation or floats.

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

Example usage:

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]
\$\endgroup\$
7
\$\begingroup\$

Retina (non-competing - Language is newer than the challenge), 43

While working on this answer, it occurred to me that a similar method can be used to calculate integer square roots using retina:

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

1+

This relies on the fact that perfect squares may be expressed as 1+3+5+7+..., and by corollary that the number of terms in this expression is the square root.

Try it online. (First line added to allow multiple testcases to be run.)

Obviously due to the decimal to unary conversion, this will only work for relatively small inputs.

\$\endgroup\$
  • 4
    \$\begingroup\$ (Language is newer than the challenge) \$\endgroup\$ – mbomb007 Jun 13 '16 at 21:44
  • \$\begingroup\$ @mbomb007 Fair enough - Headline edited. This answer is definitely in the "because it can be done" category, and not meant to compete in the challenge in any meaningful way. \$\endgroup\$ – Digital Trauma Jun 13 '16 at 21:50
  • 1
    \$\begingroup\$ I know what you mean. \$\endgroup\$ – mbomb007 Jun 14 '16 at 16:17
6
\$\begingroup\$

Perl, 133 characters

Not the shortest by far, but uses a digit-by-digit algorithm to handle any size input, and runs in O(log n) time. Converts freely between numbers-as-strings and numbers-as-numbers. Since the largest possible product is the root-so-far with the square of a single digit, it should be able to take the square root of up to 120-bit or so numbers on a 64-bit system.

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}

Decompressed, that is:

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;
}
\$\endgroup\$
  • \$\begingroup\$ Nice! I was wondering when someone would post a Perl answer. BTW, does it work to say if length%2 instead of if(length)%2? That would shave off 1 character. Also, would it work to say $y=$z,$d=$_ if instead of ($y,$d)=($z,$_)if? I think that would shave off 3 more characters. \$\endgroup\$ – Todd Lehman Jul 27 '14 at 22:45
  • \$\begingroup\$ And this is getting a bit perverse, but I think you can shave off 1 more yet by rewriting the for loop as: $a<($z=$_*(20*$r+$_))or$y=$z,$d=$_ for(1..9); \$\endgroup\$ – Todd Lehman Jul 27 '14 at 23:02
  • \$\begingroup\$ The first suggestion doesn't work (it tries to take the length of a hash named %2), but the others are valid. I'll work them in. \$\endgroup\$ – hobbs Jul 28 '14 at 1:26
  • 1
    \$\begingroup\$ @ToddLehman postfix for doesn't need parentheses; adding that to your suggestions nets me 6 characters total. Thanks! \$\endgroup\$ – hobbs Jul 28 '14 at 1:32
5
\$\begingroup\$

Matlab (56) / Octave (55)

It works out the square root by using a fixed point method. It converges in maximal 36 steps (for 2^64-1 as argument) and then checks if it is the lower one of the 'possible' integer roots. As it always uses 36 iterations it has a runtime of O(1) =P

The argument is assumed to be 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

Octave:

function x=q(s)
x=1
for i = 1:36
    x = (x+s/x)/2
end
if x*x>s
    x-=1
end
\$\endgroup\$
  • \$\begingroup\$ This is a new method to me, and it happens to be pretty cool. +1 \$\endgroup\$ – seequ Jul 28 '14 at 7:34
  • 1
    \$\begingroup\$ It is basically the en.wikipedia.org/wiki/… which is one of the earliest known numerical methods that is estimated to be around 3700 years old. It can be justified by the en.wikipedia.org/wiki/Banach_fixed-point_theorem which has a surprisingly easy proof, it's really nice=) \$\endgroup\$ – flawr Jul 28 '14 at 11:13
5
\$\begingroup\$

Ruby — 36 characters

s=->n{g=n;g=(g+n/g)/2 while g*g>n;g}
\$\endgroup\$
  • \$\begingroup\$ Nicely done! What is the worst-case execution time? \$\endgroup\$ – Todd Lehman Jul 29 '14 at 19:06
  • \$\begingroup\$ What about in the event that g*g < n and the answer is still not close to the value desired? Won't the script just stop? \$\endgroup\$ – WallyWest Jul 30 '14 at 6:49
  • 1
    \$\begingroup\$ @ToddLehman I honestly don't know. :-/ This is the Babylonian method. Here's what appears to be a good proof of the average complexity. The initial guess of the number itself is pretty bad, but I'd need to sit down and really grok that proof to understand the worst case. Will give it a go when I have some more free time. :-) \$\endgroup\$ – O-I Aug 2 '14 at 22:53
  • \$\begingroup\$ @WallyWest My understanding is that the while loop terminates precisely when g converges to floor(√n) which is the desired value. Do you see any case where this would not be true? \$\endgroup\$ – O-I Aug 2 '14 at 23:24
4
\$\begingroup\$

Python (39)

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

The natural recursive approach. Counts up potential square roots until their square is too high, then goes down by 1. Use Stackless Python if you're worried about exceeding the stack depth.

The and/or idiom is equivalent to the ternary operator as

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

Edit: I can instead get 25 chars by exploiting the rule "you may use *, /, +, -, and exponentiation (e.g., ** or ^ if it's a built-in operator in your language of choice, but only exponentiation of powers not less than 1)." (Edit: Apparently Dennis already found and exploited this trick.)

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

I use the integer division operator // of Python 3 to round down. Unfortunately, I spend a lot of characters for the case n=0 not to give a division by 0 error. If not for it, I could do 18 chars

lambda n:n**1.5//n 

The rules also didn't say the function had to be named (depending how you interpret "You can name your function anything you like."), but if it does, that's two more characters.

\$\endgroup\$
  • \$\begingroup\$ — Thanks, I'll clarify that. It only has to be a function. It doesn't have to be named. So, lambda functions are fine. I would have mentioned this from the start if I'd thought of it. I was thinking too much in terms of C when I posted the question. \$\endgroup\$ – Todd Lehman Jul 27 '14 at 4:33
4
\$\begingroup\$

C99 (58 characters)

This is an example of an answer I would not consider to be a good one, although it's interesting to me from a code golf point of view because it's so perverse, and I just thought it would be fun to throw into the mix:

Original: 64 characters

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

The reason this one is terrible is that it runs in O(√n) time rather than O(log(n)) time. (Where n is the input value.)

Edit: 63 characters

Changing the r-1 to --r and abutting it to return:

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

Edit: 62 characters

Moving the loop increment to inside the conditional portion of the loop (note: this has unguaranteed behavior because the order of operations with respect to the preincrement operator is compiler-specific):

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

Edit: 60 characters

Adding a typedef to hide uint64_t (credit to user technosaurus for this suggestion).

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

Edit: 58 characters

Now requiring second parameter being passed as 0 in invocation of the function, e.g., r(n,0) instead of just r(n). Ok, for the life of me, at this point I can't see how to compress this any further...anyone?

typedef uint64_t Z;Z r(Z n,Z r){for(;n/++r/r;);return--r;}
\$\endgroup\$
  • \$\begingroup\$ If you are willing to call it C++ and decrement rather than increment you would be able to shave off a couple of characters: uint64_t s(uint64_t n){for(uint64_t r=n;--n>r/n;);return n;}. \$\endgroup\$ – Fors Jul 27 '14 at 0:29
  • \$\begingroup\$ @Fors — Nice approach! Unfortunately, won't that cause a divide-by-zero for input of 1? Also, what will it do for an input of 0? Because --n when n==0 would be –1, and these are unsigned values, so –1 would be 2⁶⁴–1. \$\endgroup\$ – Todd Lehman Jul 27 '14 at 0:45
  • 1
    \$\begingroup\$ #define Z uint64_t ... or typedef will save a couple \$\endgroup\$ – technosaurus Jul 28 '14 at 6:08
  • \$\begingroup\$ @technosaurus — Ah yes, that saves 2. Thank you. :-) \$\endgroup\$ – Todd Lehman Jul 28 '14 at 6:33
  • 1
    \$\begingroup\$ The expression n/++r/r has undefined behavior.... \$\endgroup\$ – aschepler Jul 29 '14 at 21:45
4
\$\begingroup\$

Golfscript - 14 character

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

Find the smallest number i less than the input n for which n < i*i. Return i - 1.

I.e. [0..n-1].first(i => n < i*i) - 1

Explanation for those who don't know Golfscript as well, for sample call with input 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 
\$\endgroup\$
  • \$\begingroup\$ Ooh, that's 3 characters shorter than the previous best Golfscript answer. Nice work! \$\endgroup\$ – Todd Lehman Jul 30 '14 at 1:30
  • \$\begingroup\$ Fixing this to give the correct answer for input 1 probably takes two chars. \$\endgroup\$ – Peter Taylor Sep 3 '14 at 13:57
4
\$\begingroup\$

Haskell, 147 138 134 128 bytes

Not the shortest code in the world, but it does run in O(log n), and on arbitrary-sized numbers:

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)

This does a binary search of the range [0..n] to find the best lower approximation to sqrt(n). Here is an ungolfed version:

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

Edit: Saved two bytes by replacing the "otherwise" clauses with "0<1" as a shorter version of "True", and a few more by inlining g*g.

Also, if you are happy with O(sqrt(n)) you could simply do

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

for 35 characters, but what fun is that?

Edit 2: I just realized that since pairs are sorted by dictionary order, instead of doing min2Cycle . map fst, I can just do fst . min2Cycle. In the golfed code, that translates to replacing f$map fst with fst$f, saving 4 more bytes.

Edit 3: Saved six more bytes thanks to proudhaskeller!

\$\endgroup\$
  • 1
    \$\begingroup\$ you can replace (div x 2 + rem x 2) with div(x+1)2, at your "half" function \$\endgroup\$ – proud haskeller Jul 30 '14 at 4:31
  • \$\begingroup\$ I actually have a solution of my own which has 49 characters, and solves in O(log n), but i only have 2 upvotes ;-(. I don't understand why \$\endgroup\$ – proud haskeller Jul 31 '14 at 6:08
4
\$\begingroup\$

JavaScript 91 88 86: Optimized for speed

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: Non optimized for speed

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

Here is a JSFiddle: http://jsfiddle.net/rmadhuram/1Lnjuo4k/

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! You can use <s>91</s> <s>88</s> for strikethrough. I tried making the edit but you were editing at the same time so I'll let you do it. \$\endgroup\$ – Rainbolt Aug 8 '14 at 18:02
  • 1
    \$\begingroup\$ Or you could do it in 41 characters like this: function s(n){for(a=1;++a*a<n;);return a} \$\endgroup\$ – Rhubarb Custard Sep 1 '14 at 21:24
4
\$\begingroup\$

C 95 97

Edit Typedef, suggested by @Michaelangelo

This should be more or less a straightforward implementation of Heron algorithm. The only quirk is in computing the average avoiding integer overflow: a=(m+n)/2 does not work for biiiig numbers.

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;
}
\$\endgroup\$
  • \$\begingroup\$ Nice work with the overflow avoidance —— not only for correctly doing it, but taking care to think about it in the first place and test it. Definitely appreciated. \$\endgroup\$ – Todd Lehman Jul 27 '14 at 19:25
  • \$\begingroup\$ BTW, it's funny how expensive division can be on some CPUs. Even though this algorithm executes in roughly half as many steps as the abacus algorithm, it has a runtime that's about 5 times slower than the abacus algorithm when I benchmark it on my Core i7 CPU, which doesn't like doing division. Anyway, but runtime isn't important here — only size. :) So nice work!!! \$\endgroup\$ – Todd Lehman Jul 27 '14 at 19:29
4
\$\begingroup\$

C# 64 62 55

Since this is a (and I'm terrible with maths), and runtime is merely a suggestion, I've done the naive approach that runs in linear time:

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

(test on dotnetfiddle)

Of course, it's terribly slow for larger inputs.

\$\endgroup\$
  • 1
    \$\begingroup\$ You might be able to shave off a character by changing return i-1 to return--i? \$\endgroup\$ – Todd Lehman Jul 27 '14 at 18:39
  • \$\begingroup\$ In the expression i*i<=a, is that guaranteed to be integer arithmetic of the usual type? (I'm not familiar with C#.) If so, and if C# allows implicit integer conversion to boolean like C does, then you might be able to save one more character by changing that to a/i/i. \$\endgroup\$ – Todd Lehman Jul 27 '14 at 18:41
  • 1
    \$\begingroup\$ @ToddLehman That actually happens to be fixed-point arithmetic (Decimal, higher max value and precision), to avoid the overflow since the multiplication result could potentially go one step past UInt64.MaxValue. But C# doesn't have implicit conversions to Boolean anyway. I should be able to change the return though, thanks. I'll do it when I get back to a computer. \$\endgroup\$ – Bob Jul 27 '14 at 22:47
3
\$\begingroup\$

Clojure - 51 or 55 bytes

Checks all numbers from n to 0, giving the first one where x^2 <= n. Runtime is O(n - sqrt n)

Unnamed:

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

Named:

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

Example:

(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)
\$\endgroup\$
3
\$\begingroup\$

Befunge 93 - 48 Bytes or 38 Characters

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

Try it over here.

\$\endgroup\$
  • 1
    \$\begingroup\$ Ok, that is just cool. Nice work! I entered 17, clicked Creep and then Run, and it came up with 4! :) \$\endgroup\$ – Todd Lehman Jul 27 '14 at 0:29
3
\$\begingroup\$

Cobra - 62

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

Batch - 74

set a=0
:1
set /ab=%a%*%a%
if %b% LSS %1 set /aa=%a%+1&goto 1
echo %a%
\$\endgroup\$
3
\$\begingroup\$

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

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

this solution implements the newton-raphson method, although it searches integers instead of floats. wiki: http://en.wikipedia.org/wiki/Newton%27s_method

the complexity seems to be about O(log n), but is there a proof of it? please answer in the comments.

\$\endgroup\$
  • \$\begingroup\$ \g->div(n+g^2)$2*g saves 7 bytes. \$\endgroup\$ – Anders Kaseorg Jul 10 '17 at 21:41
3
\$\begingroup\$

J (10)

Very, very, very inspired by the answer of @Dennis:

<.@%~^&1.5

And a slightly longer, but with better performance (I suspect):

<.@(-:&.^.)

floor(halve under log)

To execute, indented parts are input:

   f=:<.@%~^&1.5
   f 0 8 12 16
0 2 3 4
   g=:<.@(-:&.^.)
   g 0 8 12 16
0 2 3 4
\$\endgroup\$
  • \$\begingroup\$ How do you execute this for a given integer? \$\endgroup\$ – Dennis Sep 1 '14 at 20:23
  • 1
    \$\begingroup\$ @Dennis See answer \$\endgroup\$ – ɐɔıʇǝɥʇuʎs Sep 1 '14 at 20:26
3
\$\begingroup\$

APL - 12 chars, 19 bytes

{⌊(⍵*1.5)÷⍵}

example use:

{⌊(⍵*1.5)÷⍵}17

returns 4

Test vector

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

returns

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

Try Online

Big thanks to: user "ssdecontrol" for algorithm

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! We normally score APL as one byte per character. Unless the challenge specifies it, there is no need to count in UTF-8. Any existing encoding is fine, and there is an old APL codepage from back in the day which uses a single byte for each character. The fact that APL predates ASCII is a bad reason to penalise it for using non-ASCII characters. ;) (That said, this rather old challenge seems to score by characters anyway.) \$\endgroup\$ – Martin Ender Jun 13 '16 at 22:08
  • \$\begingroup\$ @MartinEnder Thanks for the warm welcome and tips :) \$\endgroup\$ – QuantumKarl Jun 14 '16 at 12:27
  • 1
    \$\begingroup\$ 01! Using Dyalog APL, you can set ⎕DIV←1 (which many use as default) to obtain the correct result. \$\endgroup\$ – Adám Jun 16 '16 at 10:59
2
\$\begingroup\$

C99 (108 characters)

Here is my own solution in C99, which is adapted from an algorithm in an article on Wikipedia. I'm sure it must be possible to do much better than this in other languages.

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

Partially golfed:

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Suggestion: No need for a, use n. \$\endgroup\$ – edc65 Jul 27 '14 at 8:28
  • \$\begingroup\$ Ah yes. Thank you. In my original version, I was maintaining n so that just before returning I could make the assertion (not shown) that r^2 <= n < (r+1)^2. With that assertion omitted, it's longer necessary to keep n intact. \$\endgroup\$ – Todd Lehman Jul 27 '14 at 10:50
  • \$\begingroup\$ @edc65 — Thanks again for pointing that out. I updated my code to reflect that, as well as added a couple other golf tricks. Also added the original assertions and made n const in the ungolfed version. \$\endgroup\$ – Todd Lehman Jul 27 '14 at 18:21
2
\$\begingroup\$

JavaScript 73 81 (to comply with 64-bit numbers requirement)

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

Implementing Heron of Alexandria's algorithm...

\$\endgroup\$
  • \$\begingroup\$ Nice! Does this work for all unsigned 64-bit integer inputs? \$\endgroup\$ – Todd Lehman Jul 29 '14 at 4:55
  • \$\begingroup\$ Try as I might this only seems to work up to 32-bit... Much to my disappointment... \$\endgroup\$ – WallyWest Jul 29 '14 at 6:32
  • \$\begingroup\$ Surely the last |0 truncates any value to 32 bit. Using Math.floor instead? \$\endgroup\$ – edc65 Jul 29 '14 at 18:54
  • \$\begingroup\$ @edc65 You're right actually, seems |0 affects up to 32-bit whereas Math.floor is more effective at 64-bit... I've updated my code, having to take an extra 8 characters in order to do so... \$\endgroup\$ – WallyWest Jul 29 '14 at 23:27
  • \$\begingroup\$ @edc65 I've just had a thought... would ~~x work in 64-bit? \$\endgroup\$ – WallyWest Dec 4 '14 at 22:52
2
\$\begingroup\$

Powershell (52) Limited to Int32 (-2,147,483,648 to 2,147,483,647)

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

I'm screaming at Powershell right now trying to make the last test case work but no matter what I do Powershell winds up using the pipeline variable $_ as an Int32, and I can't find a way around it right now.

So I'll just limit my answer for now. If I can find a better way to handle uint64s I will edit. (The last test case is too big for Powershell's normal Int64 type, by the way!)

Here are a few test cases (with a bit of extra output I used to track the time)

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

I don't know my O()s, but this seems like a pretty dramatic jump.

\$\endgroup\$
2
\$\begingroup\$

Caveat: as of 2011, R had no built-in support for 64 bit integers as I had assumed it did. These answers might be invalid on that technicality, but then again R has changed a lot in the last 3 years.


R, 85

Using Newton's method:

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

which converges quadratically. +2 characters to assign the function to a variable for benchmarking:

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

Brute force:

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

And the same check:

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

The cheap/brilliant exponentiation trick:

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

which also happens to be very fast (although not as fast as the built-in):

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
\$\endgroup\$
2
\$\begingroup\$

C, 38

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

Translation of my Forth submission. Slow but correct. O(√n). Tested on OS X (64 bit).

\$\endgroup\$
2
\$\begingroup\$

dc, 50 bytes

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

Spaced out and explained:

               # 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
\$\endgroup\$
  • \$\begingroup\$ Uh, looks like the last test case crashes. I'll try to fix it. \$\endgroup\$ – Joe Jun 30 '16 at 22:41
  • \$\begingroup\$ Resolved. Now accepts very large input; serendipitously, the fix allowed me to remove some ugly code at the beginning. \$\endgroup\$ – Joe Jun 30 '16 at 23:47
2
\$\begingroup\$

C, 139 137 136 bytes

My first try at code golf. It looks like it's the shortest in C that fits the "efficient" requirement, as it runs in O(log n) time, using only addition and bit shifts. Though I'm sure it could be shorter yet...

It should work just fine for larger integer values too as long as the a=32 part is changed to 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;}
\$\endgroup\$
  • \$\begingroup\$ Nice work! I haven't run it to test, but the code looks interesting. Is there a reason you wrote (t++) instead of just t++ in the assignment to r? \$\endgroup\$ – Todd Lehman Aug 23 '16 at 23:08
  • 1
    \$\begingroup\$ @ToddLehman Nope, just missed taking those out. Nice catch! \$\endgroup\$ – Chris Aug 23 '16 at 23:16
  • \$\begingroup\$ BTW, I love the a--+1 as a way to avoid writing a-- != UINT64_C(-1). Did you learn that trick somewhere or invent it yourself? \$\endgroup\$ – Todd Lehman Aug 23 '16 at 23:31
  • 1
    \$\begingroup\$ @ToddLehman Thanks! I figured that out myself. \$\endgroup\$ – Chris Aug 24 '16 at 7:20
1
\$\begingroup\$

C - 50 (61 without global)

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

It use global variables as parameter and return value to save space.

No global version :

typedef uint64_t T;T f(T n){T i=0;while(++i*i<=n);return--i;}
\$\endgroup\$
  • 1
    \$\begingroup\$ I don't think using global variables is legal. At least tell how long it would be legitimately and provide a legitimate version \$\endgroup\$ – proud haskeller Jul 30 '14 at 14:29
  • \$\begingroup\$ @proud haskeller Why would global variables be forbidden ? \$\endgroup\$ – mantale Jul 30 '14 at 14:43
  • \$\begingroup\$ @mantal because you must provide a runnable program/method. \$\endgroup\$ – Marciano.Andrade Sep 3 '14 at 16:25
  • \$\begingroup\$ @Marciano.Andrade the code is gave is runnable. \$\endgroup\$ – mantale Sep 4 '14 at 8:43
1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Nice! How about x+=(d<0)-0.5; ... saves 5 more characters? \$\endgroup\$ – Todd Lehman Jul 30 '14 at 19:34
  • \$\begingroup\$ BTW, this isn't (but should be) in the form of a function, as mentioned in the problem statement. (Okay, technically, yeah, main is a function, but it's not callable from inside a program like an f(y) would be.) \$\endgroup\$ – Todd Lehman Jul 30 '14 at 19:39
  • \$\begingroup\$ I think you can omit the innermost pair of parentheses and write while((d=x*x-y)>0.5) instead of while((d=(x*x-y))>0.5). Saves 2 more characters. :) \$\endgroup\$ – Todd Lehman Jul 30 '14 at 19:39
  • \$\begingroup\$ Every 0.5 can be changed to .5 \$\endgroup\$ – Yytsi Jun 20 '16 at 10:07

Not the answer you're looking for? Browse other questions tagged or ask your own question.