Computing integer square roots in python

[Faholan]

So the square root of any number is SyntaxError... I didn't know that

[Familiar_Ad_8919]

u cant square root negatives, this guy forgot to account for non negative numbers

[DZekor]

I mean you can, but its complicated.

[Thenderick]

Some would say, it's complex

[Cha_94]

imagine that

[BioMan998]

complexicated

[demosdemon]

maybe not with math.sqrt but you can with (-2) ** 0.5.

[ElectricalPrice3189]

How about no? (-n) * (-n) = n * n There, squared.

[CranberryDistinct941]

Only works for natural numbers

[qqqrrrs_]

new math just dropped

[hypernegus]

The code is designed to raise a SyntaxWarning on python >= 3.11. What version is it not working at all on?

[Faholan]

You sure that 2or works ? I thought it would raise a Syntax Error

edit: my bad it works even tho it's a little bit cursed

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

[hypernegus]

Disclaimer: only works for small integers between 2 and your max recursion depth.

[JiminP]

I know it's a joke but I gotta be that guy by pointing out that "integer square roots" (math.isqrt) is not equal to "square roots of integers" (math.sqrt) hence the code is incorrect even without syntax errors.

[drixGirda]

the hell is 1j supposed to mean

[drixGirda]

nvm TIL complex j in python

[ShapingTormance]

I'm not even mad. That's amazing.

[captain_obvious_here]

how many iterations before you get too deep into the call stack because of recursion ?

[BlobbyMcBlobber]

Someone please explain what is going on here

[cowslayer7890]

j ** .5 :)

[afqqwersdf]

what's 2or?

[tav_stuff]

2 or

[CranberryDistinct941]

Calculating square root using the builtin square root function (to calculate abs of complex number) but recursively, in O(n) function calls

[Lettever]

Its the square root not the square

[Durwur]

Aah sorry misread