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.
