patternMinor
Best algorithm to calculate the integer partition number
Viewed 0 times
thepartitionnumberalgorithmcalculateintegerbest
Problem
The total number of ways a positive number $n$ can be partitioned is called the partition number $p(n)$. The best algorithm I found on the internet is a dynamic programming implementation of Euler's pentagonal formula. Is there any proof that there cannot be any better algorithm? Is there any better algorithm already?
Solution
Fredrik Johansson showed in his work Efficient implementation of the
Hardy-Ramanujan-Rademacher formula how to compute $p(n)$ in time $O(\sqrt{n} \log^{4+o(1)} n)$ (the recent optimal integer multiplication algorithm might result in a removal of the $\log^{o(1)} n$ factor). This is nearly optimal, since the output length is $\Theta(\sqrt{n})$.
Hardy-Ramanujan-Rademacher formula how to compute $p(n)$ in time $O(\sqrt{n} \log^{4+o(1)} n)$ (the recent optimal integer multiplication algorithm might result in a removal of the $\log^{o(1)} n$ factor). This is nearly optimal, since the output length is $\Theta(\sqrt{n})$.
Context
StackExchange Computer Science Q#149657, answer score: 4
Revisions (0)
No revisions yet.