Shift right by half a bit

Question

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

• FryAmTheEggman: Just in case someone is tempted to use Brainbool or something similar, I'll just leave a link to the appropriate loophole here.
• user85052: Shifting half a bit requires more than bitwise insight to solve.
• 640KB: Suggested test case: 9223372036854775807

Answer 1

Regex (ECMAScript+(?*)), (削除) 1169 (削除ここまで) (削除) 929 (削除ここまで) (削除) 887 (削除ここまで) (削除) 853 (削除ここまで) (削除) 849 (削除ここまで) 708 bytes

-141 bytes by using the second form of shortened division, where \$A^2 > C\$

Regex was never designed to do mathematics. It has no concept of arithmetic. However, when input is taken in the form of bijective unary, as a sequence of identical characters in which the length represents a natural number, it is possible to do a wide range of operations, building up from the simple primitives available, which basically amount to addition, comparison, multiplication by a constant, and modulo. Everything must fit inside the input; it isn't possible to directly operate on numbers larger than that.

In ECMAScript regex, it's especially difficult (and therefore interesting) to do even some of the simplest of operations, because of the limitation that all backrefs captured in a loop are reset to empty at the beginning of each iteration – which makes it impossible to count anything directly. It's nevertheless possible to match prime numbers, powers of N, Nth powers, arbitrary multiplication and exponentiation, Fibonacci numbers, factorial numbers, abundant numbers, and more, much of which is demonstrated in my other answers.

One of the operations that turns out to be far more verbose than the rest is to "calculate an irrational number". I initially discussed this with teukon back in 2014. The only known way to do this is to emulate operations on numbers larger than the input, and probably the simplest way to do this is by working in a number base chosen based on what can fit into the input.

It wasn't until late 2018 that I finally set about to implementing the theory I had sketched in 2014. Implementing it involved adapting the multiplication algorithm to work with factors of 0, which turned out to golf rather elegantly. (The underlying multiplication algorithm is explained in this post.) The basic algorithm is this:

For input \$N\$, we want to calculate \$M=\lfloor{N\over\sqrt2}\rfloor\$. So we want the largest \$M\$ such that \2ドルM^2\le N^2\$.

If we take the "number base" to be \$k=\lceil\sqrt N\rceil\$ or \$\lfloor\sqrt N\rfloor\!+\!1\$, all multiplication operations \$m\cdot n\$ on \0ドル\leq m,n<k\$ are guaranteed to fit in the available space.

So if \$N=A k+B\$, where \0ドル\leq A,B\lt k\$, we can calculate \$N^2\$:

$$N^2=(A k+B)^2=A^2 k^2+2 A B k+B^2$$

We must then do division, modulo, and carry to bring \$A^2\$, \2ドル A B\$, and \$B^2\$ back into the range of a base \$k\$ "digit". A similar operation is then done to calculate \2ドル M^2\$ iterated over the decreasing consecutive possible values of \$M\$, using digit-by-digit comparison to test for \2ドルM^2\le N^2\$, until the first \$M\$ is found that passes the test.

