trjhtr

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 


 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.

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.