4
\$\begingroup\$

This code runs slowly, even with numbers smaller than 1,000,000. Can someone help me optimize this thing?

// Finds the highest perfect square below a certain input (int)

let target: Int = 758865 // Swap this out for testing other numbers
var smlSqr = [Int]()
let findLimit = Int(Double(target).squareRoot().rounded(.up))   // Saves CPU time, because perfect squares less than
                                                                // number a but higher than a.squareRoot is impossible.

var index = 0
var maxSqr = 0 // Final result
var candidate = 0

repeat {
    smlSqr.append(index * index)
    index += 1
} while(index < findLimit)

while candidate < smlSqr.count {
    if smlSqr[candidate] > maxSqr {
        maxSqr = smlSqr[candidate]
    }
    candidate += 1
}

print(String(maxSqr)) // For debugging, should print out 100
print(Int(Double(maxSqr).squareRoot())) // For debugging, making sure the number is actually a perfect square

I'm using Swift 5.1 on Xcode 11. Also using a playground (if that helps)

\$\endgroup\$
4
\$\begingroup\$

Martin is right that playgrounds are notoriously inefficient. Using compiled target will solve this problem.

But the other issue is that the chosen algorithm is inefficient. Your algorithm is basically trying every integer, one after another, until you reach the appropriate value. So, with your input of 758,865, you’ll try every integer between 0 and 872. That’s 873 iterations.

There are far better approaches. Martin (+1) is right that the easiest solution is to use the built-in sqrt() function. That having been said, these sorts of questions are testing your ability to write algorithms and they don’t generally want you just calling some system function.

Binary search

So, which algorithm should we use? The “go to” solution for improving searches is often the binary search. Let’s say you wanted square root of n. You know that the answer rests somewhere in the range between 0 and n.

  1. Let’s consider 0 to be our “lower bound” and n to be our “upper bound” of possible values.
  2. Pick a “guess” value in the middle of the range of possible values;
  3. Square this guess by multiplying it by itself;
  4. See if the result of this is too big or too small;
    • If it’s too big, throw away the top half of the range (by adjusting the upper bound of our modified range to be what was previously the middle of the range, namely our last guess);
    • Likewise, if it’s too small, we throw away the bottom half of the range (by adjusting the lower bound of our range to be equal to the last guess); and
  5. Repeat the process, halving the range of possible values each time, looping back to step 2.

This binary search technique finds the answer to 758,865 in 20 iterations rather than 873.

That might look like:

func nearestSquare(below value: Int) -> Int? {
    guard value > 0 else { return nil }

    let target = value - 1
    var upperBound = value
    var lowerBound = 0

    repeat {
        let guess = (upperBound + lowerBound) / 2
        let guessSquared = guess * guess
        let difference = guessSquared - target
        if difference == 0 {
            return guessSquared
        } else if difference > 0 {
            upperBound = guess
        } else {
            lowerBound = guess
        }
    } while (upperBound - lowerBound) > 1

    return lowerBound * lowerBound
}

There are refinements you could do, but this is the basic idea. Keep cutting the range of possible solutions in half and trying the middle value until you’ve got a winner. The binary search is a mainstay of efficient searches through large ranges of possible values.

Newton-Raphson

That having been said, while a binary search is a huge improvement, there are even other, more efficient, algorithms, if you’re so inclined. For example, Newton–Raphson can calculate the result for 758,865 in only 12 iterations.

The Newton-Raphson is an iterative technique in which you

  1. take a guess;
  2. identify where that falls on a curve;
  3. calculate the tangent to that point on the curve;
  4. identify the x-intercept of that tangent; and
  5. use that as your next guess, repeating until you find where it crosses the x-axis.

So, the notion is that the square root of n can be represented as the positive x-intercept of the function:

\$y = x^2 - n\$

We know that the tangent of a given point on this curve in iteration i is:

\$y = m_ix + b_i\$

Where the slope is the first derivative of the above curve:

\$m_i = 2x_i\$

and the y-intercept is:

\$b_i = y_i - m_ix_i\$

And the x-intercept (i.e. our guess for the next iteration) of that tangent is:

