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

Answer 1

Regex (ECMAScript+(?*)), 1169 929 887 853 849 bytes

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 \$2M^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 \$2M^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.

Note that there is one departure from pure code golf in this version of the regex. 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. This only involved 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.

(?=(x(x*))(x)*(?=\1*$)\2+$)(?=(x(\2\3))+(x?(x*)))(?=\6(x(x*))(?=\8*$)\5\9*$)(?=.*(?=(?=\6*$)\6\7+$)(x*?)(?=\4*$)(x?(x*))(?=\11*$)((?=\5+$)\5\12*$|$\11))(?=.*(?=(?=\6*$)(?=\8*$)(?=\6\9+$)\8\7+$|$\6)(x*?)(?=\4*$)(x?(x*))(?=\15*$)((?=\5+$)\5\16*$|$\15))(?=.*(?=\14\14\11$)(x*?)(?=\4*$)(x?(x*))(?=\19*$)((?=\5+$)\5\20*$|$\19))(?*.*?(?=((?=\4*(x?(x*)))\23(x(x*))(?=\25*$)\5\26*$)))(?=.*(?=\25*$)(\25\26+$))(?=.*(?=(?=\23*$)\23\24+$)(x*?)(?=\4*$)(x?(x*))(?=\29*$)((?=\5+$)\5\30*$|$\29))(?=.*(?=(?=\23*$)(?=\25*$)(?=\23\26+$)\25\24+$|$\23)(x*?)(?=\4*$)(x?(x*))(?=\33*$)((?=\5+$)\5\34*$|$\33))(?=.*(?=\32\32\29$)(x*?)(?=\4*$)(x?(x*))(?=\37*$)((?=\5+$)\5\38*$|$\37))(?=.*(?=\28\28)(?=\4*(x*))(\5(x)|))(?=.*(?=\36\36\42)(?=\4*(x*))(\5(x)|))(?=(?=(.*)\15\15\19(?=\8*$)\8\9+$)\46(x+|(?=.*(?!\18)\43|(?!.*(?!\40)\10).*(?=\18$)\43$))(\27\33\33\37){2}\45$)\22|x\B|

Try it on repl.it

This regex is on GitHub with a full version history.

# Giving 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
  (x)*(?=\1*$)           # \3 = tool to round up instead of down
  \2+$
)

# Step 1: Calculate N*N in base ceil(sqrt(N))

