47
\$\begingroup\$

The challenge is to implement a program or function (subsequently referred to as "program") that takes a nonnegative integer \$n\$ as input and returns \$n\over\sqrt{2}\$ (the input divided by the square root of two) as output, rounded to a nonnegative integer.

You may take your input and output in any reasonable format; for example stdin/stdout, files, or arguments/return values would all be acceptable.

You are required to use, at minimum, the largest fixed-size integer type offered by your language, and if an unsigned variant of this is available, you must use it. If your language has no built-in integer type (e.g. JavaScript) you are allowed to use its default numerical type (e.g. floating point); for languages with no concept of a number (e.g. regex), input and output can be e.g. the length of a string.

It is not required to reject negative integers; a submission that returns correct answers for negative inputs is allowed, but not required. Undefined behavior with negative inputs is allowed.

You are allowed and encouraged to use arbitrary-precision integer types if you so desire, but the type must either be a built-in, part of a standard library, or implemented from scratch in your program. As such, there are two categories of competition in this challenge:

  1. Precision limited by built-in types (fixed-size integer, floating point, etc.)
  2. Arbitrary precision (recursion and memory allocation, if used, can be assumed to be unlimited, where appropriate to the language in question)

Despite what the title might imply, you may use any rounding algorithm you want (floor, ceiling, nearest half up, nearest half even, arbitrary, or even random), as long as the difference between the integer returned value and the theoretical exact (irrational) value is always less than \$1\$ for all inputs that fit in your chosen integer type (but exactly 0 for an input of 0). All inputs up to the maximum representable value must return a correct output.

In a way, the job of this program is to calculate the irrational number \$\sqrt{2}\$ to the requested precision, presenting it in the form of an integer. This is why solutions using arbitrary-precision types are encouraged, but not required.

This is a challenge. Standard loopholes are denied. The program with the least number of bytes wins. That said, this challenge is not only about which answer wins overall; it's also about seeing how concisely the challenge can be solved in each language, seeing how each language "prefers" to handle rounding, and how hard it is to solve in esoteric languages. And for those submissions that choose to use arbitrary precision, it's about seeing how concisely this can be done in the language.

Test cases

Within the Precision-limited category, only the cases that are in range of the language's capability are required to pass.

If your solution is too slow to demonstrably pass the larger inputs (or runs out of memory/stack), it becomes all the more important to explain it sufficiently well, so that it can be understood that it would pass.

Input → Floor or Ceiling
0 → 0 (this is the only input that can only result in one valid output)
1 → 0 or 1
2 → 1 or 2
3 → 2 or 3
4 → 2 or 3
5 → 3 or 4
10 → 7 or 8
32 → 22 or 23
500 → 353 or 354
1000 → 707 or 708
1000000 → 707106 or 707107
186444716 → 131836322 or 131836323
1000000000 → 707106781 or 707106782
2147483647 → 1518500249 or 1518500250
3037000499 → 2147483647 or 2147483648
4294967295 → 3037000499 or 3037000500
4503599627370496 → 3184525836262886 or 3184525836262887
9223372036854775807 → 6521908912666391105 or 6521908912666391106
18446744073709551615 → 13043817825332782211 or 13043817825332782212
10000000000000000000000000000000000000 → 7071067811865475244008443621048490392 or 7071067811865475244008443621048490393
956287480911872131784896176254337633353980911149964074434383 → 676197362516585909969655173274459790030028262421622111830069 or 676197362516585909969655173274459790030028262421622111830070
\$\endgroup\$
3
  • 16
    \$\begingroup\$ Just in case someone is tempted to use Brainbool or something similar, I'll just leave a link to the appropriate loophole here. \$\endgroup\$ Commented Jan 24, 2020 at 6:26
  • 9
    \$\begingroup\$ Shifting half a bit requires more than bitwise insight to solve. \$\endgroup\$
    – user85052
    Commented Jan 24, 2020 at 10:29
  • 5
    \$\begingroup\$ Suggested test case: 9223372036854775807 \$\endgroup\$
    – 640KB
    Commented Jan 24, 2020 at 22:18

58 Answers 58

1
2
2
\$\begingroup\$

JavaScript (Node.js) arbitrary-precision, 62 58 bytes

Thanks to Arnauld saving 4 bytes

(n,v=n*n/2n,m=x=>x-(y=v/x+x>>1n)>>1n?m(y):y)=>v<2n?v:m(1n)

Try it online!

This is sqrt(n*n/2) after golfing the iterative Newton method sqrt() from https://stackoverflow.com/a/53684036.

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

Haskell, 32 bytes

h n=last[x|x<-[0..n],2*x^2<=n^2]

