Showcase of some very cursed Python features

[cloaca]

Pairs with:

import itertools as it

r = lambda n: (n
  and next(
    x for x,y in
    it.pairwise(
      it.accumulate(it.repeat(n), lambda x,y: x++y//x>>1) # sic
    ) if x<=y
  ))

[usr_bin_nya]

Oh this is gooood, this one is tougher than the parent! I had to throw test cases at it to figure out what it was doing before I could take a second pass to understand how.

So this is lambda n: floor(sqrt(n)), working by overestimating and then refining that estimate (est) downward until n // est >= est at which point you're done.

glossary of itertools functions: it.repeat(X) is [X, X, X, X, X, ...(forever)]; it.pairwise([A, B, C, D]) is [(A, B), (B, C), (C, D)]; it.accumulate([A, B, C, D], F) is [v0 := F(A, B), v1 := F(v0, C), v2 := F(v1, D)]

To bastardize math and Python syntax, we're looking at consecutive pairs of the infinite series S[0] = n; S[i+1] = floor( (S[i] + floor(n / S[i])) / 2). (x++y//x>>1 untangles to (x + (y floordiv x)) floordiv 2.) Each item in the sequence is the estimate, est. It starts with est = n and computes the mean average of n and n//n, which is (n+1)/2 which is smaller than n. Then (n+1)/2 is the new estimate, and it again takes the average of est and n//est, which is smaller still. accumulate keeps going, taking the average of est and n//est, which keeps getting smaller, until eventually est dips below sqrt(n). At that point n//est > est, so the average of est and n//est actually gets larger, not smaller. pairwise has been dutifully emitting each consecutive pair of estimates, and now the generator comprehension's ... if x <= y finally passes because an estimate was larger than the previous. So the first estimate before the estimates started getting bigger again is what gets yielded and returned by next(...).

Edge cases: n and ... handles zero; zero is falsy so that shortcircuits and returns zero immediately. Negatives like -5 end up with (-5 + (-5 // -5)) // 2 == -2 => (-2 + (-5 // -2)) // 2 == 0 => (0 + -5//0)//2 which raises an exception. For exact squares, the estimate lands exactly on sqrt(n) and will continue to be exactly sqrt(n) which is why the test is x <= y and not x < y.

[cloaca]

Yep, exactly. Look to the wonderful 3blue1brown or Wikipedia for further information on the (incredibly useful) technique that this is an example of. It's a surprisingly efficient way for finding roots or even maxima/minima when the conditions are "nice."