# Comparing pari.numbpart() and sympy.partition()

Hi. I understand this question is not contained to SageMath, but I determined to post a question on this forum because I felt this place was the closest to where the experts do exist, regarding math algorithm questions.

If I test and compare the running time of pari.numbpart() and sympy.partition() as the following,

import timeit
import sympy

def sy(n=10^4):
sympy.partition(n)

def par(n=10^4):
pari.numbpart(n)

print('Sympy   \t\t', timeit.timeit(sy, number=1))
print('PARI    \t\t', timeit.timeit(par, number=1))


I usually see the result as pari.numbpart function running faster. However, I'm not sure whether pari.numbpart is generally faster than sympy.partition.

My question is, what functional approach do pari.numpart and sympy.partition adopt respectively?

There are not many options as long as I know, such as Hardy–Ramanujan–Rademacher and brute force over Young's diagram. If there is someone, I hope ze could let me know what algorithmic approach does each function has taken, and which function is generally faster than the other. Moreover, if possible, I would like to know the complexity time (Big O) of each function.

Thanks.

edit retag close merge delete

Sort by » oldest newest most voted

Both use the Hardy-Ramanujan-Rademacher formula, see:

more

Thanks. I'm newbie so I didn't know from where I could refer to the documentations! Btw, It seems that Hardy-Ramanujan-Rademacher method runs over O((n^(1/2)) according to the following link.

Efficient implementation of the Hardy-Ramanujan-Rademacher formula