Computing the integer square root of large numbers

Question

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.

Answer 1

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
}

Answer 2

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.