Counting Squares In a Range

Question

I've been working on a series of programming challenges to work on my math skills, and I came across a solution that I don't know how to explain.

The problem:

"For 1 <= A <= B <= 10^9, find the number of perfect squares between $A$ and $B$ (inclusive).

My initial solution was to loop through all the numbers in a range and count the perfect squares that way. However, this was obviously a very slow solution (~ 14 seconds for range 1 -> 10^9).

Then, I came across the following:

"The number of squares between $A$ and $B$ = sqrt(B) - sqrt(A - 1) rounded down".

NOTE: From an answer to this question, rounded down is incorrect in this case, but this formula holds for finding the perfect squares in a given range. The code for this question actually converts the value to an int, which performs rounding to the nearest integer, not necessarily down.

This is cool and offered a vastly quicker solution, but I don't understand why.

Can anyone help me understand why this simple equation actually works?

Answer 1

I presume $A$ and $B$ are positive integers. The number of squares $\le B$ is $\lfloor \sqrt{B} \rfloor$. The number of squares $< A$ is the number of squares $\le A-1$, and thus $\lfloor \sqrt{A-1}\rfloor$. The number between $A$ and $B$ (inclusive) is the difference between these.

EDIT: But this is not the same as " sqrt(B) - sqrt(A - 1) rounded down". For example, take $A = 3$, $B = 4$. There is one square ($4$) between $A$ and $B$, inclusive, but $\lfloor \sqrt{4} - \sqrt{2}\rfloor = 0$.

Answer 2

To understand why this is the answer, let's start off with a simpler. Lets take a look at the number of perfect squares between $0$ and $B$. What more, let's assume that $B$ is a perfect square, meaning there exists $C$ such that $C^2=B$.

How many perfect squares are there between $0$ and $B$? There are exactly $C$ - for each integer from 1 to $C$ we have a square number.

Let's now assume $B$ is between $C^2$ and $(C+1)^2$. How many square numbers are there between $0$ and $B$ this time? We definitely have $C$ numbers, since $C^2 < B$. The $C+1$-th number is too big, however, to contribute to the total - that leaves us with exactly $C$ perfect squares. Let us notice that $\sqrt B\in(C, C+1)$, from which $\lfloor \sqrt B \rfloor = C$.

So now we return to the original question: we know that from $0$ to $A$ we have $\lfloor \sqrt A \rfloor$ perfect squares. From $0$ to $B$ we have $\lfloor \sqrt B \rfloor$ perfect squares. So from $A$ to $B$ we have as many as there are from $0$ to $B$ minus as many as from $O$ to $A-1$(due to the fact, that we are interested in the perfect squares between $[A,B]$) - that is, $\lfloor \sqrt B \rfloor - \lfloor \sqrt(A - 1) \rfloor$.