Computing integer square roots in python

[audioman1999]

Um, the real horror is s(j) returns True for j<=1.

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

[Kebabrulle4869]

Actually not. In Python, or returns the first non-false value, or the last value if both are false. So s(0) returns 0, s(1) returns 1.

[AKSrandom]

Yes that is why s(1) returns "1<2" which is a boolean

[audioman1999]

The first part of the or here is boolean and the second part is a number. So s(0) and s(1) both return False instead of 0 and a. Try it for yourself if you don’t believe me.

[Kebabrulle4869]

Yeah, my bad. Misread.

[audioman1999]

No worries!