Integer square root of integer [closed]

Question

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!

Answer 1

Forth, 43

: f -1 begin 1+ 2dup dup * - 0< until 1- ;

O(√n)

Answer 2

GolfScript (15 chars)

Pick any one of

{):x,{.*x<},,(}
{:x,{).*x>!},,}
{.,\{1$)/<}+,,}
{,.,{1$)/<}+,,}

I've followed the other GolfScript answers in interpreting "You can name your function anything you like" as meaning "You may leave a block which does the job on the stack". These are currently the shortest GolfScript answers which correctly handle inputs 0 and 1.

Online demo

Answer 3

JavaScript (ES6) 61 bytes

n=>n&&eval('g=n;while(Math.abs(g-(g=(n/g+g)/2))>1e-9);g-g%1')

Tests:

f=n=>n&&eval('g=n;while(Math.abs(g-(g=(n/g+g)/2))>1e-9);g-g%1')

console.log(f(0) == 0);
console.log(f(1) == 1);
console.log(f(2) == 1);
console.log(f(3) == 1);
console.log(f(4) == 2);
console.log(f(8) == 2);
console.log(f(9) == 3);
console.log(f(15) == 3);
console.log(f(16) == 4);
console.log(f(65535) == 255);
console.log(f(65536) == 256);
console.log(f(18446744073709551615) == 4294967296);

I hope you can excuse the last test, since JavaScript interprets the literal value 18446744073709551615 as 18446744073709552000. This is because JavaScript uses the IEEE 754 standard, which can only store every consecutive positive integer up to 9007199254740992 (2^53).

An alternative method that's even shorter is below. However, it does not meet the speed optimization requirements:

JavaScript (ES6) 30 bytes (non-competing)

n=>eval('for(a=0;a*a<=n;)a++')

Tests:

f=n=>eval('for(a=0;a*a<=n;)a++')

console.log(f(0) == 0);
console.log(f(1) == 1);
console.log(f(2) == 1);
console.log(f(3) == 1);
console.log(f(4) == 2);
console.log(f(8) == 2);
console.log(f(9) == 3);
console.log(f(15) == 3);
console.log(f(16) == 4);
console.log(f(65535) == 255);
console.log(f(65536) == 256);
// console.log(f(18446744073709551615) == 4294967296)

f=n=>eval('for(a=4294967290;a*a<=n;)a++')

console.log(f(18446744073709551615) == 4294967296);

The last test case hypothetically evaluates to true, but would take around a month to execute.

Answer 4

Dyalog APL, 8 bytes

⌊*∘1.5÷⊢

⌊^n³⁄₂∕_n⌋ as follows:
*∘1.5 the power-1.5 function
⊢ the pass-through function
(*∘1.5) ÷ ⊢ is the power-1.5 divided by the number itself
⌊ floor

Uses ⎕DIV←1 which often is default.

For the fun of it, here is a generalized solution that lets you calculate any root without raising to any power < 1:

⌊⊣(*÷⊣)(1+(÷⊢))

Answer 5

Swift 2, 43 bytes

let f={a in (0..<a).filter{$0*$0<=a}.last!}

Try here. There is a caveat - it won't compile unless the function is called, ie f(255), as type inference is unable to infer the return type.

Answer 6

Mathematica, 20

⌊#^1.5/1~Max~#⌋&

Answer 7

Pyke, 7 bytes (noncompeting)

#Xt)ltt

Try it here!

Finds the first number where i*i>=n and takes 2 from the number of numbers it had to check to get there

Answer 8

C++17, 80 bytes

auto f(auto n){auto x=1ul<<32,a=x-x;for(;x/=2;)a+=(a+x)*(a+x)<=n?x:0;return a;};

Explanation

This computes one bit per iteration, accumulating the result in a.

Tests

int main()
{
    return
        + (f(0) != 0)
        + (f(1) != 1)
        + (f(1) != 1)
        + (f(2) !=  1)
        + (f(3) !=  1)
        + (f(4) !=  2)
        + (f(8) !=  2)
        + (f(9) !=  3)
        + (f(15) !=  3)
        + (f(16) !=  4)
        + (f(65535) != 255)
        + (f(65536) != 256)
        + (f(18446744073709551615ul) != 4294967295)
        ;
}

Answer 9

Tellurium(non-competing), 8 bytes

@s|Iqg^`

This defines a function named s that converts input to an integer (I), calculates the square root (q) and rounds it to the floor (g)

The function can be called using =s.

Alternatively, 7 bytes

{Iqg^}f

This one defines an anonymous function that can be called using ä.

Answer 10

Lua, 74 bytes

n=io.read() if n==0 then print(0) os.exit() end print(math.floor(n^1.5/n))

Try it online!