\$x_{i+1} = -\frac{b_i}{m_i}\$

So, you can calculate the nearest perfect square below a given value using Newton-Raphson like so:

func nearestSquare(below value: Int) -> Int? {
    guard value > 0 else { return nil }

    let target = value - 1

    func f(_ x: Int) -> Int {                    // y = x² - n
        return x * x - target
    }

    var x = target
    var y = f(x)

    while y > 0 {
        let m = 2 * x                            // slope of tangent
        let b = Double(y - m * x)                // y-intercept of tangent
        x = Int((-b / Double(m)).rounded(.down)) // x-intercept of tangent, rounded down
        y = f(x)
    }

    return x * x
}

Or you can simplify that formula a bit, doing a few arithmetic substitutions, to:

\$x_{i+1} = x_i-\frac{y_i}{2x_i}\$

Thus:

func nearestSquare(below value: Int) -> Int? {
    guard value > 0 else { return nil }

    let target = Double(value - 1)

    func f(_ x: Double) -> Double {                    // y = x² - n
        return x * x - target
    }

    var x = target
    var y = f(x)

    while y > 0 {
        x = x - (y / x / 2).rounded(.up)
        y = f(x)
    }

    return Int(x * x)
}
\$\endgroup\$
6
\$\begingroup\$

Also using a playground (if that helps)

Well, that is the main reason for the slow execution. A playground is an interactive environment, and the code is not optimized. For all computations in the main playground file, intermediate results are displayed in the side bar (such as the values of the variables, or how often a loop has executed). This makes longer computations really slow.

For code that consists of many computation steps you better

  • either move it to a function in a separate playground source file,
  • or use a compiled Xcode project instead of a playground.

I often prefer a compiled project over a playground because

  • you can debug your code (single-step, inspect variables, ...),
  • you can enable optimizations (compile with the “Release” configuration) for performance critical tasks.

But your code can also be simplified and optimized. This loop

var index = 0
var smlSqr = [Int]()
repeat {
    smlSqr.append(index * index)
    index += 1
} while(index < findLimit)

appends one array element in each loop iteration, so that it can be written as a map operation:

let smlSqr = (0..<findLimit).map { k in k * k }

(You may also think about better variable names: what does smlSqr stand for?)

And this

var maxSqr = 0 // Final result
var candidate = 0
while candidate < smlSqr.count {
    if smlSqr[candidate] > maxSqr {
        maxSqr = smlSqr[candidate]
    }
    candidate += 1
}

determines the largest array element. The is a dedicated method for that purpose:

let maxSqr = smlSqr.max()!

(We can force-unwrap here if we know that the array is not empty.) But the array elements are sorted in increasing order, so that the largest element is actually the last element:

let maxSqr = smlSqr.last!

So what we have so far is

let target = 758865
let findLimit = Int(Double(target).squareRoot().rounded(.up))
let smlSqr = (0..<findLimit).map { k in k * k }
let maxSqr = smlSqr.last!

and now we can see that this can be simplified even further: The last element appended to the array is (findLimit - 1) * (findLimit - 1), so that we only need

let target = 758865
let findLimit = Int(Double(target).squareRoot().rounded(.up))
let maxSqr = (findLimit - 1) * (findLimit - 1)

(And this is so short and fast that you can execute it in in a playground directly, without any of the optimization tricks mentioned above.)

To make the code reusable, you should define it as a function:

func largestSquareRoot(lessThan n: Int) -> Int {
    let root = Int(Double(n).squareRoot().rounded(.up)) - 1
    return root * root
}

Note that this gives a nonsensical result for \$ n = 0 \$ and crashes for \$ n < 0 \$. You'll have to define what result you want in those cases.

\$\endgroup\$
  • \$\begingroup\$ smlSqr means "small squares" (a list of perfect squares smaller than input) \$\endgroup\$ – FlipperCanoe163 Sep 23 at 15:00
  • 2
    \$\begingroup\$ I think Martin figured that out. Lol. I think the point was that we generally prefer clarity over brevity, and as such smallSquares might be a better name than smlSqr. \$\endgroup\$ – Rob Oct 2 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.