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:

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:

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

And now, with the discovery of a second shortened form of division that gives the correct quotient when \$A^2 > C \ge A\$, 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.

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

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.

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

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

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\$.

And now, with the discovery of a second shortened form of division that gives the correct quotient when \$A^2 > C \ge A\$, I found an 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! Currently it's saving 9 bytes, but I haven't gone through the entire regex yet, so there may be more places it can be used.

(?=(x(x*)).*(?=1円*$)2円+$)(?=(x1円)+(x?(x*)))(?=4円(x(x*?))1円+$)(?=.*(?=(?=4円*$)4円5円+$)(x*?)(?=3円*$)(x?(x*))(?=9円*$)((?=1円+$)1円10円*$|$9円))(?=.*(?=(?=4円*$)(?=6円*$)(?=4円7円+$)6円5円+$|$4円)(x*?)(?=3円*$)(x?(x*))(?=13円*$)((?=1円+$)1円14円*$|$13円))(?=.*(?=12円12円9円$)(x*?)(?=3円*$)(x?(x*))(?=17円*$)((?=1円+$)1円18円*$|$17円))(?*.*?(?=((?=3円*(x?(x*)))21円(x(x*))(?=23円*$)(?=1円*$)1円24円*$)))(?=.*(?=23円*$)(23円24円+$))(?=.*(?=(?=21円*$)21円22円+$)(x*?)(?=3円*$)(x?(x*))(?=27円*$)((?=1円+$)1円28円*$|$27円))(?=.*(?=(?=21円*$)(?=23円*$)(?=21円24円+$)23円22円+$|$21円)(x*?)(?=3円*$)(x?(x*))(?=31円*$)((?=1円+$)1円32円*$|$31円))(?=.*(?=30円30円27円$)(x*?)(?=3円*$)(x?(x*))(?=35円*$)((?=1円+$)1円36円*$|$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|

# 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
(?=(x1円)+(x?(x*))) # 3円 = 1円 + 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; Use the second shortened form of division, because we're
 1円+$ # guaranteed that 6円 < 3円 thanks to using floor(sqrt(N))+1 as our number base.
)
(?=
 .*
 (?=
 (?=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
 (?=9円*$)
 (
 (?=1円+$)
 1円10円*$
 |
 $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
 (?=13円*$)
 (
 (?=1円+$)
 1円14円*$
 |
 $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
 (?=17円*$)
 (
 (?=1円+$)
 1円18円*$
 |
 $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
 (?=23円*$)
 (?=1円*$)
 1円24円*$
 )
 )
)
(?=
 .*
 (?=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
 (?=27円*$)
 (
 (?=1円+$)
 1円28円*$
 |
 $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
 (?=31円*$)
 (
 (?=1円+$)
 1円32円*$
 |
 $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
 (?=35円*$)
 (
 (?=1円+$)
 1円36円*$
 |
 $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 (削除ここまで) 852 bytes

This is a direct port of the (削除) 849 (削除ここまで) 840 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*))(?=9円*$)((?=1円+$)1円10円*$|$9円))(?=.*(?=(?=4円*$)(?=6円*$)(?=4円7円+$)6円5円+$|$4円)(x*?)(?=3円*$)(x?(x*))(?=13円*$)((?=1円+$)1円14円*$|$13円))(?=.*(?=12円12円9円$)(x*?)(?=3円*$)(x?(x*))(?=17円*$)((?=1円+$)1円18円*$|$17円))(?=.*?(?=((?=3円*(x?(x*)))21円(x(x*))(?=23円*$)(?=1円*$)1円24円*$))(?<=(?=(?=.*(?=23円*$)(23円24円+$))(?=.*(?=(?=21円*$)21円22円+$)(x*?)(?=3円*$)(x?(x*))(?=27円*$)((?=1円+$)1円28円*$|$27円))(?=.*(?=(?=21円*$)(?=23円*$)(?=21円24円+$)23円22円+$|$21円)(x*?)(?=3円*$)(x?(x*))(?=31円*$)((?=1円+$)1円32円*$|$31円))(?=.*(?=30円30円27円$)(x*?)(?=3円*$)(x?(x*))(?=35円*$)((?=1円+$)1円36円*$|$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!

# 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
(?=(x1円)+(x?(x*))) # 3円 = 1円 + 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; Use the second shortened form of division, because we're
 1円+$ # guaranteed that 6円 < 3円 thanks to using floor(sqrt(N))+1 as our number base.
)
(?=
 .*
 (?=
 (?=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
 (?=9円*$)
 (
 (?=1円+$)
 1円10円*$
 |
 $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
 (?=13円*$)
 (
 (?=1円+$)
 1円14円*$
 |
 $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
 (?=17円*$)
 (
 (?=1円+$)
 1円18円*$
 |
 $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
 (?=23円*$)
 (?=1円*$)
 1円24円*$
 )
 )
 (?<=
 (?=
 (?=
 .*
 (?=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
 (?=27円*$)
 (
 (?=1円+$)
 1円28円*$
 |
 $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
 (?=31円*$)
 (
 (?=1円+$)
 1円32円*$
 |
 $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
 (?=35円*$)
 (
 (?=1円+$)
 1円36円*$
 |
 $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+(?*)), (削除) 1169 (削除ここまで) (削除) 929 (削除ここまで) (削除) 887 (削除ここまで) (削除) 853 (削除ここまで) (削除) 849 (削除ここまで) 708 bytes

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

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 \ge A\$, 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|

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

# 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}$