# Three Partition-Function Algorithms Comparison

I have implemented three algorithms codes, in Swift:

1- Polynomial coefficient:

 // create polynomial
func arrangePoly(ofTerms term: Int, toLength len: Int) -> [Int] {
var a = Array(repeating: 0, count: len+1)

for i in stride(from: 0, to: a.count, by: term) {
a[i] = 1
}
return a
}
// polynomial product
func productToN(array1 a: [Int], arrayb b: [Int], toPower n: Int) -> [Int] {
var res = Array(repeating: 0, count: n+1)

for (pa, ca) in a.enumerated() {
for (pb, cb) in b.enumerated() {
if pa+pb <= n {
res[pa+pb] += ca*cb
}
}
}
return res
}
// test code: partition of N
var p1 = arrangePoly(ofTerms: 1, toLength: N)
var res = p1

for i in 2...N {
res = productToN(array1: res, arrayb: arrangePoly(ofTerms: i, toLength: N), toPower: N)
}
print(res[N])   // coefficient of x^N


2- Euler recurrence relations:

func eulerPartition(_ n: Int) -> Int {
if n < 0 {
return 0
} else if n == 0 {
return 1
} else {
var k = 1
var sum = 0
while k <= n {
let sign = power(-1, k-1)
sum += sign * (eulerPartition(n-(k*((3*k)-1)/2)) + eulerPartition(n-(k*((3*k)+1)/2)))
k += 1
}
return sum
}
}


3- Divisor sum formula:

// sigma(k) is the well-known sum of divisors of k
func part(_ n: Int) -> Int {
if n < 0 {
return 0
} else if n == 0 {
return 1
} else {
var k = 1
var sum = 0
while k <= n {
sum += sigma(k) * part(n-k)
k += 1
}
return sum / n
}
}


All the three versions gives the same results for each n >= 1, but with different efficiency. While the Euler recurrence algorithm is assumed, theoretically, to be the fastest of the three, the polynomial coefficient algorithm works the best on my core2duo laptop in spite of it is not recursively coded like the others. I am sure I have done something wrong, but I can not figure what or where.

Any idea?

• Questions about particular programming languages are off-topic here, but questions about algorithms (described in pseudocode) are on-topic. – Yuval Filmus Aug 11 '17 at 20:22
• Have you tried to estimate the running time of the algorithms? – Yuval Filmus Aug 11 '17 at 20:23
• For n = 35, for example, running time for Euler method is ~41 sec, while it takes less than 0.1 sec in the poly-coeff. method. – Ali_Habeeb Aug 12 '17 at 6:30
• This is a rather broad question. We have a post on the subject. – Yuval Filmus Aug 12 '17 at 6:46
• The paper already includes complexity analyses of the various algorithms. That is, for each of the algorithms there is an analysis of its asymptotic running time. – Yuval Filmus Aug 12 '17 at 6:57

Fibonacci(n)

You should modify the implementation so that after calculating eulerPartition for a certain $n$, if you are given the same $n$ again then you immediately return the previously calculated value.