(?=(x(\2\3))+(x?(x*)))   # \4 = \1 + \3 = ceil(sqrt(N)), the number base to work in; \5 = \4-1; \6 = N % \4; \7 = \6-1, or 0 if \6==0
(?=
  \6
  (x(x*))                # \8 = floor(N / \4); \9 = \8-1
  (?=\8*$)               # we can skip the test for divisibility by \5 because it's guaranteed that \5 <= \8
  \5\9*$
)
(?=
  .*
  (?=
    (?=\6*$)             # tail = \6 * \6
    \6\7+$
  )
  (x*?)(?=\4*$)          # \10 =       (\6 * \6) % \4, the base-\4 digit in place 0 of the result for N*N
  (x?(x*))               # \11 = floor((\6 * \6) / \4); \12 = \11-1, or 0 if \11==0
  (?=\11*$)
  (
    (?=\5+$)
    \5\12*$
  |
    $\11                 # must make a special case for \11==0, because \5 is nonzero
  )
)
(?=
  .*
  (?=
    (?=\6*$)             # tail = \6 * \8; must do symmetric multiplication, because \6 is occasionally 1 larger than \8
    (?=\8*$)
    (?=\6\9+$)
      \8\7+$
  |
    $\6                  # must make a special case for \6==0, because \8 might not be 0
  )
  (x*?)(?=\4*$)          # \14 =       (\6 * \8) % \4
  (x?(x*))               # \15 = floor((\6 * \8) / \4); \16 = \15-1, or 0 if \15==0
  (?=\15*$)
  (
    (?=\5+$)
    \5\16*$
  |
    $\15                 # must make a special case for \15==0, because \5 is nonzero
  )
)
(?=
  .*(?=\14\14\11$)       # tail =       2 * \14 + \11
  (x*?)(?=\4*$)          # \18 =       (2 * \14 + \11) % \4, the base-\4 digit in place 1 of the result for N*N
  (x?(x*))               # \19 = floor((2 * \14 + \11) / \4); \20 = \19-1, or 0 if \19==0
  (?=\19*$)
  (
    (?=\5+$)
    \5\20*$
  |
    $\19                 # must make a special case for \19==0, because \5 is nonzero
  )
)                        # {\8*\8 + 2*\15 + \19} = the base-\4 digit in place 2 of the result for N*N, which is allowed to exceed \4 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 \4
(?*
  .*?                    # Determine value of M with backtracking, starting with largest values first
  (?=
    (                    # \22 =       M
      (?=\4*(x?(x*)))\23 # \23 =       M % \4; \24 = \23-1, or 0 if \23==0
      (x(x*))            # \25 = floor(M / \4); \26 = \25-1
      (?=\25*$)          # we can skip the test for divisibility by \5, but I'm not sure why; TODO: figure out why this is
      \5\26*$
    )
  )
)
(?=
  .*
  (?=\25*$)
  (\25\26+$)             # \27 = \25 * \25
)
(?=
  .*
  (?=
    (?=\23*$)            # tail = \23 * \23
    \23\24+$
  )
  (x*?)(?=\4*$)          # \28 =       (\23 * \23) % \4, the base-\4 digit in place 0 of the result for M*M
  (x?(x*))               # \29 = floor((\23 * \23) / \4); \30 = \29-1, or 0 if \29==0
  (?=\29*$)
  (
    (?=\5+$)
    \5\30*$
  |
    $\29                 # must make a special case for \29==0, because \5 is nonzero
  )
)
(?=
  .*
  (?=
    (?=\23*$)            # tail = \23 * \25; must do symmetric multiplication, because \23 is occasionally 1 larger than \25
    (?=\25*$)
    (?=\23\26+$)
      \25\24+$
  |
    $\23                 # must make a special case for \23==0, because \25 might not be 0
  )
  (x*?)(?=\4*$)          # \32 =       (\23 * \25) % \4
  (x?(x*))               # \33 = floor((\23 * \25) / \4); \34 = \33-1, or 0 if \33==0
  (?=\33*$)
  (
    (?=\5+$)
    \5\34*$
  |
    $\33                 # must make a special case for \33==0, because \5 is nonzero
  )
)
(?=
  .*(?=\32\32\29$)       # tail =       2 * \32 + \29
  (x*?)(?=\4*$)          # \36 =       (2 * \32 + \29) % \4, the base-\4 digit in place 1 of the result for M*M
  (x?(x*))               # \37 = floor((2 * \32 + \29) / \4); \38 = \37-1, or 0 if \37==0
  (?=\37*$)
  (
    (?=\5+$)
    \5\38*$
  |
    $\37                 # must make a special case for \37==0, because \5 is nonzero
  )
)                        # {\27 + 2*\33 + \37} = the base-\4 digit in place 2 of the result for M*M, which is allowed to exceed \4 and will always do so

# Step 2b: Calculate 2*M*M in base \4
(?=
  .*
  (?=\28\28)             # tail =       2*\28
  (?=\4*(x*))            # \40 =       (2*\28) % \4, the base-\4 digit in place 0 of the result for 2*M*M
  (\5(x)|)               # \42 = floor((2*\28) / \4) == +1 carry if {2*\28} does not fit in a base \4 digit
)
(?=
  .*
  (?=\36\36\42)          # tail =       2*\36 + \42
  (?=\4*(x*))            # \43 =       (2*\36 + \42) % \4, the base-\4 digit in place 1 of the result for 2*M*M
  (\5(x)|)               # \45 = floor((2*\36 + \42) / \4) == +1 carry if {2*\36 + \42} does not fit in a base \4 digit
)                        # 2*(\27 + 2*\33 + \37) + \45 = the base-\4 digit in place 2 of the result for 2*M*M, which is allowed to exceed \4 and will always do so

# Step 2c: Require that 2*M*M <= N*N

