Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

In Swift 3, how to calculate the factorial when the result becomes too high?

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.

like image 797
Jon Avatar asked May 07 '17 10:05

Jon


People also ask

What is the highest factorial we can calculate?

The last factorial is 170! “Did you know? The number 170 is the highest possible number you can calculate a factorial for? Any higher than 170, and the mathematical answer is infinity.” - visualfractions.com/calculator/fac…

How do you calculate factorial quickly?

Most of the time when you need factorials, you'll need many of them, so the best idea is to build a table. Then you can compute each one in constant time on average by using n! = n*(n-1)! .


2 Answers

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.

  1. Multiply each value in that array by n.
  2. 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

like image 75
vacawama Avatar answered Oct 08 '22 09:10

vacawama


You can use this library: BigInt

Install it using CocoaPods:

pod 'BigInt'

Then you can use it like this:

import BigInt

    func factorial(_ n: Int) -> BigInt {
        if n == 0 {
            return 1
        }
        else {
            return BigInt(n) * factorial(n - 1)
        }
    }

    print( factorial(50) )  // 30414093201713378043612608166064768844377641568960512000000000000
like image 44
Anton Novoselov Avatar answered Oct 08 '22 08:10

Anton Novoselov