13
\$\begingroup\$

The "integer square root" of a non-negative integer \$ n \$ is defined as the largest integer not greater than \$ \sqrt{n} \$: $$ \operatorname{isqrt}(n) = \lfloor \sqrt{n} \rfloor = \max \{ k \in \Bbb N_0 \mid k^2 \le n \} $$ It is for example needed in prime factorization, as an upper bound for the possible factors.

A simple approach is to compute the floating point square root and truncate the result to an integer. In Swift that would be

func isqrt_simple(_ n: Int) -> Int {
    return Int(Double(n).squareRoot())
}

As observed in Computing the square root of a 64-bit integer, this can produce wrong results for large numbers, because an IEEE 64-bit floating point number with its 53 bit significand cannot represent large integers exactly. Here is an example:

let n = 9223371982334239233
let r = isqrt_simple(n)

print(r)           // 3037000491
print(r * r <= n)  // false

The correct result would be 3037000490, since $$ \sqrt{9223371982334239233} \approx 3037000490.9999996957524364127605120353 $$ (computed with PARI/GP).

The following implementation uses the ideas from DarthGizka's answer to the above mentioned question to implement a "correct" integer square root function in Swift 4:

func isqrt(_ n: Int) -> Int {
    precondition(n >= 0, "argument of isqrt() must be non-negative")

    var r = Int(Double(n).squareRoot()) // Initial approximation
    // Try to increase:
    while case let prod = r.multipliedReportingOverflow(by: r),
        !prod.overflow && prod.partialValue < n  {
            r += 1
    }
    // Decrease if necessary:
    while case let prod = r.multipliedReportingOverflow(by: r),
        prod.overflow || prod.partialValue > n  {
            r -= 1
    }
    return r
}

Example:

let n = 9223371982334239233
let r = isqrt(n)

print(r)                 // 3037000490
print(r * r <= n)        // true
print((r+1) * (r+1) > n) // true

Remarks:

  • I have chosen Int as argument and result type even if the square root is defined only for non-negative integers. The reason is that Int is the prevalent integer type in Swift and already used for quantities that can not be negative (e.g. the count of an array, or the MemoryLayout<T>.size of a type).
  • Int can be a 32-bit or 64-bit quantity, therefore I cannot check against a constant for overflow (as r < UINT32_MAX in DarthGizka's C++ solution). multipliedReportingOverflow() is used instead to check if squaring a candidate causes an overflow.

The code worked correctly in all my tests. Here are some tests which all succeed

func testSqrt(_ n: Int) {
    let r = isqrt(n)
    if r * r > n {
        print("Too large:", n, r)
    } else if (r+1) * (r+1) <= n {
        print("Too small:", n, r)
    }
}

testSqrt(4503599761588224)
testSqrt(4503599895805955)
testSqrt(4503600030023688)
testSqrt(4503600164241423)

testSqrt(9223371982334241080)
testSqrt(9223371982334239233)
testSqrt(9223372024852248003)
testSqrt(9223372024852247041)
testSqrt(9223372030926249000)
testSqrt(9223372030926247424)

These tests fail if isqrt_simple() is used instead.

All feedback is welcome, in particular suggestions how to improve the performance.

\$\endgroup\$

2 Answers 2

Reset to default
5
\$\begingroup\$

Your function is rather unnecessary. When converted to double, all 64-bit integers retain 1 sign bit and at least 52 precision bits. So the error is at most 11 bit; which means for any number N, the error $$dN<=\frac{2^{11}}{2^{63}}N=2^{-52}N$$ With simple calculus, the error of sqrt() is $$d(\sqrt{N})=\frac{dN}{2\sqrt{N}}<=\frac{2^{-52}N}{2\sqrt{N}}=2^{-53}\sqrt{N}<2^{-53}*2^{32}=2^{-21}<<1$$ In any case the error must be smaller than 1. With rounding/truncation, it can only be -1, 0, or 1.

So your code can be

func isqrt(_ n: Int) -> Int {
    var r = Int(Double(n).squareRoot()) // Initial approximation
    if r * r > n { r -= 1 }
    else if (r + 1) * (r + 1) <= n { r += 1}
    return r
}

edit: There will be time that (r + 1) * (r + 1) be larger than Int.max and causes error. Instead of using multipliedReportingOverflow, I would do it this way

func isqrt(_ n: Int) -> Int {
    if n >= 3037000499 * 3037000499 {return 3037000499}
    var r = Int(Double(n).squareRoot()) // Initial approximation
    if r * r > n { r -= 1 }
    else if (r + 1) * (r + 1) <= n { r += 1}
    return r
}

edit 2: To deal with different possible Int sizes:

func isqrt(_ n: Int) -> Int {
  #if arch(i386) || arch(arm)
    if n >= 46340 * 46340 {return 46340}
  #else
    if n >= 3037000499 * 3037000499 {return 3037000499}
  #endif

  var r = Int(Double(n).squareRoot()) // Initial approximation
  if r * r > n { r -= 1 }
  else if (r + 1) * (r + 1) <= n { r += 1}
  return r
}
\$\endgroup\$
9
  • 2
    \$\begingroup\$ Thank you for your answer and analysis. There is one problem though: (r + 1) * (r + 1) can overflow. As an example, isqrt(Int.max) will crash at runtime with your suggested implementation. \$\endgroup\$ Commented Jul 19, 2018 at 8:05
  • \$\begingroup\$ Swift has a &* operator which silently discards overflow (similar to what * does in other languages). But then isqrt(Int.max) would return 3037000500, which is one too large. \$\endgroup\$ Commented Jul 19, 2018 at 8:36
  • \$\begingroup\$ @MartinR I guess that's because you are using signed integers. Casting both r and n as unsigned and you should be good. \$\endgroup\$ Commented Jul 19, 2018 at 13:35
  • \$\begingroup\$ @MartinR See my new changes. \$\endgroup\$ Commented Jul 19, 2018 at 14:02
  • \$\begingroup\$ Int can be a 32-bit or 64-bit integer in Swift, that's why I wanted to avoid checking against a constant (compare remark #2 in my question). – Using UInt for intermediate results would be an option, I'll check that later. \$\endgroup\$ Commented Jul 19, 2018 at 14:08
-1
\$\begingroup\$

don't want to be an ass here, but in your case all the heavy lifting is actually done by Int(Double(n).squareRoot()) which is implemented in Swift standard library (I suppose, not a swift programmer my self). All your code does is actually +-1, so there's not much field for performance improvement I suppose. Generally in order to improve performance, you need to optimize the most time consuming operation, so in this case you'd have to reimplement Double(n).squareRoot() or implement custom sqr root method for integer, maybe based on some integer numerical approximation methods. Last but not least - this forum is IMHO rather for code style / quality review, your question rather belongs to stackoverflow.com, it's more popular so you might expect more feedback there.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Performance questions are on-topic (compare help center), and I did not restrict my question to that aspect ("All feedback is welcome ...") \$\endgroup\$ Commented Oct 24, 2017 at 11:39
  • \$\begingroup\$ Not saying they are off-topic, just saying you might get better feedback at SO as, like I said, your actual code does not do much work so there's not much to optimize / review here. Now, if you wrote your own sqrt implementation, that might be very nice too look at and comment of performance and stuff. \$\endgroup\$ Commented Oct 24, 2017 at 11:57
  • 1
    \$\begingroup\$ isqrt is slower than isqrt_simple by a factor of about 3, so the extra work (2 multiplications with overflow check) is relevant. Reducing that factor would be nice. \$\endgroup\$ Commented Oct 24, 2017 at 12:05

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.