Return to Revisions

Let's start with a small note: The power parameter in

func powerDigitSum(x:Int, var power:Int) -> Int { ... }

need not be variable, so you can remove the var.

You use arrays to store "large integers", and the most significant digit is stored in the first array element (at index 0). As a consequence, the arrays are reversed in infMult() and the result is reversed again.

It would be easier to store the least significant digit at index 0 of the arrays. This simply means that you remove all reverse() calls in infMult() and intToIntArray().

This reduces the computation time slightly from 0.027 to 0.02 seconds on my computer.

Another improvement would be to store more than one decimal digit in each array element. On the OS X platform, Int is a 64-bit integer, so that you can safely store 8 decimal digits in the array elements without risking an overflow when multiplying two "large digits".

So you would define

let BASE = 100000000

replace all occurrences of 10 by BASE in your code, and change powerDigitSum() to

func digitSum(var x : Int) -> Int {
    var result = 0
    while x > 0 {
        result += x % 10
        x /= 10
    }
    return result
}

func powerDigitSum(x:Int, power:Int) -> Int {
    let powerSum = infPow(x, power)
    let result = reduce(powerSum, 0) { $0 + digitSum($1) }
    return result
}

This reduces the computation time to 0.011 seconds.

The greatest performance improvement can be achieved by using a better exponentiation algorithm in infPow(), such as Exponentiation by squaring (see also https://codereview.stackexchange.com/a/70197/35991 for a nice explanation).

In this context this would look like

func infPow(x:Int, var power:Int) -> [Int] {
    
    var result = [1]
    var square = intToIntArray(x)
    
    if power > 0 {
        if power % 2 == 1 {
            result = infMult(result, square)
        }
        power /= 2
    }
    while power > 0 {
        square = infMult(square, square)
        if power % 2 == 1 {
            result = infMult(result, square)
        }
        power /= 2
    }
    return result
}

This reduces the computation time to 0.0002 seconds.