Project Euler #16 in Swift - Power digit sum

Question

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

Answer 1

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.