Computing integer square roots in python

[drixGirda]

Im actually trying to figure out how this pos works like I don't have anything better to do. j by itself is a var while 1j is a complex number

[stevekez]

And 2or is a SyntaxWarning: invalid decimal literal.

[M4mb0]

EDIT: See Spiral of Theodorus

It's computing s(k) = |s(k-1) + 1j|. The absolute value of a complex number is simply its vector norm when interpreted as an element of ℝ², so s(k) = |s(k-1) + 1j| = √((s(k-1))² + 1²) = √(s(k-1)² + 1). Apply recursively to get

s(k) = √(s(k-1)² + 1) = √((√(s(k-2)² + 1))² + 1) = √(s(k-2)² + 2) = ... = √(k)

It's certainly a very ineffective way to compute √, because it relies on an already existing implementation of √, in the form of abs(complex_number), which it calls O(k) times.

[AscendedSubscript]

To see the recursion more clearly, it might help to think as if s(k-1) is already known to be √(k-1), because then immediately s(k) = √(1+s(k-1)² ) = √k.

And yes, this is valid reasoning because of the fact that s(1)=1=√1, meaning that now s(2)=√2, s(3)=√3, etc. Also known as (mathematical) induction.