This submission works for arbitrary precision integers, but is very slow because it checks every number \$x\$ below \$n\$ for whether it satisfies the equation \$ 2x^2\leq n^2\$, then takes the last one. Thus the runtime is exponential in the bit length of the input number.

Try it online!

Haskell, 64 bytes

g n|n<2=n|s<-g(n`div`4)*2=last$s+1:[s|(s+1)^2>n]
f n=g$n*n`div`2

This submission also works for arbitrary precision integer and is much faster (all test cases instantaneous). It is based on the digit-by-digit integer square root listed on Wikipedia.

Try it online!

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

Ruby, 20 bytes

->n{(n/2**0.5).to_i}

Try it online!

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

Husk, 3 bytes

÷√2

Try it online!

Explanation

 √2  Find the square root of 2 (pretty straightforward).
÷  ⁰ Floor division with the input.
     Note that the numerator is the input, NOT the square root of 2.
\$\endgroup\$
2
\$\begingroup\$

AppleSoft BASIC, 24 bytes

The (js) emulator allows for huge integers (and is way too fast), but a real Apple II would have overflowed at 1000000. Integer values have a fixed range of -32767 to 32767.

The 24-byte "function":

9?INT(N/SQR(2)):RETURN

The full test program:

0DATA0,1,2,3,4,5,10,32,500,1000,1000000,186444716,1000000000,2147483647,3037000499
1FORI=1TO15:READN:GOSUB9:NEXT:END
9?INT(N/SQR(2)):RETURN
\$\endgroup\$
2
\$\begingroup\$

Scratch, 62 bytes