(?=
  (?=
    (.*)                 # \46
    \15\15\19
    (?=\8*$)             # tail = \8 * \8
    \8\9+$
  )
  \46                    # tail = {\8*\8 + 2*\15 + \19}; we can do this unconditionally because our digits in place 2 are always greater than those in places 0..1
  (
    x+
  |
    (?=
      .*(?!\18)\43       # \43 < \18
    |
      (?!.*(?!\40)\10)   # \40 <= \10
      .*(?=\18$)\43$     # \43 == \18
    )
  )
  (\27\33\33\37){2}\45$  # 2*(\27 + 2*\33 + \37) + \45
)

\22

|x\B|                    # handle inputs in the domain ^x{0,2}$

---

Regex (ECMAScript 2018), 861 bytes

This is a direct port of the 849 byte molecular lookahead version, using variable length lookbehind.

(?=(x(x*))(x)*(?=\1*$)\2+$)(?=(x(\2\3))+(x?(x*)))(?=\6(x(x*))(?=\8*$)\5\9*$)(?=.*(?=(?=\6*$)\6\7+$)(x*?)(?=\4*$)(x?(x*))(?=\11*$)((?=\5+$)\5\12*$|$\11))(?=.*(?=(?=\6*$)(?=\8*$)(?=\6\9+$)\8\7+$|$\6)(x*?)(?=\4*$)(x?(x*))(?=\15*$)((?=\5+$)\5\16*$|$\15))(?=.*(?=\14\14\11$)(x*?)(?=\4*$)(x?(x*))(?=\19*$)((?=\5+$)\5\20*$|$\19))(?=.*?(?=((?=\4*(x?(x*)))\23(x(x*))(?=\25*$)\5\26*$))(?<=(?=(?=.*(?=\25*$)(\25\26+$))(?=.*(?=(?=\23*$)\23\24+$)(x*?)(?=\4*$)(x?(x*))(?=\29*$)((?=\5+$)\5\30*$|$\29))(?=.*(?=(?=\23*$)(?=\25*$)(?=\23\26+$)\25\24+$|$\23)(x*?)(?=\4*$)(x?(x*))(?=\33*$)((?=\5+$)\5\34*$|$\33))(?=.*(?=\32\32\29$)(x*?)(?=\4*$)(x?(x*))(?=\37*$)((?=\5+$)\5\38*$|$\37))(?=.*(?=\28\28)(?=\4*(x*))(\5(x)|))(?=.*(?=\36\36\42)(?=\4*(x*))(\5(x)|))(?=(?=(.*)\15\15\19(?=\8*$)\8\9+$)\46(x+|(?=.*(?!\18)\43|(?!.*(?!\40)\10).*(?=\18$)\43$))(\27\33\33\37){2}\45$))^.*))\22|x\B|

Try it online!

This regex is on GitHub.

# Giving 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
  (x)*(?=\1*$)           # \3 = tool to round up instead of down
  \2+$
)

# Step 1: Calculate N*N in base ceil(sqrt(N))

