How to calculate the 21! (21 factorial) in swift?
Unsigned 64 bit integer has a maximum value of 18,446,744,073,709,551,615. While 21! = 51,090,942,171,709,440,000. For this kind of case, you need a Big Integer type. I found a question about Big Integer in Swift. There's a library for Big Integer in that link.
BigInteger equivalent in Swift?
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.
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)
Swift has error : thread return -x to return to the state before expression evaluation
The answer is in the error message - the upper bound of the range has to be greater than or equal to the lower.
Therefore you'll need to rewrite the method differently. You also have a fundamental flaw in your code - your maths logic is wrong - result will be overwritten every time, rather than accumulating a total. Adopting a similar approach to the question you can do this:
func factorial(_ num: Int) -> Int {
var result :Int = 1
guard num > 0 else {return result}. //0! is 1 not 0
var num = num
while num > 0 {
result *= num
num -= 1
}
return result
}
There is a more elegant way of performing this using recursion, which avoids the ugly var num=num
func fac2(_ num: Int, total: Int = 1) -> Int {
return num > 0 ? fac2(num-1, total: total * num) : total
}
How handle different threads in recursive function in swift?
My recommendation would be to split it into synchronous and asynchronous functions:
func factorial(of number: Double, completion: @escaping (Double) -> ()) {
DispatchQueue.global(qos: .background).async {
let result = factorial(of: number)
DispatchQueue.main.sync { //I don't know what thread you're intending to use, so I picked main :)
completion(result)
}
}
}
func factorial(of number: Double) -> Double {
var result: Double = 0
if number > 170 {
return Double.infinity
}
if number != Double(Int(number)) || number < 1 {return 0}
if number == 1 {
return 1
}
result = number * factorial(of: number - 1)
return result
}
This allows the meet of the work to happen in whichever way you want, without having to worry about potential threading issues.
Related Topics
Swiftui: Navigationlink Not Working If Not in a List
Spritekit Particle Emitter Multi Image
Converting Audiobuffer to Cmsamplebuffer with Accurate Cmtime
Binding 2 Properties (Observe) Using Keypath
Get Color of Point in a Skscene Swift
Save the Text in a Text Field as a Variable
Subscript of a Struct Doesn't Set Values When Created as an Implicitly Unwrapped Optional
How to Create Right Angle View in Swift
How to Animate Changes to an @Observedobject
How to Keep a Reference to Another Object in the Parameters of the Class
Changing Font Color of Uibarbuttonitem
Differenceand Purpose of Auto and Escaping Closure in Swift
How to Create Objects from Swiftyjson
Accurately Get a Color from Pixel on Screen and Convert Its Color Space
Why Do We Need to Explicitly Cast the Optional to Any
How to Save Value in Nsset Core Data (Swift)
Struggling with Notificationcenter/Combine in Swiftui/Avplayer