How would I find the closest perfect square to a number, without using sqrt?

Python Help
61

Ugh. I hadn’t realized the OP wrote N = float(input("Number: ")). Somehow I thought the inputs are integers. Maybe because the name N indicates integers, see for example math.isqrt(n) (inputs must be ints) vs math.sqrt(x). My little closest_square(n) functions assumed int inputs and need something like + 0.5 for the midpoints between squares if they can be any floats, like:

def closest_square(x):
    i = sq = 0
    while x > sq + i + 0.5:
        sq += 2*i+1
        i += 1
    return sq
1 Like
62

in fact that was already the case with the then-running example, 24, given their starting suggestion:

>>> N = 24
>>> guess = N >> (N.bit_length() // 2)
>>> guess
6
>>> guess = (guess + N // guess) // 2
>>> guess # oops! changes by just 1, but still too large
5
>>> guess = (guess + N // guess) // 2
>>> guess # down by 1 again
4
>>> guess = (guess + N // guess) // 2
>>> guess # now up by 1, so 4 was right
5

I’m not 100% sure, but I’d bet a doughnut it’s OK to stop if it goes down by 1 twice in a row - but I’m 100% sure you can stop when it no longer decreases (for actual reasons :wink:, already briefly explained).

1 Like
63

Just to note, you didn’t miss it the first time; that post (and several others), had issues with their markdown syntax (code fences on the same line as code) that hid the first line of their code blocks (and didn’t terminate the code block/added triple backticks to the last line), so that line wasn’t visible right away until I fixed it for them, as I mentioned here.

2 Likes
64

No, you fixed a post of theirs that came afterwards. I’m talking about their near-top post.

65

You can/should stop at x=5 which is not too large, but the correct solution: x² = 25 is the nearest square to N=24.

66

Haha yeah, perfect squares was just to find an estimate, and then the decimal comes in later, i do think we have sorta moved past that whole perfect square thing now. I’d change the title if I knew how

1 Like
67

That is really cool to think about how far I’ve come with coding. My dad is a software manager who helps people code for a living so i did have a lot of help, he had me coding in scratch at 6, then i learned processing from a zoom class in 2021, and I just started in python in September using some book i found in my brother’s room. I’m really not good at all compared to all you guys but i do feel like I’ve come a long way. I was talking to a maths teacher about this exact formula the other day (i actually asked him about a formula for square route arround December and he said there’ wasn’t one, so i was showing him the new info i found) and he was saying for the leaving cert there’s a computer science course (that was the day we were picking subjects) and i looked through a past paper with my dad and it was some of the most simple questions i’ve seen, i could get an easy distinction on that with a week to study, so i feel really confident i could make a career out of this.

Wow i wrote a long paragraph, once i start typing i just can’t stop lmaoo

Completley random rant aside, for this square route program, i started it in a pretty boring history class and thought I’d get it finished in that day, wow i was wrong. I’m trying to take in all this advice I’m getting, it’s been really helpful, it does take me a while to decipher though, i will admit i have copy and pasted a couple paragraphs into chat gbt to get it to explain it to me. I’m looking at that issue with the infinite loop now, and i’ll update when i work it out. Thank you so much everyone for the help!!

1 Like
68

Also thanks for the note on the code ticks, I’ve been using them on discord for the past while and you don’t need to do that there, so thank you for the note i wouldn’t have noticed whatsover otherwise :smiley:

1 Like
69

Just tried to open the code again, I usually just have whatever I’m working on open all the time and it wasn’t open. I completley forgot, trying to run the code with that infinite loop completley crashed idle, and i had to restart my laptop because the cursor got stuck as the loading symbol, so yeah I wouldn’t recommend running that code, that’s definitely an issue i ned to fix

1 Like
70

Not sure if I’ve shown this already, but this is the current code

N = float(input("Number: "))
E = 1

while not E * E == N:
    E = (E + N / E) / 2
    print (E)
    
print(E)
print(E * E)

It feels really short and simple at the moment, really weird this tiny code has such a large discussion over it

Also really sorry i just sent a bunch of messages in a row the forums site just decided to tell me I can do multiple replies at once

1 Like
71

Last one ill do i swear (Probably wont be)

If the issue is the number being rounded, could i do something like, if round(E * E) = N, my issue with that though is that if i get a decimal like x.6 and it can still be brought down to a closer answer.
An idea i do have is to detect when E = the same number 2 times in a row, because once it gets to the point where it can’t be simplified any further it’ll just stay as the same number each time the formula runs right?
I’m not sure how to test that because trying to run an infinite loop will just crash idle and i won’t get a chance to look at how E changes over time.
in that situation I wouldn’t need to look at E*E at all i would just have to have while loop detect when the number starts repeating

72

Heres the code implementing that

N = float(input("Number: "))
E = 1
E2 = 1
loopRepeating = False

while not loopRepeating:
    E = (E + N / E) / 2
    if E2 == E:
        loopRepeating = True
    E2 = E
    
print(E)
print(E * E)

I don’t see any issues currently, seems to be working fine!

73

I’m using “correct” to mean floor(sqrt(N)). You have a different meaning, but just repeat that your suggestion is correct under your meaning, without supplying reasoning or code. Here’s my best guess at the code you have in mind:

def guy(n):
    g = n >> (n.bit_length() // 2)
    while True:
        g2 = (g + n // g) // 2
        d = abs(g - g2)
        if d <= 1:
            break
        g = g2
    return g, g2

It’s returning both final guesses so we can see which one (if either) is “correct” under various meanings of the word:

>>> guy(64) # both correct
(8, 8)
>>> guy(63) # 1st is floor, 2nd closest
(7, 8)
>>> guy(62) # both are floor, neither closest
(7, 7)
>>> guy(35) # 1st is closest, 2nd floor
(6, 5)
>>> guy(26) # 1st is ceiling, 2nd both closest and floor
(6, 5)

So no fixed way of picking is always “correct” under either meaning of the word. For 62, neither final guess was “closest”.

By my meaning of “correct”, “closest” is always gotten by going on to see which of r**2 and (r+1)**2`` is closest to n, where r is the computed floor(sqrt(n)). Code for that was already posted.

If you have different code in mind than what I guessed at, please post it.

1 Like
74

You should be able to scroll up to the top of the page, click the pencil icon next to the title, edit the title in the text field that appears, then click the accept button (a square button with a check-mark icon).

75

You’d win that bet. (guess + N // guess) // 2 is the same as (guess*guess + N) // (2 * guess), and that’s equal to guess - 1 if and only if 2 * guess * (guess - 1) <= guess*guess + N < 2 * guess * guess. That rearranges to (guess - 1)**2 - 1 <= N < guess**2, so either isqrt(N) = guess - 1, or N = (guess - 1)**2 - 1, the next guess is guess - 2, and isqrt(N) = guess - 2.

Ah, right; seems like we’ve got crossed wires here - @tim.one and I were talking about computing the floor of the square root, but you’re looking at computing the nearest perfect square to the initial value (which was indeed what @ccatcclawz originally asked for).

As it turns out, there’s a simple variant of the standard integer form of Heron’s algorithm that computes the nearest integer to the square root, and doesn’t suffer from the awkward termination condition problem - it always converges, from any positive integer starting guess, so we can just stop when the new value is equal to the old.

def sqrt_nearest(n: int, a: int = 1) -> int:
    """Find the closest integer to the square root of a positive integer n."""
    while True:
        a_old, a = a, a -- n // a >> 1
        if a == a_old:
            return a

(A form of this was used in the original Python 2.x decimal library.)

Indeed it does! I confess to being surprised, and a little horrified. There’s no obvious reason that we couldn’t end up oscillating between two different (but very close) values for E, so that E2 == E is never true. However, it turns out that there are nonobvious reasons that that can’t happen. Essentially, we always converge to a situation where N/E and E are either equal, or exactly one unit in the last place apart. And once we’ve hit that point, the averaging operation (E + N / E) / 2 will always prefer whichever of E and N/E has even last bit, thanks to the default round-ties-to-even rounding mode for IEEE 754 floating-point arithmetic.

By the way, your loopRepeating construct is a perfect use-case for Python’s break statement: you can rewrite your while loop like this:

while True:
    E = (E + N / E) / 2
    if E2 == E:
        break
    E2 = E
1 Like
76

When I do that it just shows me the version history rather than letting me change the title, i’d assume I just havn’t been on the the website for long enough and i’ll unlock that ability later

If its working does that mean we’re done here? thank you everyone so much for all of the help!! Here’s the final code then: :smile:

N = float(input("Number: "))
E = 1
E2 = 1

while True:
    E = (E + N / E) / 2
    if E2 == E:
        break
    E2 = E
    
print(E)
77

Great info, @mdickinson ! Thank you for sharing all that. Some surprises there!

This one was new to me:

In English, where the integer version of Heron’s method averages a and the floor of n/a, this is averaging in the ceiling of n/a instead.

I was surprised that it works to return round(sqrt(n)), and astonished that it’s so exceedingly well behaved. A bit of easy algebra convinced me it’s correct - but I doubt I would ever have thought of it on my own.

While doing that algebra, it occurred to me that there’s a dubious implicit assumption at work here too: that the original question (as interpreted by us to mean integer operations) - “which perfect square is closest to a given integer N?” has answer “the square of the integer closest to sqrt(N)”.

I believe that’s true, but it’s not obvious. It can be false for powers higher than 2. For example,

>>> n = 1165
>>> 10**3 - n
-165
>>> 11**3 - n
166
>>> n ** (1/3)
10.522250623254795
>>> round(_)
11

Spelling that out, n=1165 is closer to 10 cubed than to 11 cubed, but the cube root of n is closer to 11 than 10.

Squaring is “special” in that the average of the squares of consecutive ints is very close to the square of the average of those ints (the former is larger by 0.25):

(i**2 + (i+1)**2)/2 - ((i + (i+1))/2)**2 =
(2*i**2 + 2*i + 1)/2 - (i + 1/2)**2 =
i**2 + i + 1/2 - i**2 - i - 1/4 =
1/4

Which is one way of quantifying the observation that, between consecutive ints on the X axis, the graph of Y = X**2 is very well approximated by a straight line.

2 Likes
78

On the last observation about the behaviour of consecutive squares, if I’ve understood it correctly, it is actually linear, as the difference between consecutive squares is given by (n + 1)^2 - n^2 = 2n + 1.

For a real number x > 1 - which we may assume is not a square - there is a smallest n such that n^2 < x < (n + 1)^2 = n^2 + 2n + 1, which means n < sqrt(x) < n + 1. We can also write x = n^2 + r where 0 < r < 2n + 1.

Then math.isqrt(x) will give you n, but sqrt_nearest(x) will give you either n or n + 1, depending on whether the fractional part of sqrt(x), which partly depends on r, is closer to 0 or 1. So math.isqrt(x) <= sqrt_nearest(x). Example: for x = 2 we have math.isqrt(2) = 1, which is also math.isqrt(3), but sqrt_nearest(2) = 1 vs sqrt_nearest(3) = 2.

The sqrt_nearest seems like a nice complement to math.isqrt and might be useful as part of math. :slight_smile:

1 Like
79

Yes, newer users can only edit their posts for a certain period of time, which gets longer and then is eventually indefinite as one moves up to the highest Trust Levels. However, if you want to change the topic of an existing thread, you are usually better off just posting a new thread (as this one is rapidly approaching nearly a hundred posts long, and has several related discussions ongoing already).

81

Just to note, there are up to three pencil buttons on OPs if you are able to edit them:

image
image902×713 56.9 KB

  • Button 1 allows you to edit the title, category and tags for the entire thread.
  • Button 2 shows the edit history of the post (which is evidently the one you clicked)
  • Button 3 allows editing the text of the post

In this case, it is Button 1 that you want, but again, if you’re going to change the topic of the thread you should just create a new thread rather than try to make this long and winding thread about something else now. You’ll likely get more, on topic response, and it’ll make things easier to navigate for others and avoid confusion.

2 Likes