So while the basic concept is simple enough, it adds up to a lot of calculations, and the regex is huge! And this is probably the simplest calculation of an irrational number that can be done in ECMAScript regex. (It is still unknown whether it's possible to calculate a transcendental number to arbitrary precision in regex.)

This regex uses molecular lookahead, a.k.a. non-atomic lookahead, represented as (?*...). Without this feature, it would be much harder (or at least much more verbose) to implement.

A choice I made early on, to depart from pure code golf by going for mathematical aesthetics, turned out to be a very interesting. I chose to use \$k=\lceil\sqrt N\rceil\$ because it has the very neat property of making the calculations fit perfectly into \$N\$ if \$N\$ is a perfect square, whereas \$k=\lfloor\sqrt N\rfloor\!+\!1\$ is basically chaotic for all inputs. They both yield the same final outputs, but the former is just cleaner. A few golfs later, this choice ended up net increasing the total length of the regex by 8 bytes, so I figured it was worth it. (This change is in the git version history.) But another golf later that day, unbeknownst to me, was actually dependent on that decision! The skipping of a divisibility check in a division calculation makes \$N=25\$ return the incorrect output of \$M=11\$ instead of \$M=17\$ if \$k=\lfloor\sqrt N\rfloor\!+\!1\$, but works perfectly for all inputs if \$k=\lceil\sqrt N\rceil\$. So the actual net change in byte length was zero! It was a purely aesthetic decision for over two years.

At the time I did not understand why that division optimization worked, but this is now fully explained thanks to H.PWiz. The shortened form of division (削除) used at the beginning of the calculation of \$M^2\$ (削除ここまで) gives the correct quotient \$B\$ when \$A+2 < 4B\$, where \$C\$ is the dividend and \$A\$ is the divisor. Previously I believed that it was only guaranteed to work when \$A \le B\$. [This is no longer used, due to the number base switch.]

And now, with the discovery of a second shortened form of division that gives the correct quotient when \$A^2 > C\$, I found a major opportunity to use it in this regex! It only works when \$k=\lfloor\sqrt N\rfloor\!+\!1\$, so now I've switched back to that number base. It's saving 141 bytes! It's oddly convenient that this just happened to exist and works perfectly for this exact use.

(?=(x(x*)).*(?=1円*$)2円+$)(?=(x1円)+(x?(x*)))(?=4円(x(x*?))1円+$)(?=.*(?=(?=4円*$)4円5円+$)(x*?)(?=3円*$)(x?(x*?))(1円+$|$9円))(?=.*(?=(?=4円*$)(?=6円*$)(?=4円7円+$)6円5円+$|$4円)(x*?)(?=3円*$)(x?(x*?))(1円+$|$13円))(?=.*(?=12円12円9円$)(x*?)(?=3円*$)(x?(x*?))(1円+$|$17円))(?*.*?(?=((?=3円*(x?(x*)))21円(x(x*?))1円+$)))(?=.*(?=23円*$)(23円24円+$))(?=.*(?=(?=21円*$)21円22円+$)(x*?)(?=3円*$)(x?(x*?))(1円+$|$27円))(?=.*(?=(?=21円*$)(?=23円*$)(?=21円24円+$)23円22円+$|$21円)(x*?)(?=3円*$)(x?(x*?))(1円+$|$31円))(?=.*(?=30円30円27円$)(x*?)(?=3円*$)(x?(x*?))(1円+$|$35円))(?=.*(?=26円26円)(?=3円*(x*))(1円(x)|))(?=.*(?=34円34円40円)(?=3円*(x*))(1円(x)|))(?=(?=(.*)13円13円17円(?=6円*$)6円7円+$)44円(x+|(?=.*(?!16円)41円|(?!.*(?!38円)8円).*(?=16円$)41円$))(25円31円31円35円){2}43円$)20円|xx?\B|

Try it on repl.it

This regex is on GitHub with a full version history.

# Given an input number N in the domain ^x*,ドル this regex returns floor(N / sqrt(2))
(?=
 (x(x*)) # 1円 = will be the square root of the main number, rounded down; 2円 = 1円 - 1
 .*(?=1円*$)
 2円+$
)
# Step 1: Calculate N*N in base floor(sqrt(N))+1. Thanks to this choice of number base to work in, we'll be able to use the
# second shortened form of division in all places where the number base is the divisor, because it's guaranteed to give the
# correct quotient when the dividend is less than the squared divisor, and N itself is less than this. This form of division
# can be recognized by its lazy rather than greedy matching of the quotient, and only one divisibility test following that.
(?=(x1円)+(x?(x*))) # 3円 = 1円+1 = floor(sqrt(N))+1, the number base to work in; 4円 = N % 3円; 5円 = 4円-1, or 0 if 4円==0
(?=
 4円
 (x(x*?)) # 6円 = floor(N / 3円); 7円 = 6円-1
 1円+$
)
(?=
 .*
 (?=
 (?=4円*$) # tail = 4円 * 4円
 4円5円+$
 )
 (x*?)(?=3円*$) # 8円 = (4円 * 4円) % 3,円 the base-3円 digit in place 0 of the result for N*N
 (x?(x*?)) # 9円 = floor((4円 * 4円) / 3円); 10円 = 9円-1, or 0 if 9円==0
 (
 1円+$
 |
 $9円 # must make a special case for 9円==0, because 1円 is nonzero
 )
)
(?=
 .*
 (?=
 (?=4円*$) # tail = 4円 * 6円; must do symmetric multiplication, because 4円 is occasionally 1 larger than 6円
 (?=6円*$)
 (?=4円7円+$)
 6円5円+$
 |
 $4円 # must make a special case for 4円==0, because 6円 might not be 0
 )
 (x*?)(?=3円*$) # 12円 = (4円 * 6円) % 3円
 (x?(x*?)) # 13円 = floor((4円 * 6円) / 3円); 14円 = 13円-1, or 0 if 13円==0
 (
 1円+$
 |
 $13円 # must make a special case for 13円==0, because 1円 is nonzero
 )
)
(?=
 .*(?=12円12円9円$) # tail = 2 * 12円 + 9円
 (x*?)(?=3円*$) # 16円 = (2 * 12円 + 9円) % 3,円 the base-3円 digit in place 1 of the result for N*N
 (x?(x*?)) # 17円 = floor((2 * 12円 + 9円) / 3円); 18円 = 17円-1, or 0 if 17円==0
 (
 1円+$
 |
 $17円 # must make a special case for 17円==0, because 1円 is nonzero
 )
) # {6円*6円 + 2*13円 + 17円} = the base-3円 digit in place 2 of the result for N*N, which is allowed to exceed 3円 and will always do so;
 # Note that it will be equal to N iff N is a perfect square, because of the choice of number base.
# Step 2: Find the largest M such that 2*M*M is not greater than N*N
# Step 2a: Calculate M*M in base 3円
(?*
 .*? # Determine value of M with backtracking, starting with largest values first
 (?=
 ( # 20円 = M
 (?=3円*(x?(x*)))21円 # 21円 = M % 3円; 22円 = 21円-1, or 0 if 21円==0
 (x(x*?)) # 23円 = floor(M / 3円); 24円 = 23円-1
 1円+$
 )
 )
)
(?=
 .*
 (?=23円*$)
 (23円24円+$) # 25円 = 23円 * 23円
)
(?=
 .*
 (?=
 (?=21円*$) # tail = 21円 * 21円
 21円22円+$
 )
 (x*?)(?=3円*$) # 26円 = (21円 * 21円) % 3,円 the base-3円 digit in place 0 of the result for M*M
 (x?(x*?)) # 27円 = floor((21円 * 21円) / 3円); 28円 = 27円-1, or 0 if 27円==0
 (
 1円+$
 |
 $27円 # must make a special case for 27円==0, because 1円 is nonzero
 )
)
(?=
 .*
 (?=
 (?=21円*$) # tail = 21円 * 23円; must do symmetric multiplication, because 21円 is occasionally 1 larger than 23円
 (?=23円*$)
 (?=21円24円+$)
 23円22円+$
 |
 $21円 # must make a special case for 21円==0, because 23円 might not be 0
 )
 (x*?)(?=3円*$) # 30円 = (21円 * 23円) % 3円
 (x?(x*?)) # 31円 = floor((21円 * 23円) / 3円); 32円 = 31円-1, or 0 if 31円==0
 (
 1円+$
 |
 $31円 # must make a special case for 31円==0, because 1円 is nonzero
 )
)
(?=
 .*(?=30円30円27円$) # tail = 2 * 30円 + 27円
 (x*?)(?=3円*$) # 34円 = (2 * 30円 + 27円) % 3,円 the base-3円 digit in place 1 of the result for M*M
 (x?(x*?)) # 35円 = floor((2 * 30円 + 27円) / 3円); 36円 = 35円-1, or 0 if 35円==0
 (
 1円+$
 |
 $35円 # must make a special case for 35円==0, because 1円 is nonzero
 )
) # {25円 + 2*31円 + 35円} = the base-3円 digit in place 2 of the result for M*M, which is allowed to exceed 3円 and will always do so
# Step 2b: Calculate 2*M*M in base 3円
(?=
 .*
 (?=26円26円) # tail = 2*26円
 (?=3円*(x*)) # 38円 = (2*26円) % 3,円 the base-3円 digit in place 0 of the result for 2*M*M
 (1円(x)|) # 40円 = floor((2*26円) / 3円) == +1 carry if {2*26円} does not fit in a base 3円 digit
)
(?=
 .*
 (?=34円34円40円) # tail = 2*34円 + 40円
 (?=3円*(x*)) # 41円 = (2*34円 + 40円) % 3,円 the base-3円 digit in place 1 of the result for 2*M*M
 (1円(x)|) # 43円 = floor((2*34円 + 40円) / 3円) == +1 carry if {2*34円 + 40円} does not fit in a base 3円 digit
) # 2*(25円 + 2*31円 + 35円) + 43円 = the base-3円 digit in place 2 of the result for 2*M*M, which is allowed to exceed 3円 and will always do so
# Step 2c: Require that 2*M*M <= N*N
(?=
 (?=
 (.*) # 44円
 13円13円17円
 (?=6円*$) # tail = 6円 * 6円
 6円7円+$
 )
 44円 # tail = {6円*6円 + 2*13円 + 17円}; we can do this unconditionally because our digits in place 2 are always greater than those in places 0..1
 (
 x+
 |
 (?=
 .*(?!16円)41円 # 41円 < 16円
 |
 (?!.*(?!38円)8円) # 38円 <= 8円
 .*(?=16円$)41円$ # 41円 == 16円
 )
 )
 (25円31円31円35円){2}43円$ # 2*(25円 + 2*31円 + 35円) + 43円
)
20円
|xx?\B| # handle inputs in the domain ^x{0,4}$

---

Regex (ECMAScript 2018), (削除) 861 (削除ここまで) 720 bytes

This is a direct port of the (削除) 849 (削除ここまで) 708 byte molecular lookahead version, using variable length lookbehind.

(?=(x(x*)).*(?=1円*$)2円+$)(?=(x1円)+(x?(x*)))(?=4円(x(x*?))1円+$)(?=.*(?=(?=4円*$)4円5円+$)(x*?)(?=3円*$)(x?(x*?))(1円+$|$9円))(?=.*(?=(?=4円*$)(?=6円*$)(?=4円7円+$)6円5円+$|$4円)(x*?)(?=3円*$)(x?(x*?))(1円+$|$13円))(?=.*(?=12円12円9円$)(x*?)(?=3円*$)(x?(x*?))(1円+$|$17円))(?=.*?(?=((?=3円*(x?(x*)))21円(x(x*?))1円+$))(?<=(?=(?=.*(?=23円*$)(23円24円+$))(?=.*(?=(?=21円*$)21円22円+$)(x*?)(?=3円*$)(x?(x*?))(1円+$|$27円))(?=.*(?=(?=21円*$)(?=23円*$)(?=21円24円+$)23円22円+$|$21円)(x*?)(?=3円*$)(x?(x*?))(1円+$|$31円))(?=.*(?=30円30円27円$)(x*?)(?=3円*$)(x?(x*?))(1円+$|$35円))(?=.*(?=26円26円)(?=3円*(x*))(1円(x)|))(?=.*(?=34円34円40円)(?=3円*(x*))(1円(x)|))(?=(?=(.*)13円13円17円(?=6円*$)6円7円+$)44円(x+|(?=.*(?!16円)41円|(?!.*(?!38円)8円).*(?=16円$)41円$))(25円31円31円35円){2}43円$))^.*))20円|xx?\B|

Try it online!

This regex is on GitHub.

# Given an input number N in the domain ^x*,ドル this regex returns floor(N / sqrt(2))
(?=
 (x(x*)) # 1円 = will be the square root of the main number, rounded down; 2円 = 1円 - 1
 .*(?=1円*$)
 2円+$
)
# Step 1: Calculate N*N in base floor(sqrt(N))+1. Thanks to this choice of number base to work in, we'll be able to use the
# second shortened form of division in all places where the number base is the divisor, because it's guaranteed to give the
# correct quotient when the dividend is less than the squared divisor, and N itself is less than this. This form of division
# can be recognized by its lazy rather than greedy matching of the quotient, and only one divisibility test following that.
(?=(x1円)+(x?(x*))) # 3円 = 1円+1 = floor(sqrt(N))+1, the number base to work in; 4円 = N % 3円; 5円 = 4円-1, or 0 if 4円==0
(?=
 4円
 (x(x*?)) # 6円 = floor(N / 3円); 7円 = 6円-1
 1円+$
)
(?=
 .*
 (?=
 (?=4円*$) # tail = 4円 * 4円
 4円5円+$
 )
 (x*?)(?=3円*$) # 8円 = (4円 * 4円) % 3,円 the base-3円 digit in place 0 of the result for N*N
 (x?(x*?)) # 9円 = floor((4円 * 4円) / 3円); 10円 = 9円-1, or 0 if 9円==0
 (
 1円+$
 |
 $9円 # must make a special case for 9円==0, because 1円 is nonzero
 )
)
(?=
 .*
 (?=
 (?=4円*$) # tail = 4円 * 6円; must do symmetric multiplication, because 4円 is occasionally 1 larger than 6円
 (?=6円*$)
 (?=4円7円+$)
 6円5円+$
 |
 $4円 # must make a special case for 4円==0, because 6円 might not be 0
 )
 (x*?)(?=3円*$) # 12円 = (4円 * 6円) % 3円
 (x?(x*?)) # 13円 = floor((4円 * 6円) / 3円); 14円 = 13円-1, or 0 if 13円==0
 (
 1円+$
 |
 $13円 # must make a special case for 13円==0, because 1円 is nonzero
 )
)
(?=
 .*(?=12円12円9円$) # tail = 2 * 12円 + 9円
 (x*?)(?=3円*$) # 16円 = (2 * 12円 + 9円) % 3,円 the base-3円 digit in place 1 of the result for N*N
 (x?(x*?)) # 17円 = floor((2 * 12円 + 9円) / 3円); 18円 = 17円-1, or 0 if 17円==0
 (
 1円+$
 |
 $17円 # must make a special case for 17円==0, because 1円 is nonzero
 )
) # {6円*6円 + 2*13円 + 17円} = the base-3円 digit in place 2 of the result for N*N, which is allowed to exceed 3円 and will always do so;
 # Note that it will be equal to N iff N is a perfect square, because of the choice of number base.
# Step 2: Find the largest M such that 2*M*M is not greater than N*N
# Step 2a: Calculate M*M in base 3円
(?=
 .*? # Determine value of M with backtracking, starting with largest values first
 (?=
 ( # 20円 = M
 (?=3円*(x?(x*)))21円 # 21円 = M % 3円; 22円 = 21円-1, or 0 if 21円==0
 (x(x*?)) # 23円 = floor(M / 3円); 24円 = 23円-1
 1円+$
 )
 )
 (?<=
 (?=
 (?=
 .*
 (?=23円*$)
 (23円24円+$) # 25円 = 23円 * 23円
 )
 (?=
 .*
 (?=
 (?=21円*$) # tail = 21円 * 21円
 21円22円+$
 )
 (x*?)(?=3円*$) # 26円 = (21円 * 21円) % 3,円 the base-3円 digit in place 0 of the result for M*M
 (x?(x*?)) # 27円 = floor((21円 * 21円) / 3円); 28円 = 27円-1, or 0 if 27円==0
 (
 1円+$
 |
 $27円 # must make a special case for 27円==0, because 1円 is nonzero
 )
 )
 (?=
 .*
 (?=
 (?=21円*$) # tail = 21円 * 23円; must do symmetric multiplication, because 21円 is occasionally 1 larger than 23円
 (?=23円*$)
 (?=21円24円+$)
 23円22円+$
 |
 $21円 # must make a special case for 21円==0, because 23円 might not be 0
 )
 (x*?)(?=3円*$) # 30円 = (21円 * 23円) % 3円
 (x?(x*?)) # 31円 = floor((21円 * 23円) / 3円); 32円 = 31円-1, or 0 if 31円==0
 (
 1円+$
 |
 $31円 # must make a special case for 31円==0, because 1円 is nonzero
 )
 )
 (?=
 .*(?=30円30円27円$) # tail = 2 * 30円 + 27円
 (x*?)(?=3円*$) # 34円 = (2 * 30円 + 27円) % 3,円 the base-3円 digit in place 1 of the result for M*M
 (x?(x*?)) # 35円 = floor((2 * 30円 + 27円) / 3円); 36円 = 35円-1, or 0 if 35円==0
 (
 1円+$
 |
 $35円 # must make a special case for 35円==0, because 1円 is nonzero
 )
 ) # {25円 + 2*31円 + 35円} = the base-3円 digit in place 2 of the result for M*M, which is allowed to exceed 3円 and will always do so
 # Step 2b: Calculate 2*M*M in base 3円
 (?=
 .*
 (?=26円26円) # tail = 2*26円
 (?=3円*(x*)) # 38円 = (2*26円) % 3,円 the base-3円 digit in place 0 of the result for 2*M*M
 (1円(x)|) # 40円 = floor((2*26円) / 3円) == +1 carry if {2*26円} does not fit in a base 3円 digit
 )
 (?=
 .*
 (?=34円34円40円) # tail = 2*34円 + 40円
 (?=3円*(x*)) # 41円 = (2*34円 + 40円) % 3,円 the base-3円 digit in place 1 of the result for 2*M*M
 (1円(x)|) # 43円 = floor((2*34円 + 40円) / 3円) == +1 carry if {2*34円 + 40円} does not fit in a base 3円 digit
 ) # 2*(25円 + 2*31円 + 35円) + 43円 = the base-3円 digit in place 2 of the result for 2*M*M, which is allowed to exceed 3円 and will always do so
 # Step 2c: Require that 2*M*M <= N*N
 (?=
 (?=
 (.*) # 44円
 13円13円17円
 (?=6円*$) # tail = 6円 * 6円
 6円7円+$
 )
 44円 # tail = {6円*6円 + 2*13円 + 17円}; we can do this unconditionally because our digits in place 2 are always greater than those in places 0..1
 (
 x+
 |
 (?=
 .*(?!16円)41円 # 41円 < 16円
 |
 (?!.*(?!38円)8円) # 38円 <= 8円
 .*(?=16円$)41円$ # 41円 == 16円
 )
 )
 (25円31円31円35円){2}43円$ # 2*(25円 + 2*31円 + 35円) + 43円
 )
 )
 ^.*
 )
)
20円
|xx?\B| # handle inputs in the domain ^x{0,4}$

---

Regex (ECMAScript)

I have not yet ported this algorithm to basic ECMAScript. One way to do it would be to use \$k=\lceil\sqrt[\uproot{1}3]N\rceil\$ as the number base, and calculate:

$$N^2=(A k^2+B k+C)^2=A^2 k^4 + 2 A B k^3 + (2 A C + B^2)k^2 + 2 B C k + C^2$$

Another way would be to stick with \$k=\lceil\sqrt N\rceil\$, capture \$M\$ encoded into two or more backrefs, and emulate the existing calculations within the smaller available space. I'm not sure which way would be more concise. Either way, I expect the regex would roughly double in length.

• findusl: I never thought of regex as a programming language but I guess it is one? For sure not a Turing complete one though...
• Shaggy: Did you post this challenge just so you could post this solution?!
• Deadcode: @Shaggy I wouldn't have had the idea otherwise. Explained in the original sandbox post.
• Deadcode: @findusl It's certainly not Turing complete. Its power rests somewhere below primitive recursive, but exactly where hasn't really been pinned down. With unlimited scratch space it would be exactly primitive recursive; it's the extra limit of having to work within the input's space that changes this.

Answer 2

Python 3, (削除) 19 (削除ここまで) 17 bytes

A different python answer

lambda x:x//2**.5

-2 bytes thanks to @Mukundan

try it online

• Deadcode: Ooh, I like this method of rounding. Was scared for a moment there because I thought I wouldn't be able to accept this answer (output ends in .0), but I never said the output had to be in integer form, just that it had to be rounded to an integer. :)
• RGS: @Deadcode thanks for your feedback :)
• Mukundan314: Save 2 byte by doing truediv when dividing by sqrt of 2 instead of after it like lambda x:x//2**.5
• RGS: @Mukundan of course!!! Well pointed out :)
• paw88789: @RGS true. I wasn't sure from the original problem statement whether it mattered that one didn't necessarily get the correct values for these larger inputs.

