In Swift 3, how to calculate the factorial when the result becomes too high?
factorial, int, swift
Solution
Here's an approach that will let you find very large factorials.
Represent large numbers as an array of digits. For instance `987` would be `[9, 8, 7]`. Multiplying that number by an integer `n` would require two steps.
- Multiply each value in that array by `n`.
- Perform a carry operation to return a result that is again single digits.
For example `987 * 2`:
let arr = [9, 8, 7]
let arr2 = arr.map { $0 * 2 }
print(arr2) // [18, 16, 14]
Now, perform the carry operation. Starting at the one's digit, `14` is too big, so keep the `4` and carry the `1`. Add the `1` to `16` to get `17`.
[18, 17, 4]
Repeat with the ten's place:
[19, 7, 4]
And then with the hundred's place:
[1, 9, 7, 4]
Finally, for printing, you could convert this back to a string:
let arr = [1, 9, 7, 4]
print(arr.map(String.init).joined())
1974
Applying that technique, here is a `carryAll` function that performs the carry operation, and a `factorial` that uses it to calculate very large factorials:
func carryAll(_ arr: [Int]) -> [Int] {
var result = [Int]()
var carry = 0
for val in arr.reversed() {
let total = val + carry
let digit = total % 10
carry = total / 10
result.append(digit)
}
while carry > 0 {
let digit = carry % 10
carry = carry / 10
result.append(digit)
}
return result.reversed()
}
func factorial(_ n: Int) -> String {
var result = [1]
for i in 2...n {
result = result.map { $0 * i }
result = carryAll(result)
}
return result.map(String.init).joined()
}
print(factorial(1000))
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Problem
I have written this function to return the factorial of a given number ``` func factorial(_ n: Int) -> Int { if n == 0 { return 1 } else { return n * factorial(n - 1) } } print( factorial(20) ) // 2432902008176640000 ``` Works as it should, as long the given number does not exceed 20, because then the result becomes too high! How can I circumvent this limit and thus calculate the factorial of higher numbers? I have searched around and found some bignum libraries for Swift. I'm doing this to learn and be familiar with Swift, therefore I want to figure this out on my own.