Numbers as Strings Multiplication Function in Swift

Question

I was solving a problem 20, Factorial Digit Sum, on Project Euler.

Factorial Digits Sum

\$n!\$ means \$n \cdot (n − 1) \cdot \ldots \cdot 3 \cdot 2 \cdot 1\$

For example, \10ドル! = 10 \cdot 9 \cdot \ldots \cdot 3 \cdot 2 \cdot 1 = 3628800\,ドル and the sum of the digits in the number \10ドル!\$ is \3ドル + 6 +たす 2 +たす 8 +たす 8 +たす 0 +たす 0 =わ 27\$.

Find the sum of the digits in the number \100ドル!\$.

While doing this problem, I was working with really big numbers (\100ドル!\$ or \9ドル.33 \cdot 10^{157}\$). So at first, I decided to try to use Float80 and format it properly.

Since I have no I idea and could not find anything to properly explain to me how to do this with Float80 and String(format:_:) or NumberFormatter, I decided to make a function takes in two String parameters and returns their values multiplied as a String. With my multiplyLong (_:_:) function, I can multiply two numbers of any size. I wrote this function using concepts and principals from long multiplication from elementary school.

I wanted to find out if there is a better way to make a function that can multiply numbers of any size. Also, although my multiplyLong(_:_:) function works perfectly, it is quite long and I would like dramatically refine it, shorten it, and make it more efficient.

Note: I am using Swift 4.1 and Xcode 9.4

---

My multiplyLong(_:_:) Function

func multiplyLong(_ x: String, _ y: String) -> String {
 precondition(!x.isEmpty && !y.isEmpty, "Error, valid numbers are required for multiplication")
 var prefix = ""
 var containsInvalidCharacters : Bool {
 switch (x, y) {
 case let (s1, s2) where s1.first! == "-" && s2.first! == "-":
 return !((s1.dropFirst() + s2.dropFirst()).contains { ["0","1","2","3","4","5","6","7","8","9"].contains(0ドル) ? false : true })
 case let (s1, s2) where s2.first! == "-":
 prefix = "-"
 return !((s1 + s2.dropFirst()).contains { ["0","1","2","3","4","5","6","7","8","9"].contains(0ドル) ? false : true })
 case let (s1, s2) where s1.first! == "-":
 prefix = "-"
 return !((s1.dropFirst() + s2).contains { ["0","1","2","3","4","5","6","7","8","9"].contains(0ドル) ? false : true })
 case let (s1, s2):
 return !((s1 + s2).contains { ["0","1","2","3","4","5","6","7","8","9"].contains(0ドル) ? false : true })
 }
 }
 precondition(containsInvalidCharacters, "Error, multiplicand contains invalid non-numeric characters")
 let s1 = x.replacingOccurrences(of: "-", with: "").map { Int(String(0ドル))! }
 let s2 = y.replacingOccurrences(of: "-", with: "").map { Int(String(0ドル))! }
 var a = [Int]()
 var b = [Int]()
 switch (s1, s2) {
 case let (arr1, arr2) where arr1.count > arr2.count || arr1.first! >= arr2.first!:
 a = Array(arr1.reversed())
 b = Array(arr2.reversed())
 case let (arr1, arr2):
 a = Array(arr2.reversed())
 b = Array(arr1.reversed())
 }
 var lines = [[Int]]()
 for (bi, bn) in b.enumerated() {
 var line = Array(repeating: 0, count: bi)
 var carriedNumber = 0
 for an in a {
 let v = (bn * an) + carriedNumber
 carriedNumber = (v - (v % 10)) / 10
 line.insert(v % 10, at: 0)
 }
 if carriedNumber != 0 {
 if carriedNumber >= 10 {
 line.insert(carriedNumber % 10, at: 0)
 line.insert((carriedNumber - (carriedNumber % 10)) / 10, at: 0)
 } else {
 line.insert(carriedNumber, at: 0)
 }
 }
 lines.append(line)
 }
 let maxIndex = lines.max { 0ドル.count < 1ドル.count }!.count
 var result = [Int]()
 var addNum = 0
 for i in 0...maxIndex {
 var v = addNum
 for line in lines {
 v += line.indices.contains(i) ? line.reversed()[i] : 0
 }
 if v >= 10 {
 addNum = Int("\("\(v)".dropLast())")!
 result.insert(Int("\("\(v)".last!)")!, at: 0)
 } else {
 addNum = 0
 result.insert(v, at: 0)
 }
 }
 if addNum != 0 {
 for i in "\(addNum)".reversed() {
 result.insert(Int("\(i)")!, at: 0)
 }
 }
 result = Array(result.drop { 0ドル == 0 })
 let str = result.reduce("") { 0ドル + "\(1ドル)" }
 return prefix + str
}