Answer 3

Scratch 3.0, (削除) 7 (削除ここまで) 5 blocks/(削除) 62 (削除ここまで) 36 bytes

enter image description here

Try it on(削除) line (削除ここまで) Scratch!

As SB Syntax:

define(n
say(round((n)/([sqrt v]of(2

It's always fun to usual visual languages! At least I have built-ins this time.

-26 bytes thanks to @att

• Kevin Cruijssen: Am I the only one who read the SB Synthax initially as "when girlfriend clicked, ask and wait"? ;)
• 640KB: +1, I'm always a sucker for animated cats
• Bjonnfesk: @KevinCruijssen I read it like that as well - one could also ask whether it is the girlfriend who clicks, or if it is the girlfriend who gets clicked.
• att: 37 bytes. I'm not quite sure how many blocks that counts as, though.
• Deadcode: So I get it, this 36 byte answer is a lambda, whereas your original 62 byte answer (which @Nilster has recently reproduced) is a full program. But your link gives the function a name f, disagreeing with the source code shown here. And I confirmed that it works with the name deleted from both places, so why not link that version?

Answer 4

Regex (.NET), (削除) 106 (削除ここまで) 90 bytes

(?=(x*)(1円x?))(x*).*$(?<=(?=(?<-5>x)*1円(?<=3円))^2円((?<=(?=6円?(3円)*(?<=(?=3円$)(x*))).*)x)*)

Try it online!

Takes its input in unary, as a sequence of x characters whose length represents the number. Returns its output in group 3円.

By the very nature of this solution, its best-golfed form rounds arbitrarily – sometimes up, sometimes down. As such, it's more complicated to explain why it works, so I suggest reading the explanation of the 99 byte always-round-down solution below first. (This is oddly appropriate, given the order of operations in regexes that use right-to-left evaluated variable-length lookbehind.)

Compared to the always-round-down solution, this regex takes a shortcut. Instead of counting the number of times the anti-remainder was subtracted, it uses \$\lfloor{N\over 2}\rfloor\$ in place of that count. For even values of \$N\$ this is \1ドル\$ greater than the actual number of times the anti-remainder was subtracted (since it's never subtracted on the first iteration, and always subtracted on each subsequent iteration). As such, sometimes it doesn't change the resulting returned value \$M\$, but sometimes it results in finding an \$M\$ that is \1ドル\$ greater than the value it would otherwise have, i.e. \$\lceil{N\over\sqrt 2}\rceil\$ instead of \$\lfloor{N\over\sqrt 2}\rfloor\$.

For odd values of \$N\$, adding \1ドル\$ to that count effectively simulates the extra loop iteration done on \$\lfloor{N\over 2}\rfloor\$ in the always-round-down regex. The thing is, without actually doing that, we don't know whether the final value of the anti-remainder was greater than \$\lfloor{N\over 2}\rfloor\$ or not. Iff it was greater, then the anti-remainder subtraction count wouldn't have been incremented by \1ドル\$. Thus, by unconditionally effectively adding that \1ドル\$, we're doing the same thing for odd \$N\$ as we are for even \$N\$ – giving a return value of \$M\$ that is arbitrarily rounded up or down.

 # tail = N = input number
(?=
 (x*) # 1円 = floor(N / 2)
 (1円x?) # 2円 = ceil(N / 2)
)
(x*) # 3円 = guessed value of round(sqrt(N*N/2)) - may be rounded up or down
.*$ # tail = 0; head = N
(?<=
 # head = 0
 (?=
 (?<-5>x)* # head += 5円.capture_count
 1円 # head += 1円; this is 1 more than the actual number of times
 # 6円 was subtracted, which will change the 3円 result for some
 # even values of N from rounded-down to rounded-up. But for
 # odd values of N, it simulates subtracting 6円 from the last
 # half-chunk, which is not covered in the loop we did. Note
 # that depending on the final value of 6,円 it may be <= 1,円
 # in which case we'll get a rounded-down 3,円 or > 1,円 in which
 # case we'll get a rounded-up 3円.
 (?<=3円) # assert head ≥ 3円
 )
 ^2円 # force the loop below to iterate 1円 times; head = 0
 (
 (?<=
 # tail = N
 (?=
 6円? # tail -= 6,円 if 6円 is set
 (3円)* # X = floor(tail / 3円); tail -= 3円*X; 5円.capture_count += X;
 # note that in practice, 0 ≤ X ≤ 1;
 # Y = tail = remainder
 (?<=
 (?=3円$) # assert tail == 3円
 (x*) # 6円 = 3円 - Y
 )
 )
 .* # tail = N
 )
 x # head -= 1; tail += 1
 )*
)

Regex (.NET), (削除) 166 (削除ここまで) (削除) 104 (削除ここまで) 99 bytes

(?=(x*)(1円x?))(x*).*$(?<=(?=(?<-5>x)*(?<=3円))^1円(x(?<=(?=(6円)?(?<5>3円)*(?<=(?=3円$)(x*)))(.+2円)?))*)

Try it online!

Takes its input in unary, as a sequence of x characters whose length represents the number. Returns its output in group 3円.

This solution always rounds down, returning \$M=\lfloor{N\over\sqrt 2}\rfloor\$. It accomplishes this by calculating \$M=\lfloor\sqrt{N^2\over 2}\rfloor\$, which is done by searching for the largest value of \$M\$ for which \$\lfloor{{N^2\over 2}/M}\rfloor\ge M\$. A regex can't directly operate on values larger than the input, so this must be done by looping multiple times over \$N\$ instead of directly operating on \$N^2\$.

For even values of \$N\$ this is straightforward enough; we just loop over \$N/2\$ copies of \$N\$, subtracting \$M\$ from it as many times as will fit (which will be \0ドル\$ or \1ドル\$), taking note of the remainder, and then subtracting the corresponding "anti-remainder" (the remainder's difference from \$M\$) at the beginning of the next loop iteration. Then the value of \$\lfloor{{N^2\over 2}/M}\rfloor\$ is the sum of the number of times \$M\$ was subtracted and the number of times the anti-remainder was subtracted. This works because for even \$N\$, we have \$\lfloor{N^2\over 2}\rfloor = \lfloor{N\over 2}\rfloor N\$.

For odd values of \$N\$, we do the above, but then do \1ドル\$ extra loop iteration, subtracting from \$\lfloor{N\over 2}\rfloor\$ instead of \$N\$. This works because for odd \$N\$, we have \$\lfloor{N^2\over 2}\rfloor = \lfloor{N\over 2}\rfloor N + \lfloor{N\over 2}\rfloor\$.

The number of times \$M\$ and the anti-remainder were subtracted are counted using the .NET feature of balanced groups, with (?<-5>x)* below.

 # tail = N = input number
(?=
 (x*) # 1円 = floor(N / 2)
 (1円x?) # 2円 = ceil(N / 2)
)
(x*) # 3円 = guessed value of floor(sqrt(N*N/2))
.*$ # tail = 0; head = N
(?<=
 # head = 0
 (?=
 (?<-5>x)* # head += 5円.capture_count
 (?<=3円) # assert head ≥ 3円
 )
 ^1円 # force the loop below to iterate 2円 times; head = 0
 (
 x # head -= 1; tail += 1
 (?<=
 # tail = 1円 if N is odd and this is the last iteration, or N otherwise
 (?=
 (6円)? # if 6円 is set: tail -= 6円; 5円.capture_count += 1
 (?<5>3円)* # X = floor(tail / 3円); tail -= 3円*X; 5円.capture_count += X;
 # note that in practice, 0 ≤ X ≤ 1;
 # Y = tail = remainder
 (?<=
 (?=3円$) # assert tail == 3円
 (x*) # 6円 = 3円 - Y
 )
 )
 (.+2円)? # unless N is odd and this is the last iteration: head = 0; tail = N;
 # else: head = 2円; tail = 1円
 )
 )*
)

This algorithm would not work on a regex flavor lacking variable-length lookbehind (and lookinto), because to loop more than once with a count that scales with \$N\$, the regex needs to subtract at least \1ドル\$ from \$tail\$ on each iteration (a zero-width loop iteration would result in terminating the loop). Without lookbehind/lookinto, it would be impossible to operate directly on \$N\$ after the first iteration. And once the current value of \$tail\$ went below the currently tested value of \$M\$, it would no longer be possible to operate on the value of \$M\$ in any way. Thus forward-declared backreferences, while required by this algorithm, aren't enough on their own.

So, a regex flavor with forward-declared backreferences but no variable-length lookbehind (or lookinto) could probably use an algorithm based on this one, but additional tricks would have to be used to emulate operating on larger numbers. I'm pretty sure it would not have to use the full-fledged algorithm of my ECMAScript solution, but I haven't worked out the details yet.

Regex (PCRE+(?^=)^RME ), 81 bytes

(?=(x*)(1円x?))(x*)(?^1=(x(?^=8円?(3円(?^=(6円?x)))*(x*)(?^3=7円(x*))))*)(?^3!6円?+1円x)

Try it on replit.com!

This is a port of the 90 byte .NET regex that rounds arbitrarily. It uses features available in PCRE, in addition to lookinto, a feature just added to RegexMathEngine. The fact that even after converting the use of .NET balancing groups to group-building, this regex is still 9 bytes smaller than the .NET version, demonstrates just how much expressibility is available with lookinto. The regex is also much easier understand in this form. (Lookinto is equal in power to variable-length lookbehind, i.e. there's nothing one can do that the other can't.)

 # tail = N = input number
(?=
 (x*) # 1円 = floor(N / 2)
 (1円x?) # 2円 = ceil(N / 2)
)
(x*) # 3円 = guess for round(sqrt(N*N/2)) - may be rounded up or down
(?^1= # Lookinto: tail = 1円
 (
 x # tail -= 1
 (?^= # Atomic lookinto: tail = N
 8円? # tail -= 8,円 if 8円 is set
 # X = floor(tail / 3円); tail -= 3円*X; 6円 += X;
 # Note that in practice, 0 ≤ X ≤ 1
 (
 3円 # Assert tail ≥ 3円; tail -= 3円
 (?^=
 ( # 6円 = sum of the following:
 6円? # previous value of 6円 if set, 0 otherwise
 x # 1
 )
 )
 )* # Match the above as many times as possible, minimum 0
 (x*) # 7円 = tail = remainder = dividend % 3円
 (?^3= # Atomic lookinto: tail = 3円
 7円 # tail -= 7円
 (x*) # 8円 = tail = 3円 - 7円
 )
 )
 )* # Iterate as many times as possible, which will be exactly 1円
)
(?^3! # Negative lookinto: tail = 3円
 # Assert 3円 ≤ 6円 + 1円 (outside the negative lookinto), by asserting here
 # that tail ≥ 6円 + 1円 + 1.
 6円?+ # Take advantage of the fact that it is guaranteed 6円 ≤ 3,円
 # meaning we don't have to use "(?(6)6円)".
 1円x
 # Note that 6円 + 1円 is 1 more than the actual number of times 8円 was
 # subtracted, which will change the 3円 result for some even values of N
 # from rounded-down to rounded-up. But for odd values of N, it simulates
 # subtracting 8円 from the last half-chunk, which is not covered in the loop
 # we did. Note that depending on the final value of 8,円 it may be ≤ 1,円 in
 # which case we'll get a rounded-down 3,円 or > 1,円 in which case we'll get
 # a rounded-up 3円.
)

Regex (PCRE+(?^=)^RME ), (削除) 123 (削除ここまで) (削除) 113 (削除ここまで) (削除) 96 (削除ここまで) 95 bytes

(?=(x*)(1円x?))(x*)(?^=((?=(2円$|))x(?^=((?^=(7円?x))(^10円|3円))*5円(x*)(?^3=9円(x*))))*1円(?^7=3円)|$)

Try it on replit.com!

This is a port of the 99 byte .NET regex that rounds down.

 # tail = N = input number
(?=
 (x*) # 1円 = floor(N / 2)
 (1円x?) # 2円 = ceil(N / 2)
)
(x*) # 3円 = guess for floor(sqrt(N*N/2))
(?^= # Atomic lookinto: tail = N
 (
 (?=(2円$|)) # 5円 = 2円 if tail == 2,円 0 otherwise;
 # Note that if tail==2,円 it means this is the last iteration
 # if N is odd – but if N is even, this iteration will fail to
 # match, as the last iteration will have already finished.
 x # tail -= 1
 (?^= # Atomic lookinto: tail = N
 # if 10円 is set: tail -= 10円; 7円 += 1;
 # X = floor((tail - 5円) / 3円); tail -= 3円*X; 7円 += X;
 # Note that in practice, 0 ≤ X ≤ 1
 (
 (?^=
 ( # 7円 = sum of the following:
 7円? # previous value of 7円 if set, 0 otherwise
 x # 1
 )
 )
 (
 ^10円 # On the first iteration, if 10円 is set, tail -= 10円
 |
 3円 # Assert tail ≥ 3円; tail -= 3円
 )
 )* # Match the above as many times as possible, minimum 0
 5円 # tail -= 5円
 (x*) # 9円 = tail = remainder = dividend % 3円
 (?^3= # Atomic lookinto: tail = 3円
 9円 # tail -= 9円
 (x*) # 10円 = tail = 3円 - 9円
 )
 )
 )*
 1円 # Assert tail ≥ 1,円 forcing the loop above to iterate 2円 times
 (?^7= # Lookinto: tail = 7円
 3円 # Assert 3円 ≤ tail, i.e. 3円 ≤ 7円
 )
|
 $ # or N == 0, in which case the output = the input; this needs to be
 # a special case because "(?^7=...)" cannot match if 7円 is unset.
)

Answer 5

JavaScript (ES6), 12 bytes

i=>i/2**.5|0

Uses a binary or to truncate the result

Try it online!

Answer 6

8087 FPU machine code, 11 bytes

Unassembled listing:

D9 E8 FLD1 ; load a 1 constant (need to make a 2)
D8 C0 FADD ST, ST(0) ; ST = 1+1 = 2 
D9 FA FSQRT ; ST = SQRT(2) 
DE F9 FDIVP ST(1), ST ; ST = N / ST 
DF 1F FISTP QWORD PTR [BX] ; *BX = ROUND(ST)
C3 RET ; return to caller

Input in ST0, as a 80-bit extended precision value, output to QWORD PTR [BX].

Floating point operations done in x87 math coprocessor hardware with 80-bit extended precision. Correctly calculates values of N up to 13043817825332782211, after which the result will exceed \2ドル^{63}-1\$ (overflowing a 64-bit signed integer return variable).

Example test program with I/O:

enter image description here

(Test program now with 64 bit I/O routines thx to suggestions from @PeterCordes)

Thanks to @PeterCordes for the suggestion take input in ST(0), saving 2 bytes.

• Peter Cordes: heh, x87 has a bunch of constants build in, including pi and log and ln(2), and log2() of e and 10, but not sqrt 2. :/ push 2 / fild wouldn't help either. Suggestion: custom calling convention: input in ST0, return in ST0. Then you just use fdivp after setting up the constant.
• Peter Cordes: Or for this integer-by-reference convention, use fidvr. Oh, but there's no m64int form of that, only 16 and 32! So that only works for int32_t. Now I see why you had to use fild to handle a qword integer. I don't think we can beat that with SSE2 in 64-bit mode; divsd is at least 4 bytes, and if you need an addressing mode it's more.
• 640KB: @PeterCordes, sure that would make sense to just do i/o using ST0 (especially since the stated platform is "8087 FPU"). Would cut 4 bytes and possibly increase the highest number of N by a little bit too (at least until the result is lte than \2ドル^{63}-1\,ドル whatever that is). Also the opcode DE F9 (FDIV) is actually FDIVP ST(1), ST so that's already good there.
• Peter Cordes: Oh wait, this relies on the caller to do the rounding to nearest integer. That's not allowed. We need frndint, or fistp to an output pointer. Input can still be an integer FP value in ST0 though.
• Peter Cordes: If you want it: How to display a 64 bit number in decimal in assembly 8086 for output, using only 8086 instructions. Or in 16-bit mode on an emulator like DOSBox, you can use div r32 (32-bit regs in 16-bit mode). Then simply adapt Print 64 bit number stored in EDX:EAX to standard out. Input is easier, e.g. (x << 3) + (x<<1) + new_digit with carry propagation across 2 or 4 limbs. Or use hex; that's still trivial for large values and you can even use SSSE3 in real mode :P

Answer 7

Java 8, 18 bytes

n->n/=Math.sqrt(2)

Limited to a maximum of \9ドル{,}223{,}372{,}036{,}854{,}775{,}807\$ (signed 64-bit integer).

Try it online.

Explanation:

n-> // Method with long as both parameter and return-type
 n/= // Divide the input by:
 Math.sqrt(2) // The square-root of 2
// The `/=` sets the divided result back to `n`, which implicitly casts the resulting double
// back to long. This saves bytes in comparison to `n->(long)(n/Math.sqrt(2))`

Java 9, (削除) 76 (削除ここまで) 74 bytes

n->n.divide(n.valueOf(2).sqrt(new java.math.MathContext(n.precision())),4)

-2 bytes thanks to @OlivierGrégoire.

Arbitrary I/O and precision.

Try it online.

Explanation:

n-> // Method with BigDecimal as both parameter and return-type
 n.divide( // Divide the input by:
 n.valueOf(2) // Push a BigDecimal with value 2
 .sqrt( // Take the square-root of that
 new java.math.MathContext(n.precision())),
 // with the same precision as the input
 4) // With rounding mode HALF_UP

• Olivier Grégoire: Use n.precision() instead of (n+"").length() to save two bytes. Also, just for the sake of clarifying the language and the API, the Java 9 solution goes the extra mile since BigDecimal is not part of the language but of the API, and the challenge speaks only about language.
• Kevin Cruijssen: @OlivierGrégoire Thanks for -2! And didn't knew that about the API. I figured all internal imports that are available in Java were fine, but external not.
• Olivier Grégoire: They are fine! No worries: it was just informative :-)

Answer 8

dc, 5 bytes

d*2/v

Try it online!

Takes input and leaves output on the stack.

dc automatically uses arbitrary-precision integers, and supports a precision of 0 decimal places by default, thus automatically "rounding". So taking the square-root of 2 will yield 1. Instead, this solution squares the input, by duplicating it and * multiplying both the items at the top of the stack, / dividing it by 2 (reverse-polish) and takes the v square root of that.

Answer 9

Jelly, 15 bytes

32:2_2:Ẹ¡:2+μƬṪ

Try it online!

An arbitrary precision Jelly answer that uses the Newton-Raphson method to find the correct answer. Uses only integer arithmetic operations so the intermediate values are all Python big ints rather than getting cast as floats which would lose precision. The integer result equates to the floor of what would be the floating point answer.

A full program that takes a (possibly negative) integer as its argument and returns an integer.

Now correctly handles inputs of 0 and 1; previously threw an error because of division of 0 by 0 being impermissible for integers.

Useful comment from @PeterCordes about efficiency of this method and some detail on Python’s big integer implementation:

Newton-Raphson converges quickly, like twice as many correct bits per iteration, given a decent first estimate. e.g. one step refines a 12-bit-precision rsqrtps(x) FP result into nearly 24-bit. (In this case apparently the original input is close enough). You only pay Python interpreter overhead per operation, not per limb (aka chunk) of a very long number; extended-precision division is not cheap but it is implemented in C on chunks of 2^30 stored in an array of 32-bit integers. (I forget if Python uses 64-bit on 64-bit machines.)

Explanation

 μƬ | Do the following as a monad until no new values seen, collecting up the intermediate values:
3 | - Original argument to program
 2 | - Squared
 :2 | - Integer divide by 2
 _2 | - Subtract current estimate squared
 Ẹ¡ | - If non-zero:
 : | - Integer divide by current estimate
 :2 | - Integer divide by 2
 + | - Add to current estimate
 Ṫ | Finally, take the tail of the list of estimates

Note Ẹ¡ is literally repeat the number of times indicated by applying the any function to current value, but it is effectively used here to mean if non-zero.

A much shorter answer that is only accurate to float precision is:

Jelly, 4 bytes

21⁄2:@

Try it online!

• Deadcode: Wow, it's incredible how fast the arbitrary precision version is. I wouldn't have guessed Python could be that fast let alone Jelly.
• Kevin Cruijssen: Out of curiosity: what is the current estimate in the very first iteration? Is this the input itself, or 0, or something else? I wonder if I can somehow port this approach into a language that only uses integers, like BrainF*ck or Whitespace. :) Another question: "until no new values seen": can this include any previous collected intermediate values, or only the most recent one (in the second case, "until the current estimate no longer changes" would be a valid synonym)?
• Nick Kennedy: @KevinCruijssen the original input, which works fine. Until no new values seen is technically correct, though for this particular problem I’m not sure whether the alternative would ever lead to oscillation between two or more values without checking.
• Peter Cordes: @Deadcode: Newton-Raphson converges quickly, like twice as many correct bits per iteration, given a decent first estimate. e.g. one step refines a 12-bit-precision rsqrtps(x) FP result into nearly 24-bit. (In this case apparently the original input is close enough). You only pay Python interpreter overhead per operation, not per limb (aka chunk) of a very long number; extended-precision division is not cheap but it is implemented in C on chunks of 2^30 stored in an array of 32-bit integers. (I forget if Python uses 64-bit on 64-bit machines.)
• Nick Kennedy: @Deadcode done.

Answer 10

05AB1E, 3 bytes

2t÷

Try it online!

-1 byte thanks to @Grimmy

Yet another port of my Keg answer for the sake of completion.

Explained

2t÷
2t # Push the square root of two
 ÷ # Integer division

🍟🍅

Still no ketchup.

• Grimmy: You can save a byte by using the built-in ÷ instead of /ï.

Answer 11

Japt, 3 bytes

z2q

Try it

z is the floor division method and q is the nth-root method, defaulting to square root when it's not passed an argument.

Answer 12

Mathematica, (削除) 17 (削除ここまで) (削除) 14 (削除ここまで) 13 bytes / (削除) 12 (削除ここまで) 7 characters

⌊#/√2⌋&

Try it online

-3 bytes because Mathematica accepts the char √, which I copied from this MathGolf answer.

-1 byte, -5 characters, as per @Mark S. suggestion, by using ⌊⌋.

For just one more byte (but 5 more characters) I can always round to the nearest integer with

Round[#/√2]&

• Deadcode: Nice, a second arbitrary-precision answer :) And first answer that rounds to the nearest.
• Mark S.: @Deadcode It doesn't round to the nearest anymore, but ⌊#/√2⌋& would save 1 byte and 5 characters.
• Deadcode: Hey, that's fine with me :) Go ahead and drop that byte... I didn't mean to confine you to sticking with one rounding method. :)

Answer 13

TI-BASIC, 5 bytes

int(Ans√(2−1

Built-ins are great.
Input is a number in Ans.
Output is what is specified in the challenge.

Explanation:

 √(2−1 ;get the square root of 1/2
 Ans ;get the input (Ans)
 ;implicit multiplication
int( ;truncate
 ;implicit print of Ans

---

Note: TI-BASIC is a tokenized language. Character count does not equal byte count.

• Deadcode: Which TI calculator is this for? On TI-85, it's int Ans√2−¹, which is still 5 bytes. On TI-89 and TI-92, it's ans(1), not Ans. Edit: Ah, TI-83.
• absoluteAquarian: @Deadcode the general consensus, as far as I am aware, is that submissions are for the TI-83 and TI-84 series of calculators (correct me if i'm wrong). Specific versions are specified in the title of the submission when needed.

Answer 14

C (gcc) -lm, ^{(削除) 23 (削除ここまで) \$\cdots\$ (削除) 50 (削除ここまで)} 27 bytes

Saved 6 bytes thanks to a'_'!!!
Added 38 bytes to fix type error kindly pointed out by S.S. Anne.
Saved 3 bytes thanks to rtpax!!!
Saved a whopping 23 bytes thanks to an idea from ErikF!!!

#define f(n)ceil(n/sqrt(2))

Try it online!

Answer 15

Brainlove, (削除) 73 (削除ここまで) (削除) 70 (削除ここまで) (削除) 74 (削除ここまで) (削除) 61 (削除ここまで) 35 bytes

Because brainfuck is too hard

-3 bytes by myself, rearranging the memory and fixing some bugs

+4 bytes by myself, fixing an error

-13 bytes by myself

-26 bytes by myself, actually using the Brainlove features properly.

[$[->+<]!-]+>[<$[>[-~]<-]!++>>+<]>-

Try it online

First computes the sum $$ S = \sum_{i=1}^n i = \frac{n(n+1)}{2} $$ and then the square root by finding the largest n for which $$ \sum_{i=1}^n 2i-1 = n^2 < S $$ The error is always $$ E= \sqrt{\frac{n(n+1)}{2}}- \frac{n}{\sqrt{2}} < \sqrt{\frac{(n+\frac{1}{2})^2}{2}} - \frac{n}{\sqrt{2}} = \frac{n+\frac{1}{2}-n}{\sqrt{2}} = \frac{\sqrt{2}}{4} $$ and it is counteracted by rounding down. It is not very golfed, since I'm not very familiar with golfing in Brainlove/brainfuck, any improvements welcome (or a bf version). It should theoretically work for unbound cells (arbitrary precision), but I didn't have an option to test that. The input and output are on position 0 and 2 on tape, respectively.

• Deadcode: Nice choice of language :-) So, I guess this takes its input from the contents of memory address 1, given by the number of + in the header between > and <. But it looks like it can't handle input outside the range of 2 to 13 – it returns non-decimal output unless the input is in that range. Could you fix this, please? The output doesn't necessarily have to be in decimal; it can be in unary if you like. But it has to be able to handle input as low as 0.
• Kosatka: @Deadcode The fact it doesn't work for numbers above 13 is due to the way I convert the result to printable number for testing (since 14/sqrt(2) is approximately 10), and which isn't part of the actual code. The code only puts the result in address 5. I will add another link with output in unary, that will fix this issue, but it still won't go higher than around 23, because of the memory bound cells. As for the errors at 0 and 1, I have no idea what causes them, but I will try to look into that. Thanks for the comment.
• Deadcode: Yes I know, I specifically tried 14 because it's the first input whose output needs to be two digits. I didn't know about the 23 limit. I hate to say it, but if it can't handle inputs up to the language's native type's maximum, which I think in this case is 255, that's another thing making it not valid. Could you please fix that too?
• Kosatka: @Deadcode No I can't, since during this algorithm, I store a number around n^2/2 in memory during computation. If there was a flag to enable arbitrarily large numbers (there isn't), it would work (but be terribly slow). Since this is your question, if you think this isn't valid I can (un) happily delete this answer.
• Deadcode: Note that the test harness (header and footer) doesn't need to be golfed, so there's no good reason not to just include only one version of it that can print the full range 0-255 in decimal. I wrote a harness from scratch for you that does this (Try it online!) Same applies for taking input in multi-digit decimal, but I haven't written one for that.

Answer 16

APL (Dyalog Extended), 5 bytes ^SBCS

Full program. Prompts stdin for zero or more numbers.

⌈⎕÷√2

Try it online!

⌈ ceiling of

⎕ console input

÷ divided by

√ the square root of

2 two

Answer 17

Pyth, 6 bytes

The division auto-casts the number to a decimal!? (In seriousness, is there a square root function in Pyth?)

/Q@2 2

Try it online!

Explanation

 @2 2 to the power of
 2 1/2 (effectively calculates math.sqrt(2))
/Q Divide the (evaluated) input by that number

• hakr14: There is not a square root function in Pyth, @b2 is all we have. However, .n2 is a constant that returns sqrt(2), so that can save you a byte.

Answer 18

Whitespace, (削除) 122 (削除ここまで) 103 bytes

[S S T T N
_Push_-1][S S S N
_Push_0][S N
S _Dupe_0][T N
T T _Read_STDIN_as_integer][T T T _Retrieve_input][S N
S _Dupe_input][N
T S T N
_If_0_Jump_to_Label_ZERO][N
S S N
_Create_Label_LOOP][S N
T _Swap_top_two][S S S T N
_Push_1][T S S S _Add][S N
T _Swap_top_two][S N
S _Dupe_input][S N
S _Dupe_input][T S S N
_Multiply][S T S S T S N
_Copy_0-based_2nd_n][S N
S _Dupe_n][T S S N
_Multiply][S S S T S N
_Push_2][T S S N
_Multiply][S N
T _Swap_top_two][T S S T _Subtract][N
T T N
_If_neg_Jump_to_Label_LOOP][S N
T _Swap_top_two][N
S S T N
_Create_Label_ZERO][T N
S T _Print_as_integer]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

Try it online (with raw spaces, tabs and new-lines only).

Output is rounded up.

Inspired by the following mentioned in @Deadcode's Regex answer:

For input \$N\$, we want to calculate \$M=\left\lfloor\frac{N}{\sqrt2}\right\rfloor\$. So we want the largest \$M\$ such that \2ドルM^2<N^2\$.

EDIT: My program now implements \2ドルM^2\leq N^2\$ instead to save 19 bytes (\$\lt\$ vs \$\leq\$ is irrelevant, otherwise \$\sqrt{2}\$ would be rational). Although I see @Deadcode edited his Regex answer and he's actually using \$\leq\$ as well.

Explanation in pseudo-code:

Integer n = -1
Integer input = STDIN as integer
Start LOOP:
 n = n + 1
 If(n*n*2 - input*input < 0):
 Go to next iteration of LOOP
 Print n
 (exit program with error since no exit is defined)

Example program flow (input 4):

Command Explanation Stack Heap STDIN STDOUT STDERR
SSTTN Push -1 [-1]
SSSN Push 0 [-1,0]
SNS Duplicate 0 [-1,0,0]
TNTT Read STDIN as integer [-1,0] [{0:4}] 4
TTT Retrieve from heap #0 [-1,4] [{0:4}]
SNS Duplicate 4 [-1,4,4] [{0:4}]
NTSTN If 0: Jump to Label ZERO [-1,4,4] [{0:4}]
 (^ workaround for input=0, since it would otherwise output -1)
NSSSN Create Label LOOP [-1,4] [{0:4}]
SNT Swap top two [4,-1] [{0:4}]
SSSTN Push 1 [4,-1,1] [{0:4}]
TSSS Add top two: -1+1 [4,0] [{0:4}]
SNT Swap top two [0,4] [{0:4}]
SNS Duplicate 4 [0,4,4] [{0:4}]
SNS Duplicate 4 [0,4,4,4] [{0:4}]
TSSN Multiply top two: 4*4 [0,4,16] [{0:4}]
STSSTSN Copy 0-based 2nd [0,4,16,0] [{0:4}]
SNS Duplicate 0 [0,4,16,0,0] [{0:4}]
TSSN Multiply top two: 0*0 [0,4,16,0] [{0:4}]
SSSTSN Push 2 [0,4,16,0,2] [{0:4}]
TSSN Multiply top two: 0*2 [0,4,16,0] [{0:4}]
SNT Swap top two [0,4,0,16] [{0:4}]
TSST Subtract top two: 0-16 [0,4,-16] [{0:4}]
NTTN If neg: Jump to label LOOP [0,4] [{0:4}]
SNT Swap top two [4,0] [{0:4}]
SSSTN Push 1 [4,0,1] [{0:4}]
TSSS Add top two: 0+1 [4,1] [{0:4}]
SNT Swap top two [1,4] [{0:4}]
SNS Duplicate 4 [1,4,4] [{0:4}]
SNS Duplicate 4 [1,4,4,4] [{0:4}]
TSSN Multiply top two: 4*4 [1,4,16] [{0:4}]
STSSTSN Copy 0-based 2nd [1,4,16,1] [{0:4}]
SNS Duplicate 1 [1,4,16,1,1] [{0:4}]
TSSN Multiply top two: 1*1 [1,4,16,1] [{0:4}]
SSSTSN Push 2 [1,4,16,1,2] [{0:4}]
TSSN Multiply top two: 1*2 [1,4,16,2] [{0:4}]
SNT Swap top two [1,4,2,16] [{0:4}]
TSST Subtract top two: 2-16 [1,4,-14] [{0:4}]
NTTN If neg: Jump to label LOOP [1,4] [{0:4}]
SNT Swap top two [4,1] [{0:4}]
SSSTN Push 1 [4,1,1] [{0:4}]
TSSS Add top two: 1+1 [4,2] [{0:4}]
SNT Swap top two [2,4] [{0:4}]
SNS Duplicate 4 [2,4,4] [{0:4}]
SNS Duplicate 4 [2,4,4,4] [{0:4}]
TSSN Multiply top two: 4*4 [2,4,16] [{0:4}]
STSSTSN Copy 0-based 2nd [2,4,16,2] [{0:4}]
SNS Duplicate 2 [2,4,16,2,2] [{0:4}]
TSSN Multiply top two: 2*2 [2,4,16,4] [{0:4}]
SSSTSN Push 2 [2,4,16,4,2] [{0:4}]
TSSN Multiply top two: 4*2 [2,4,16,8] [{0:4}]
SNT Swap top two [2,4,8,16] [{0:4}]
TSST Subtract top two: 8-16 [2,4,-8] [{0:4}]
NTTN If neg: Jump to label LOOP [2,4] [{0:4}]
SNT Swap top two [4,2] [{0:4}]
SSSTN Push 1 [4,2,1] [{0:4}]
TSSS Add top two: 2+1 [4,3] [{0:4}]
SNT Swap top two [3,4] [{0:4}]
SNS Duplicate 4 [3,4,4] [{0:4}]
SNS Duplicate 4 [3,4,4,4] [{0:4}]
TSSN Multiply top two: 4*4 [3,4,16] [{0:4}]
STSSTSN Copy 0-based 2nd [3,4,16,3] [{0:4}]
SNS Duplicate 3 [3,4,16,3,3] [{0:4}]
TSSN Multiply top two: 3*3 [3,4,16,9] [{0:4}]
SSSTSN Push 2 [3,4,16,9,2] [{0:4}]
TSSN Multiply top two: 9*2 [3,4,16,18] [{0:4}]
SNT Swap top two [3,4,18,16] [{0:4}]
TSST Subtract top two: 18-16 [3,4,2] [{0:4}]
NTTN If neg: Jump to label LOOP [3,4] [{0:4}]
SNT Swap top two [4,3] [{0:4}]
NSSTN Create Label ZERO [4,3] [{0:4}]
TNST Print as integer to STDOUT [4] [{0:4}] 3
 error

Program stops with an error because no exit is defined.

• Kevin Cruijssen: @Deadcode Primarily because I would have to do an \$-1\$ after we've found \$N+1\$. So where your answer outputs \$N\,ドル mine outputs \$N+1\$ (excluding edge case \0ドル\$).
• Kevin Cruijssen: @Deadcode Also, Whitespace only has labels and jumps to labels to create loops and if-statements. The only jumps available are: jump unconditional; jump if 0; and jump it negative. Jump if positive is unfortunately not available (not really necessary, since one could use \$×-1\$ and then use the jump if neg. as alternative). Because of this I currently check whether \$(N+1)^2 - 2M^2 < 0\$ is truthy. If it is: continue the loop; if not: print \$N+1\$.
• Deadcode: Wow, very cool that the same (or very similar) algorithm is quite fitting in both regex and Whitespace. And ≤ vs. < is of course purely a golf optimization :) If it made a difference which you used, sqrt(2) would be rational. FWIW I mis-typed the LaTeX explanation – it really is ≤ in the regex. Oh, and if this is using the same algorithm as the regex, how come this rounds up and the regex rounds down? [Edit: Oops, rewrote this comment not realizing you'd already replied to it.]
• Kevin Cruijssen: @Deadcode Ah, of course, \$<\$ vs \$\leq\$ is irrelevant, otherwise \$\sqrt{2}\$ would have been rational. Edited my answer. \$<\$ certainly saves bytes in my answer though, since I'd otherwise have to add a Duplicate, Jump if 0, and additional label which discards the duplicate before continuing with the loop (what I had in my initial 122 byter).

Answer 19

C (gcc), Precision limited by built-in types, (削除) 42 (削除ここまで) 36 bytes

__int128 f(__int128 n){n/=sqrtl(2);}

Try it online!

Floor for the most part but the last output is ceiling.

Uses GCC's __int128 type: shorter in text length than unsigned long, can represent every value in unsigned long, and determined to not be a builtin type. Stay tuned for 6-8 weeks to get arbitrary precision.

-6 bytes thanks to Peter Cordes!

Answer 20

wx, 3 bytes

It's W, with just one instruction added: square root. Turns out that this is very useful! (P.S. the built-in was added before the challenge.)

2Q/

Explanation

 2Q % Find the square root of 2
a / % Divide the input by it
 % If one operand is an integer,
 % the program will automatically
 % try to trunctuate to an integer

Answer 21

PHP, 17 bytes

<?=$argn/2**.5|0;

Try it online!

Uses @Niphram's truncate method (which in PHP also has the ability to convert the float to an int)

I know it's trendy to say PHP is to be hated, but I kinda came to like its oddities, and it gives me a chance to add an original answer

EDIT: saved 4 bytes using <?= php tag (no need to echo)

EDIT2: basically it's just a port of @Niphram's answer now

• Kaddath: @640KB Ok it's noted, fixed it. Still a bit new to golfing; Thanks
• 640KB: I should have started with welcome to CGCC! The rule of thumb is that a submission doesn't have to work on all common configurations of platform but it does have to work on one. The reason omission of an opening tag can be permitted would be if your script could run using the -r command line option (php -r "echo 'hi world';"). Unless specified otherwise the Default I/O rules govern what's allowed.
• 640KB: Oh, and don't let people get you down about PHP. It is used on almost 80% of all websites utilizing server-side scripting, so it can't be that bad. :)

Answer 22

Canvas, 4 bytes

2√n┐

Try it here!

Answer 23

Dart, 33 bytes

import'dart:math';f(a)=>a~/sqrt2;

Try it online!

• naffetS: Welcome to Code Golf!

Answer 24

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!

Answer 25

Keg, 6 bytes

211⁄2Ë/Z

Try it online!

This defines the function f as:

• Taking a single parameter, then
• Calculating the square root of 2 by raising it to the power of 0.5, then
• Dividing the parameter by root 2, then
• Casting the result to an integer (truncating / flooring the result) and returning it.

The footer is to define the test cases in a nice way.

Explained in a usual way

211⁄2Ë/Z
2 # Push 2 to the stack
 11⁄2 # Push 1 and halve it to get 0.5
 Ë # Push 2 ** 0.5 (x ** 1/2 = sqrt(x))
 /Z # Divide and cast to integer (floor) 

🍟🍅

Sorry, we're all out of ketchup. You'll have to squeeze your own.

• S.S. Anne: What does that last comment mean?
• lyxal: @S.S.Anne, it's a reference to how the author asked for an explanation here

Answer 26

Haskell, 20 bytes

f n=round$n/(sqrt 2)

Try it online

• Potato44: This doesn't match the requirements. The question says to use at least,the largest fixed size (unsigned) integer type. That type happens to be Word64 (or Word on a 64-bit system). The current answer can't even accept integers as input, only floating point values. It also gets the incorrect answer due to precision loss even when you allow a Double as input with Word ouput. Try it online!
• Potato44: Whoops, my last comment comment uses a number too big for a 64 bit Word, but here is one demonstarting the accuracy problem properly Try it online!
• RGS: @Potato44 ty for your feedback! Since you have to import Data.Word, doesn't it mean that I can get away without having to support it?
• Potato44: Word is part of the prelude, I just had Data.Word imported because I was using Word64, but forgot to remove the import. Even if it was not the case that Word was in the prelude, my interpretation is you would still have to import it as it is part of the standard library. But @Deadcode would be better at ruling on that. Also you can write functions that accept Word64 without importing Data.Word if you make them polymorphic enough.
• RGS: @Potato44 in any case I can mark my answer as non-competing. Thanks for teaching me something

Answer 27

Python 3, (削除) 22 (削除ここまで) 21 bytes

lambda x:int(x/2**.5)

Try it online!

-1 byte thanks to @RGS. Thanks for reminding me that implicit decimals exist

Just a port of my Keg answer. Nothing special here.

• RGS: Save 1 byte by writing .5 instead of 0.5, no?
• RGS: c.f. this Python 3 answer (19 bytes, rounds down): codegolf.stackexchange.com/a/198435/75323

Answer 28

MathGolf, 4 bytes

2√/i

Try it online.

Explanation:

2√ # Take the square-root of 2
 / # Divide the (implicit) input-integer by this
 i # Cast it to an integer, truncating any decimal values
 # (after which the entire stack joined together is output implicitly as result)

• RGS: I copied your √ character to use in my Mathematica answer. TIO counts that character as 3 bytes, so I should do the same, right? If so, why would you get to count it as 1? I'm new to this so an explanation would be great ^^
• Kevin Cruijssen: Hi @RGS, welcome to CGCC! :) The language I use (MathGolf), has just like most other golfing languages (i.e. 05AB1E, Jelly, Charcoal, etc.) a custom codepage (which I usually link in the bytes part of the title). These codepages will contain 256 characters which are encoded as 1 byte each. That's why the √ is 1 byte in my answer, but 3 bytes in Mathematica, which uses UTF-8 encoding by default (I think, most languages use UTF-8, but I never used Mathematica, so I'm not 100% sure what the default codepage is).
• Jo King: @RGS Mathgolf, like many golfing languages, uses a SBCS (Single Byte Code Set), so all 256 characters used in the language count as one byte. Mathematica presumably uses UTF-8, where that character is three bytes
• Kevin Cruijssen: @RGS Here also an example in a comment of an 05AB1E (legacy) answer of mine, where the creator of the 05AB1E language explains how the three hexadecimal bytes using 05AB1E encoding can be verified with the --osabie flag, after someone asked a similar question as yours. :)
• Kevin Cruijssen: @RGS Tbh, I'm not sure, but I think you'd have to prove each of them can be stored in a single byte on local disk using your encoding. Although I never created a language, so I honestly don't know. Usually those who create a golfing language add a small section on their github README page to explain how to encode it in a single byte each. I.e. the Usage/Compiling section of MathGolf or the Execution section of 05AB1E.

Answer 29

CJam, 9 bytes

CJam has mQ, but unfortunately it trunctuates to an integer ... Another port of Lyxal's answer.

q~2 .5#/i

Try it online!

Explanation

q~ e# Take input & evaluate
 2 e# Take 2 to the power of ...
 .5# e# ... 0.5 (equal to square root)
 / e# Divide the input by it
 i e# Convert to integer

Answer 30

PowerShell, 67 bytes

param([uint64]$n)($n/[math]::Sqrt(2)).ToString("G17")-replace'\..*'

Try it online!

.NET (and thus, by extension, PowerShell) doesn't have a BigDecimal, so we're limited to Double or Decimal. However, the [math]::Sqrt() function only works on Double, so there we're stuck. So far, so standard. We then specify precision with G17, which successfully round-trips to give us 17 digits of precision on our Double, so we can pass everything but the last three test cases. We finish that off with a simple truncation -replace.