3
\$\begingroup\$

This code finds highly composite numbers (numbers with more factors than any smaller number) in Swift. I'm not too familiar with Swift, I did this in python but it was too slow so I decided to try it. I made some optimizations, such as only evaluating factors up to \$\sqrt{n}\$, but I would like to improve performance more. In particular, I'm not entirely sure about correcting for square numbers. Is checking whether sqrt(n) == Int(sqrt(n)) the fastest method, or is there something else that would work better? Is there anything else in the factoring that could be improved?

Edit: I don't really care about memory usage. Also, some general style advice would be appreciated, considering I don't use swift much.

#!/usr/bin/swift

func factors(_ n: Int) -> Int { 
    let root = Double(n).squareRoot() 
    let iroot = Int(root) 
    return 2 * (1...iroot).map({n % $0}).filter({$0 == 0}).count - (Double(iroot) == root ? 1 : 0) 
}

var max = 2

for i in 1...(Int(CommandLine.arguments[1]) ?? 100000) {
    let f = factors(i) 
    if f > max { 
        max = f 
        print(i, f) 
    } 
} 
\$\endgroup\$
0

1 Answer 1

0
\$\begingroup\$

The “main” function

for i in 1...(Int(CommandLine.arguments[1]) ?? 100000)

is both difficult to read and problematic:

  • If no arguments are given to the program then it just crashes.
  • If a non-integer argument is given then an upper bound of \$ 100,000 \$ is assumed.
  • If zero or a negative number is given as the upper bound then the program also crashes.
  • Additional arguments are silently ignored.

Better check the number of arguments and their validity explicitly, even if it is more code. Print an informative message if wrong arguments are given. It is also common usage to exit with a non-zero exit status if a command line program failed.

Use more descriptive variable names.

I would suggest something like this

if CommandLine.arguments.count != 2 {
    print("Usage: \(CommandLine.arguments[0]) upper_bound");
    exit(EXIT_FAILURE)
}

guard let upperBound = Int(CommandLine.arguments[1]), upperBound > 0 else {
    print("upper bound must be a positive integer");
    exit(EXIT_FAILURE)
}

var currentMax = 0

for i in 1...upperBound {
    let numFactors = factors(i)
    if numFactors > currentMax {
        currentMax = numFactors
        print(i, numFactors)
    }
}

(For command line programs with more parameters you might consider to use the Swift ArgumentParser package.)

Improving your factors function

Your factors() function seems works correctly, as far as I can see. There is a theoretical risk of rounding errors since a 64-bit IEEE floating point number with its 53-bit significant cannot represent all large integers precisely. But as long as your numbers are below \$2^{53} = 9007199254740992\$, you are on the safe side.

The name is a bit misleading: The function does not determine the factors of a numbers but the count of factors, better names might be countFactors or countDivisors.

The function is very inefficient however. It can be improved a bit with small effort, but there are much better algorithms (more below).

First note that

(1...iroot).map({n % $0})

creates an array of length iroot with all the remainders. Then

.filter({$0 == 0})

creates another array with all remainders which are zero. Creating (and disposing of) these arrays takes time (and memory), but all you are interested is the final count. Therefore an explicit loop is more efficient:

func factors(_ n: Int) -> Int {
    let root = Double(n).squareRoot()
    let iroot = Int(root)
    
    var count = 0
    for i in 1...iroot {
        if n.isMultiple(of: i) {
            count += 2
        }
    }
    if Double(iroot) == root {
        count -= 1
    }
    return count
}

A better algorithm

An efficient method to determine the number of divisors of an integer (and I'm repeating arguments from Getting all divisors from an integer now) is to use the prime factorization: If $$ n = p_1^{e_1} \, p_2^{e_2} \cdots p_k^{e_k} $$ is the factorization of \$ n \$ into prime numbers \$ p_i \$ with exponents \$ e_i \$, then $$ \sigma_0(n) = (e_1+1)(e_2+1) \cdots (e_k+1) $$ is the number of divisors of \$ n \$, see for example Wikipedia: Divisor function. Example: $$ 720 = 2^4 \cdot 3^2 \cdot 5^1 \Longrightarrow \sigma_0(720) = (4+1)(2+1)(1+1) = 30 \, . $$

A possible implementation (taken from Project Euler #12 in Swift - Highly divisible triangular number and updated for Swift 4+) is

func countDivisors(_ n : Int) -> Int {

    var n = n
    var numDivisors = 1
    var factor = 2

    while factor * factor <= n {
        if n % factor == 0 {
            var exponent = 0
            repeat {
                exponent += 1
                n /= factor
            } while n % factor == 0
            numDivisors *= exponent + 1
        }
        factor = factor == 2 ? 3 : factor + 2
    }
    if n > 1 {
        numDivisors *= 2
    }

    return numDivisors
}

Benchmarks

Running the code with an upper bound of \$10,000,000\$ (on a MacBook Air, compiled in Release configuration):

  • With your original factors function: 49 seconds.
  • With the improved factors function: 13 seconds.
  • With the countDivisors function: 3 seconds.

Further suggestions

I may be advantageous to compute all prime numbers (up to the square root of the upper bound) in advance, for example with the Sieve of Eratosthenes.

Then you can use these prime numbers as trial divisors in the countDivisors function instead of trying all odd numbers.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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