---

My Solution

func factorialDigitSum() -> Int {
 let f = Array(1...100).map{ String(0ドル) }.reduce("1",multiplyLong)
 return f.map { Int("\(0ドル)") ?? 0 }.reduce(0, +)
}
print(factorialDigitSum()) //Prints "648"

Note: 648 is indeed the right answer.

---

Answer 1

The main performance bottleneck of your solution is the representation of big integers as a string. In each step of the factorial computation:

• The intermediate result is converted from a string to an integer array,
• the current factor is converted from Int to a string to an integer array,
• a "long multiplication" is done on the two integer arrays, and finally,
• the resulting integer array is converted back to a string.

Also in every step, both input strings are validated to contain only decimal digits (plus an optional minus sign).

This is not very efficient, and I'll address this point later.

Instead of validating each possible combination of input strings x and y, it is more simple to define both strings separately, using a common utility function:

func multiplyLong(_ x: String, _ y: String) -> String {
 func isValidNumber(_ s: String) -> Bool {
 guard let first = s.first else {
 return false // String is empty
 }
 let rest = first == "-" ? s.dropFirst() : s[...]
 return !rest.isEmpty && !rest.contains { !"0123456789".contains(0ドル) }
 }
 precondition(isValidNumber(x) && isValidNumber(y), "Valid numbers are required for multiplication")
 // ...
}

Note also how "0123456789" is used as a collection instead of ["0","1","2","3","4","5","6","7","8","9"], and that a conditional expression

<someCondition> ? false : true

can always be simplified to !<someCondition>.

The multiplication algorithm can also be improved. Instead of computing separate results for the product of one big integer with a single digit of the other big integer (your lines array), and "adding" those intermediate results later, it is more efficient to accumulate all products into a single array of result digits directly.

You also insert elements at the start each line array repeatedly, which requires moving all existing elements. This could be avoided by reversing the order of elements in line.

Finally note that the expression

(v - (v % 10)) / 10

which occurs at two places, can be simplified to v / 10.

A better representation

All the conversion from strings to integer arrays and back to strings can be avoided if we represent a "big integer" not as a string, but as an integer array directly. Let's start by defining a suitable type:

struct BigInt {
 typealias Digit = UInt8
 let digits: [Digit]
 let negative: Bool
}

digits holds the decimal digits of the big integer, starting with the least-significant one. UInt8 is large enough to hold decimal digits (and all intermediate results during the long multiplication). For reasons that become apparent later, we use a type alias instead of hard-coding the UInt8 type.

Now we define some initializers:

• The first one takes an array of digits, which is truncated for a compact representation. The lastIndex(where:) method has been added in Swift 4.2, see In Swift Array, is there a function that returns the last index based in where clause? on Stack Overflow for a possible approach in earlier Swift versions.

• The second initializer takes an Int and is based on the first one.

• We also add a digitSum computed property for obvious reasons.

Then we have:

