Project Euler #16 in Swift - Power digit sum

I just finished Project Euler #16 in Swift, and since there is not any version yet on Code Review, I would like to have some comments on what I did to try to improve it.


2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.


What is the sum of the digits of the number 2^1000?

import Foundation

func addMulToResult(inout results:[Int], var mulResult:Int, index:Int) {

    if index == results.count {
        results.append(0)
    }

    mulResult = results[index] + mulResult

    var result = mulResult % 10

    results[index] = result

    var retain = mulResult / 10
    if retain > 0 {
        addMulToResult(&results, retain, index + 1)
    }
}

func infMult(left:[Int], right:[Int]) -> [Int] {

    var results:[Int] = [Int]()
    for (j, rightNumber) in enumerate(reverse(right)) {

        for (i, leftNumber) in enumerate(reverse(left)) {

            let mulResult = leftNumber * rightNumber
            addMulToResult(&results, mulResult, i + j)
        }
    }

    return results.reverse()
}

func infPow(x:Int, var power:Int) -> [Int] {

    var result = [1]
    var xArray = intToIntArray(x)
    while power > 0 {

        result = infMult(result, xArray)
        power--
    }

    return result
}

func intToIntArray(var number:Int) -> [Int] {
    var intArray:[Int] = []

    while number > 0 {

        intArray.append(number % 10)
        number /= 10
    }

    return intArray.reverse()
}

func powerDigitSum(x:Int, var power:Int) -> Int {
    let powerSum = infPow(x, power)

    let result = reduce(powerSum, 0) { $0 + $1 }

    return result
}

func euler16() {

    let number = powerDigitSum(2, 1000)

    println(number)
}

func printTimeElapsedWhenRunningCode(operation:() -> ()) {
    let startTime = CFAbsoluteTimeGetCurrent()
    operation()
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    println("Time elapsed : \(timeElapsed) s")
}

printTimeElapsedWhenRunningCode(euler16)

The code executes in 0.06s

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.

StackExchange Code Review Q#75646, answer score: 4