Ask Your Question
1

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

asked 2022-07-27 20:02:38 +0200

Vibap gravatar image

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 flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
1

answered 2022-07-27 22:11:56 +0200

slelievre gravatar image

updated 2022-07-27 22:12:17 +0200

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

edit flag offensive delete link more

Comments

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

Vibap gravatar imageVibap ( 2022-07-28 03:39:43 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2022-07-27 20:02:38 +0200

Seen: 51 times

Last updated: Jul 27