struct BigInt {
 typealias Digit = UInt8
 let digits: [Digit]
 let negative: Bool
 init(digits: [Digit], negative: Bool = false) {
 if let idx = digits.lastIndex(where: { 0ドル != 0 }) {
 self.digits = Array(digits[...idx])
 } else {
 self.digits = []
 }
 self.negative = negative
 }
 init(_ value: Int) {
 var digits: [Digit] = []
 var n = value.magnitude
 while n > 0 {
 digits.append(Digit(n % 10))
 n /= 10
 }
 self.init(digits: digits, negative: value < 0)
 }
 var digitSum: Int {
 return digits.reduce(0) { 0ドル + Int(1ドル) }
 }
}

In order to print a big integer, we adopt the CustomStringConvertible protocol:

extension BigInt: CustomStringConvertible {
 var description: String {
 if digits.isEmpty {
 return "0"
 }
 return (negative ? "-" : "") + digits.reversed().map { String(0ドル) }.joined()
 }
}

Now we can implement the multiplication. This is essentially your method of long multiplication, but simplified to accumulate all digits into a single result buffer (which is allocated only once):

extension BigInt {
 func multiplied(with other: BigInt) -> BigInt {
 var result = Array(repeating: Digit(0), count: digits.count + other.digits.count)
 for (i, a) in digits.enumerated() {
 var carry: Digit = 0
 for (j, b) in other.digits.enumerated() {
 let r = result[i + j] + a * b + carry
 result[i + j] = r % 10
 carry = r / 10
 }
 while carry > 0 {
 let r = result[i + other.digits.count] + carry
 result[i + other.digits.count] = r % 10
 carry = r / 10
 }
 }
 return BigInt(digits: result, negative: self.negative != other.negative)
 }
 static func *(lhs: BigInt, rhs: BigInt) -> BigInt {
 return lhs.multiplied(with: rhs)
 }
}

Note how the init(digits:negative:) is used to compact the result array, i.e. to remove unnecessary zero digits.

As a bonus, we implement the * method so that big integers can be multiplied more naturally.

With all that, the digit sum of 100! is computed as

let sum = (1...100).reduce(BigInt(1), { 0ドル * BigInt(1ドル) }).digitSum
print(sum) // 648

In my tests on a 1.2 GHz Intel Core m5 MacBook, with the code compiled in the Release configuration (i.e. with optimization on), the above code runs in approximately 0.5 milliseconds, compared to 30 milliseconds with your original code.

Further suggestions

• Currently, the digits array contains the base-10 digits of the big integer. If we choose a larger Digit type and store more decimal digits in each array element, then less multiplications are required, making the multiplication more efficient.

  With UInt64 as the Digit type, one can perform multiplication of 9-digit decimal numbers without overflow. This requires changing the Digit type alias, and modifying all places in the code where base-10 arithmetic is done.

• Add a init?(string: String) initializer so that a big integer can be created with

  let bn = BigInt(string: "713847891471894789471894789478917417439274")
  

• Adopt the ExpressibleByIntegerLiteral protocol, so that a big integer can be created as

  let bn: BigInt = 123
  

• Add addition and subtraction to the BigInt type.

• If you feel courageous, add division and remainder calculation.

• Noah Wilder: I don't understand what you mean, I've since changed the Digit type to UInt64, and it seems to work perfectly, so then what do I need to do in regards to: "modifying all places in the code where base-10 arithmetic is done"? Also, when conforming to the ExpressibleByIntegerLiteral protocol, it means that I can only declare small instances of BigInt with IntegerLiterals, but not large, yes? In my conformance extension I have: typealias IntegerLiteralType = Int and init(integerLiteral value: IntegerLiteralType) { self.init(value) }, is that correct? Thanks @MartinR for your help!
• Martin R: @NoahWilder: Changing UInt8 to UInt64 alone does not improve the efficiency. The idea is that every array element holds not values 0...9, but 0...999999999 (for example). – You are right with respect to ExpressibleByIntegerLiteral.