when gf clicked
ask()and wait
say(round((answer)/([sqrt v]of(2
\$\endgroup\$
2
\$\begingroup\$

MMIX, 36 bytes (9 instrs)

3FFF0001 F60100FF 3B00003F
E0FFB5D4 E5FFF333 E6FFF9DE
E7FF6484 1E0000FF F8010000

Explanation

3FFF0001: SRU $255,$0,1
F60100FF: PUT rD,$255 Put input / 2 in hidiv register.
3B00003F: SLU $0,$0,1 Multiply input by \$2^{63}\$ (mod \$2^{64}\$).
E0FFB5D4: SETH $255,#B5D4
E5FFF333: INCMH $255,#F333
E6FFF9DE: INCML $255,#F9DE
E7FF6484: INCL $255,#6484 Set temp to \$\lfloor\sqrt2\mathop\cdot2^{63}\rfloor\$.
1E0000FF: DIVU $0,$0,$255 Divide \$2^{63}\$ times input by temp.¹
F8010000: POP 1,0 Return one register

The value of 0xb5d4f333f9de6484 I used for \$\sqrt2\mathop\cdot2^{63}\$ was hand-calculated by bisecting search.

  1. DIVU $X,$Y,$Z sets $X to the quotient of rD * 2^64 + $Y divided by $Z, rounding down (and rR to the remainder, though it isn't used).
\$\endgroup\$
2
\$\begingroup\$

Perl 5 -p, 15 13 bytes

$_=0|$_/2**.5

Try it online!

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

Lua, 16 bytes

print(...//2^.5)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

cQuents, 11 bytes

#|1:A_/2^.5

Try it online!

Explanation

#|1          output the first term
   :         mode: sequence
             each term equals:
    A        input
     _/            //
       2              2
        ^               **
         .5                .5
\$\endgroup\$
1
\$\begingroup\$

R, 19 bytes

function(i)i%/%2^.5

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 17 bytes

Another arbitrary-precision answer.

n->sqrtint(n^2\2)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

AWK, 19 17 bytes

1,$0=int($0/2^.5)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Zsh, 17 bytes

Built-ins only. No need to use zmodload zsh/mathfunc as basic math capabilities of zsh are pretty decent. Correct up to 4503599627370496, after that it overflows. Try it Online!

<<<$[(n/2**.5)^0]
\$\endgroup\$
1
  • 1
    \$\begingroup\$ With -o cprecedences, you can drop the parentheses: Try it online! \$\endgroup\$
    – pxeger
    Commented Jan 1, 2022 at 8:41
1
\$\begingroup\$

Vyxal, 3 bytes

2√ḭ

Try it Online!

\$\endgroup\$
1
\$\begingroup\$

Raku, 11 bytes

0+|*/2.sqrt

Try it online!

\$\endgroup\$
1
+50
\$\begingroup\$

Desmos, 20 bytes

f(n)=floor(n/\sqrt2)

Try it on Desmos!

\$\endgroup\$
1
  • \$\begingroup\$ I think you can use ceil instead of floor for -1. \$\endgroup\$
    – Bbrk24
    Commented Apr 10, 2023 at 18:02
1
\$\begingroup\$

Charcoal, 46 bytes

≔⁰θ≔⁰ηF↨÷XN²¦²¦⁴«≔⁺×θ⁴ιθ≦⊗η¿›θ⊗η«≧⁻⊕⊗ηθ≦⊕η»»Iη

Try it online! Link is to verbose version of code. Performs an arbitrary-precision floored integer square root of n²/2 using the binary square root algorithm as demonstrated e.g. by Dr. Math. Explanation:

≔⁰θ≔⁰η

Set the accumulator and result to zero.

F↨÷XN²¦²¦⁴«

Loop over the base 4 digits of n²/2.

≔⁺×θ⁴ιθ

Multiply the accumulator by 4 and add the next digit.

≦⊗η

Double the result.

¿›θ⊗η«

If the accumulator is greater than double the doubled result, ...

≧⁻⊕⊗ηθ≦⊕η

... then subtract the incremented doubled result from the accumulator and increment the result.

»»Iη

Print the result once all of the digits have been processed.

\$\endgroup\$
1
\$\begingroup\$

Thunno, \$ 3 \log_{256}(96) \approx \$ 2.47 bytes

2t,

Attempt This Online!

2 pushes 2; t square roots it; , does integer division.

\$\endgroup\$
1
\$\begingroup\$

J, 9 bytes

<.@%2%:2:

Attempt This Online!

<.@%2%:2:
       2:  NB. literal 2
    2%:    NB. sqrt
   %       NB. division
  @        NB. then
<.         NB. floor
\$\endgroup\$
1
\$\begingroup\$

Trilangle, 41 bytes

<2?:2'L0'*<....'~~*22.L(-Sj2,7>~,!@..._.^

Outputs the larger number for even inputs, and the smaller number for odd inputs. Doesn't work for numbers larger than 4096 due to the integer limit, and for 4096 exactly it invokes UB but still outputs a valid result on my machine.

Try it in the online interpreter!

For the lack of floating-point numbers or a sqrt builtin, this computes the smallest nonnegative integer \$m\$ for which \$m^2 \ge n\left\lfloor\frac{n}{2}\right\rfloor\$. It turns out to be slightly more compact to add some bitwise complement instructions, replacing ++m with m = ~m; --m; m = ~m.

\$\endgroup\$
1
\$\begingroup\$

FRACTRAN, 15 14 fractions

-1 fraction thanks to my stupidity

22/35 14/55 1/14 1/22 15/2 14/5 143/119 91/187 3211/11 17/39 143/17 13/3 1/13 1/7

Try it online

A port of my Brainlove answer. Accepts input as 2^n, returns as 19^n.

\$\endgroup\$
2
  • \$\begingroup\$ Very cool choice of language. But there's a bug – it returns 706 for an input of 1000, when the allowed outputs are 707 or 708. \$\endgroup\$
    – Deadcode
    Commented Apr 11, 2023 at 15:58
  • \$\begingroup\$ Should be fixed now, there was one leftover 3 from some debugging. \$\endgroup\$
    – Kosatka
    Commented Apr 11, 2023 at 17:02
1
\$\begingroup\$

Thunno 2, 3 bytes

2ƭ÷

Attempt This Online!

Explanation

2ƭ÷  # Implicit input
     # n
  ÷  #   //
 ƭ   #      sqrt( )
2    #           2
     # Implicit output
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 31 bytes

n=>(g=i=>i*i*2<n*n?g(++i):i)(0)

Try it online!

or BigInt version, anyway really large values impractical to run

Brute-force i till reach

\$\endgroup\$
1
\$\begingroup\$

Python 3.8 (pre-release), 40 bytes

All other python answers are limited to integers smaller than about 10**16.

Here is one that works with all python integers, giving the correct result even for arbitrarily large integers. Always rounds down.

lambda x:isqrt(x*x//2)
from math import*

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Clarion, 58 bytes

Takes an integer input as the first command-line parameter, and displays the result in a Win32 MessageBox

Program
 Map.
Code
 Stop(Round((Command(1)/Sqrt(2)),1))
\$\endgroup\$
0
\$\begingroup\$

Arturo, 17 bytes

$=>[floor&/2^0.5]

Try it

\$\endgroup\$
0
\$\begingroup\$

Nibbles, 4.5 bytes (9 nibbles)

^/*$$~-2
  *         # multiply
   $        # input
    $       # by itself,
 /          # divide by
     ~      # 2,
^     -2    # and get the square-root

enter image description here

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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