(?=(x(\2\3))+(x?(x*)))   # \4 = \1 + \3 = ceil(sqrt(N)), the number base to work in; \5 = \4-1; \6 = N % \4; \7 = \6-1, or 0 if \6==0
(?=
  \6
  (x(x*))                # \8 = floor(N / \4); \9 = \8-1
  (?=\8*$)               # we can skip the test for divisibility by \5 because it's guaranteed that \5 <= \8
  \5\9*$
)
(?=
  .*
  (?=
    (?=\6*$)             # tail = \6 * \6
    \6\7+$
  )
  (x*?)(?=\4*$)          # \10 =       (\6 * \6) % \4, the base-\4 digit in place 0 of the result for N*N
  (x?(x*))               # \11 = floor((\6 * \6) / \4); \12 = \11-1, or 0 if \11==0
  (?=\11*$)
  (
    (?=\5+$)
    \5\12*$
  |
    $\11                 # must make a special case for \11==0, because \5 is nonzero
  )
)
(?=
  .*
  (?=
    (?=\6*$)             # tail = \6 * \8; must do symmetric multiplication, because \6 is occasionally 1 larger than \8
    (?=\8*$)
    (?=\6\9+$)
      \8\7+$
  |
    $\6                  # must make a special case for \6==0, because \8 might not be 0
  )
  (x*?)(?=\4*$)          # \14 =       (\6 * \8) % \4
  (x?(x*))               # \15 = floor((\6 * \8) / \4); \16 = \15-1, or 0 if \15==0
  (?=\15*$)
  (
    (?=\5+$)
    \5\16*$
  |
    $\15                 # must make a special case for \15==0, because \5 is nonzero
  )
)
(?=
  .*(?=\14\14\11$)       # tail =       2 * \14 + \11
  (x*?)(?=\4*$)          # \18 =       (2 * \14 + \11) % \4, the base-\4 digit in place 1 of the result for N*N
  (x?(x*))               # \19 = floor((2 * \14 + \11) / \4); \20 = \19-1, or 0 if \19==0
  (?=\19*$)
  (
    (?=\5+$)
    \5\20*$
  |
    $\19                 # must make a special case for \19==0, because \5 is nonzero
  )
)                              # {\8*\8 + 2*\15 + \19} = the base-\4 digit in place 2 of the result for N*N, which is allowed to exceed \4 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 \4
(?=
  .*?                    # Determine value of M with backtracking, starting with largest values first
  (?=
    (                    # \22 =       M
      (?=\4*(x?(x*)))\23 # \23 =       M % \4; \24 = \23-1, or 0 if \23==0
      (x(x*))            # \25 = floor(M / \4); \26 = \25-1
      (?=\25*$)          # we can skip the test for divisibility by \5, but I'm not sure why; TODO: figure out why this is
      \5\26*$
    )
  )
  (?<=                   # emulate molecular lookahead for the above expressions
    (?=
      (?=
        .*
        (?=\25*$)
        (\25\26+$)       # \27 = \25 * \25
      )
      (?=
        .*
        (?=
          (?=\23*$)      # tail = \23 * \23
          \23\24+$
        )
        (x*?)(?=\4*$)    # \28 =       (\23 * \23) % \4, the base-\4 digit in place 0 of the result for M*M
        (x?(x*))         # \29 = floor((\23 * \23) / \4); \30 = \29-1, or 0 if \29==0
        (?=\29*$)
        (
          (?=\5+$)
          \5\30*$
        |
          $\29           # must make a special case for \29==0, because \5 is nonzero
        )
      )
      (?=
        .*
        (?=
          (?=\23*$)      # tail = \23 * \25; must do symmetric multiplication, because \23 is occasionally 1 larger than \25
          (?=\25*$)
          (?=\23\26+$)
            \25\24+$
        |
          $\23           # must make a special case for \23==0, because \25 might not be 0
        )
        (x*?)(?=\4*$)    # \32 =       (\23 * \25) % \4
        (x?(x*))         # \33 = floor((\23 * \25) / \4); \34 = \33-1, or 0 if \33==0
        (?=\33*$)
        (
          (?=\5+$)
          \5\34*$
        |
          $\33           # must make a special case for \33==0, because \5 is nonzero
        )
      )
      (?=
        .*(?=\32\32\29$) # tail =       2 * \32 + \29
        (x*?)(?=\4*$)    # \36 =       (2 * \32 + \29) % \4, the base-\4 digit in place 1 of the result for M*M
        (x?(x*))         # \37 = floor((2 * \32 + \29) / \4); \38 = \37-1, or 0 if \37==0
        (?=\37*$)
        (
          (?=\5+$)
          \5\38*$
        |
          $\37           # must make a special case for \37==0, because \5 is nonzero
        )
      )                  # {\27 + 2*\33 + \37} = the base-\4 digit in place 2 of the result for M*M, which is allowed to exceed \4 and will always do so

      # Step 2b: Calculate 2*M*M in base \4
      (?=
        .*
        (?=\28\28)       # tail =       2*\28
        (?=\4*(x*))      # \40 =       (2*\28) % \4, the base-\4 digit in place 0 of the result for 2*M*M
        (\5(x)|)         # \42 = floor((2*\28) / \4) == +1 carry if {2*\28} does not fit in a base \4 digit
      )
      (?=
        .*
        (?=\36\36\42)    # tail =       2*\36 + \42
        (?=\4*(x*))      # \43 =       (2*\36 + \42) % \4, the base-\4 digit in place 1 of the result for 2*M*M
        (\5(x)|)         # \45 = floor((2*\36 + \42) / \4) == +1 carry if {2*\36 + \42} does not fit in a base \4 digit
      )                  # 2*(\27 + 2*\33 + \37) + \45 = the base-\4 digit in place 2 of the result for 2*M*M, which is allowed to exceed \4 and will always do so

      # Step 2c: Require that 2*M*M <= N*N

      (?=
        (?=
          (.*)           # \46
          \15\15\19
          (?=\8*$)       # tail = \8 * \8
          \8\9+$
        )
        \46              # tail = {\8*\8 + 2*\15 + \19}; we can do this unconditionally because our digits in place 2 are always greater than those in places 0..1
        (
          x+
        |
          (?=
            .*(?!\18)\43     # \43 < \18
          |
            (?!.*(?!\40)\10) # \40 <= \10
            .*(?=\18$)\43$   # \43 == \18
          )
        )
        (\27\33\33\37){2}\45$  # 2*(\27 + 2*\33 + \37) + \45
      )
    )
    ^.*                  # emulate molecular lookahead
  )
)
\22
|x\B|                    # handle inputs in the domain ^x{0,2}$

