4
\$\begingroup\$

This is my Swift code for finding the starting number, under one million, which produces the longest collatz chain.

var x = 1
var max = 0
var originalNum = 0

func collatzFunc(number: Int, originalNumber: Int){
    let oNum = originalNumber
    var num = number
    if num % 2 == 0{
        num = num/2
    } else {
        num = (3 * num) + 1
    }

    if num == 1{
        x += 1
    if max < x{
        max = x
        originalNum = oNum
    }
    return
    } else {
        x += 1
        collatzFunc(number: num, originalNumber: oNum)
    }
    }

for numbers in 1...1000000{
    x = 1
    collatzFunc(number: numbers, originalNumber: numbers)
}

print(originalNum)

This code is giving correct result but it's taking almost 5 seconds on my system to execute. I believe it can be done well under 1 sec. Where could I be wasting all that time?

\$\endgroup\$
  • \$\begingroup\$ You are recalculating the same values over and over. For example, if 12345 has a collatz sequence that is 50 long, and then later you find that 15001 has 12345 in it's sequence, you know that there are 50 more steps until it terminates. Don't recalculate them all, use memoization \$\endgroup\$ – Zack Sep 21 '17 at 17:35
  • \$\begingroup\$ I did find out that this must be the issue. Thanks for your help. \$\endgroup\$ – N4SK Sep 22 '17 at 7:36
  • \$\begingroup\$ Also have a look at codereview.stackexchange.com/a/157366/35991 if you plan to run the code on a 32-bit platform. \$\endgroup\$ – Martin R Sep 24 '17 at 21:41
1
\$\begingroup\$

Some suggestion to improve your code:

  • The global variables max and originalNum should be named differently to match their purpose, possibly with explaining comments.

  • The global variable x is used to keep track of the length of the current Collatz chain, this is better done by making the function return a value. That also allows to eliminate the second originalNumber parameter.

  • collatzFunc() should just compute the Collatz chain length for a given number, and the caller of that function should compare that with previously computed values.

  • Why assign var num = number if that value is then overwritten? You can simplify that to

    let num = number % 2 == 0 ? number / 2 : 3 * number + 1
    
  • The indenting is not always correct, and the spacing is not consistent (e.g. always put a space before opening curly braces).

  • The challenge asks for a number below 1 million, therefore the loop must be

    for number in 1..<1000000 { ... }
    

    and the singular form number is more appropriate here.

Putting it all together, this is how I would modify your code:

/// Compute the length of the Collatz chain starting at `number`.
func collatzFunc(number: Int) -> Int {
    if number == 1 {
        return 1
    }
    return 1 + collatzFunc(number: number % 2 == 0 ? number / 2 : 3 * number + 1)
}

var maxLength = 0 // Maximal length of Collatz chain found so far.
var maxNumber = 0 // Number for which this length is achieved.

for number in 1 ..< 1_000_000 {
    let length = collatzFunc(number: number)
    if length > maxLength {
        maxLength = length
        maxNumber = number
    }
}

print(maxNumber)

This is perhaps not faster than your version, but definitely better to read and therefore better to maintain.

You can also replace the recursive function by an iterative version

/// Compute the length of the Collatz chain starting at `number`.
func collatzFunc(number: Int) -> Int {
    var length = 1
    var num = number
    while num != 1 {
        num = num % 2 == 0 ? num / 2 : 3 * num + 1
        length += 1
    }
    return length
}

and check if that performs better.

As already mentioned in the comments, caching (or memoization) increases the performance dramatically. You'll find some caching solutions in the various answers to Project Euler problem 14 (longest Collatz sequence) in Swift 3. Here is a version using an array to cache all results for number up to a certain limit, this turned out to be quite fast:

var cache = [Int](repeating: 0, count: 1_000_000)
cache[1] = 1

func collatzFunc(number: Int) -> Int {
    if number < cache.count && cache[number] > 0 {
        return cache[number]
    }
    let length = 1 + collatzFunc(number: number % 2 == 0 ? number / 2 : 3 * number + 1)
    if number < cache.count {
        cache[number] = length
    }
    return length
}
\$\endgroup\$

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.