More Advanced Math (e.g. combinatorics) in Swift?

Using Swift
1

Can anyone direct me to some suitable Swift libraries with higher math operations?

The one I'm specifically thinking of here is the math on combinations and permutations. The problem I'm having writing them "from scratch" is the possibility of having to divide into numbers like 20! (=2,432,902,008,176,640,000). Has anyone else found a good, ready, mix-in solution for this sort of work?

2

maybe look at BigInt?

3

I don’t know of a combinatorics library offhand, but if I were writing one I would try to avoid multiplying out factorials. I would probably adopt the strategy of working with prime powers in this domain.

1 Like
4

that's gonna get really messy really quick. but I don’t see how this is a question about using Swift. this same problem exists in every other language and i’m sure someone has already written an article about this for some other language

1 Like
5

If you want precision and speed, try the following:

  • You have some type that is a “combinatoric”
  • Combinatorics don’t store the value they represent, but only a formula, e.g. 9!/7! is stored like that and not like “72”.
  • Since they store a formula, it can be (a) quickly reasoned about, and thus (b) simplified. You could multiply and divide many Combinatorics and simplify the resulting formula into a canonical Combinatoric form.
  • They can be converted to (a) Strings, for printing, (b) Cooler Strings: a tree that shows the structure of all the nested fractions in case you’d like to print it somewhere else but preserving its structure. And they can as well be converted to (c) BigBigBigIntegers, for whenever you’d like to print them in Integer form.

A pet idea of mine is to have something like this for doing exact calculations over Rational numbers (or even Algebraic, since their representation can be finite just like Rationals’). Remember that you only need the BigBigBigInteger value in case you’d want to show it somewhere. Until you need that, you can work symbolically over the formulaeic representation :)

6

I'd already taken my own hint (of sorts) on the factorials; the classic factorial function (without safeguards or error checking) would read something like:

func factorial(x: Int) -> Int64 {
    if (x==1) return Int64(x)
    else return Int64(x)*factorial(x-1)
}

Loading that into an array makes for much faster calculations, and even generating the array is simpler than using that function:

var facCache: [Int64] = [1, 1]

func fillFacCache() {
    for x in 2...20 { // The limits of Int64, apparently.
        facCache.append(Int64(x)*facCache[x-1])
    }
}

Neat, sweet, and petite. (Although it still only does the math up to 20!, and that bugs me). If I end up rolling my own combin() functions (and it's looking more likely as time goes on), that's sitting at the heart of that class, if only for its own use.

I've looked briefly at BigInt, and given that I need to work that math into floating point multiplication and division, (I'm peculiar about the precision of my probabilistic calculations, for which I need this stuff), nice as it may be in its own space it may be a non-starter here.

In the short term, for the specific application I'm working on, I may have to change the way I'm doing the math. But I can still see uses for this as a future include.

7

Int64s aren’t going to do the job if you want anything more than small binomial coefficients (in fact if you’re only going up to n = 20, there’s really only like 210 possible binomial coefficients,, just store them in a lookup table!)

if you want to go higher i would use a Dictionary to store prime factorizations and use the dictionary as a multiset which makes multiplying and dividing easy. the problem with that is you need a way to get the prime factorization of a number and that’s a very hard thing to do efficiently

3 Likes