---

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.

Answer 2

Scratch 3.0, 7 blocks/62 bytes

Try it online Scratch!

As SB Syntax:

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

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

Answer 3

Python 3, 19 17 bytes

A different python answer

lambda x:x//2**.5

-2 bytes thanks to @Mukundan

try it online

Answer 4

JavaScript (ES6), 12 bytes

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

Uses a binary or to truncate the result

Try it online!

Answer 5

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:

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

Answer 6

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

Answer 7

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.

Answer 8

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

Answer 9

Jelly, 15 bytes

³²: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:
³                | - Original argument to program
 ²               | - Squared
  :2             | - Integer divide by 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

2½:@

Try it online!

Answer 10

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 11

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 12

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 13

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

Answer 14

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 15

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

Answer 16

C (gcc), ^{23 \$\cdots\$ 53} 50 bytes

typedef unsigned long long L;L f(L x){x/=sqrt(2);}

Try it online!

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

Answer 17

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 18

Keg, 6 bytes

21½Ë/ℤ

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

21½Ë/ℤ
2   # Push 2 to the stack
 1½ # Push 1 and halve it to get 0.5
   Ë    # Push 2 ** 0.5 (x ** 1/2 = sqrt(x))
    /ℤ  # Divide and cast to integer (floor) 

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

Answer 19

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.

Answer 20

Haskell, 20 bytes

f n=round$n/(sqrt 2)

Try it online

Answer 21

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)

Answer 22

TI-BASIC, 5 bytes

int(Ans√(2⁻¹

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

Explanation:

       √(2⁻¹   ;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.

Answer 23

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 24

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 \$2M^2<N^2\$.

EDIT: My program now implements \$2M^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.

Answer 25

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.

Answer 26

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.

Answer 27

Burlesque, 8 bytes

@2r@|/R_

Try it online!

@2   # Push 2.0
r@   # Sqrt it
|/   # Cast input to number, divide input by 2
R_   # Round to nearest

Answer 28

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

Answer 29

Charcoal, 46 bytes

≔⁰θ≔⁰ηＦ↨÷ＸＮ²¦²¦⁴«≔⁺×θ⁴ιθ≦⊗η¿›θ⊗η«≧⁻⊕⊗ηθ≦⊕η»»Ｉη

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.

Ｆ↨÷ＸＮ²¦²¦⁴«

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.

»»Ｉη

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

Answer 30

Pari/GP, 17 bytes

Another arbitrary-precision answer.

n->sqrtint(n^2\2)

Try it online!

Answer 31

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!

Answer 32

Ruby, 20 bytes

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

Try it online!

Answer 33

AWK, 19 17 bytes

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

Try it online!

Answer 34

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.

Answer 35

R, 19 bytes

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

Try it online!