In Swift 3, how to calculate the factorial when the result becomes too high?
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
Factorial with intermediate results - Swift playgrounds - index out of range error
results
is an empty array but you try to access values without appending values first.
The simplest solution might be to pre-populate your array with zeros.
var results: [Int] = Array(repeating: 0, count: n)
Factorials in Swift
As others have said you can use libraries that support larger numbers, or just don't allow values that are too big.
Note that if you want to handle very large values you might need to use a loop rather than a recursive algorithm because recursion can cause a Stack Overflow. Yes, that's right, an SO "eponymous crash".
To prevent numbers that are too big, figure out the largest number that doesn't crash, and do input checking and reject numbers bigger than that.
You can figure out the number that crashes it by going in the opposite direction and logging the count and the result every 10 steps:
1 * 2 * 3 * 4 * 5 * 6...
When you crash, go back to the previous largest logged value, start from there plugging in your previously logged factorial result, and step 1 at a time until you crash. Then only allow n that's 1 less than your crash value.
Factorial function produces wrong result for 21! and above
With long you can represent between -9,223,372,036,854,775,808 to +9,223,372,036,854,775,807 (source)so as soon the factorial pass that range you start to get errors.
Related Topics
Try, Try! & Try? What's the Difference, and When to Use Each
Get Description of Emoji Character
Swift Cross Compile to Single Linux Binary
Navigationview Pops Back to Root, Omitting Intermediate View
How to Check If a Property Value Exists in Array of Objects in Swift
Dynamic Row Hight Containing Texteditor Inside a List in Swiftui
Trouble Using Callbacks with Cgpattern in Swift3
What Is the Correct Date.Format for Mmm Dd, Yyyy Hh:Mm:Ss A? and How Convert to Dd-Mm-Yyyy Hh:Ii
Alamofire Asynchronous Completionhandler For Json Request
Reference to Property in Closure Requires Explicit 'Self.' to Make Capture Semantics Explicit
How to Access Nswindow from @Main App Using Only Swiftui
Fixing Nsurlconnection Deprecation from Swift 1.2 to 2.0
Why Non Optional Any Can Hold Nil
Draw on a PDF Using Swift on MACos
Stop a Dispatchqueue That Is Running on the Main Thread
Uitableviewautomaticdimension Not Working for Resizing Cell Height